How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Maximize Boundary-Difference Subarray Sum

Q: Maximize Boundary-Difference Subarray Sum

This question evaluates algorithmic problem-solving skills with emphasis on array processing, constrained subarray sums, and the design of time- and space-efficient algorithms within the Coding & Algorithms domain.

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Given an integer array `nums` and an integer `k`, find the maximum possible sum of a non-empty contiguous subarray whose first and last elements differ by exactly `k` in absolute value. A subarray `nums[l..r]` is valid if: `abs(nums[l] - nums[r]) == k` Return the maximum sum among all valid subarrays. If no valid subarray exists, return `0`. Example 1: ```text Input: nums = [1, 2, 3, 4, 5], k = 3 Output: 14 Explanation: The subarray [2, 3, 4, 5] has endpoints 2 and 5, whose absolute difference is 3, and its sum is 14. ``` Example 2: ```text Input: nums = [-1, 3, 2, 4, 5], k = 3 Output: 11 Explanation: The subarray [2, 4, 5] has endpoints 2 and 5, whose absolute difference is 3, and its sum is 11. ``` Example 3: ```text Input: nums = [5, 1, 8], k = 10 Output: 0 Explanation: There is no valid subarray. ``` Constraints: ```text 1 <= nums.length <= 100000 -1000000000 <= nums[i] <= 1000000000 0 <= k <= 1000000000 ``` Design an algorithm efficient enough for the given constraints.

Quick Answer: This question evaluates algorithmic problem-solving skills with emphasis on array processing, constrained subarray sums, and the design of time- and space-efficient algorithms within the Coding & Algorithms domain.

Given an integer array nums and an integer k, find the maximum possible sum of a non-empty contiguous subarray nums[l..r] such that abs(nums[l] - nums[r]) == k. A subarray is valid if its first and last elements differ by exactly k in absolute value. Return the maximum sum among all valid subarrays. If no valid subarray exists, return 0. Note: When k = 0, a single-element subarray is valid because its first and last elements are the same element.

Constraints

1 <= nums.length <= 100000
-1000000000 <= nums[i] <= 1000000000
0 <= k <= 1000000000
The final answer fits in a signed 64-bit integer

Examples

Input: ([1, 2, 3, 4, 5], 3)

Expected Output: 14

Explanation: The subarray [2, 3, 4, 5] is valid because abs(2 - 5) = 3, and its sum is 14.

Input: ([-1, 3, 2, 4, 5], 3)

Expected Output: 11

Explanation: The subarray [2, 4, 5] is valid because abs(2 - 5) = 3, and its sum is 11.

Input: ([5, 1, 8], 10)

Expected Output: 0

Explanation: No contiguous subarray has endpoints whose absolute difference is exactly 10.

Input: ([4, -1, 4], 0)

Expected Output: 7

Explanation: The whole subarray [4, -1, 4] is valid because its endpoints are both 4, so the difference is 0 and the sum is 7.

Input: ([-5, -2, -4], 2)

Expected Output: -6

Explanation: The subarray [-2, -4] is valid because abs(-2 - (-4)) = 2, and its sum is -6. A valid subarray exists, so the answer is not 0.

Input: ([3, -100, 3, 4], 1)

Expected Output: 7

Explanation: The best valid subarray is [3, 4] using the later 3. Its endpoints differ by 1 and its sum is 7.

Input: ([7], 0)

Expected Output: 7

Explanation: A single-element subarray [7] is valid when k = 0 because its first and last elements are the same.

Hints

Use prefix sums so you can compute the sum of any subarray ending at index r in O(1) once you know its starting index.
For each ending value nums[r], the starting value must be either nums[r] - k or nums[r] + k. For each value, keep the smallest prefix sum seen before an index holding that value.

Quick Overview

This question evaluates algorithmic problem-solving skills with emphasis on array processing, constrained subarray sums, and the design of time- and space-efficient algorithms within the Coding & Algorithms domain.