#3026

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Maximum Good Subarray Sum

Find the maximum sum of any subarray where the first and last elements differ by exactly k using efficient array scanning and hash lookup.

array hash table prefix sum

Problem Statement

Given an array nums of length n and a positive integer k, a subarray is considered good if the absolute difference between its first and last elements is exactly k. Your task is to find the maximum sum among all good subarrays.

Return 0 if no good subarray exists. For example, nums = [1,2,3,4,5,6] with k = 1 has several good subarrays, and the one with the highest sum should be returned.

Examples

Example 1

Input: nums = [1,2,3,4,5,6], k = 1

Output: 11

The absolute difference between the first and last element must be 1 for a good subarray. All the good subarrays are: [1,2], [2,3], [3,4], [4,5], and [5,6]. The maximum subarray sum is 11 for the subarray [5,6].

Example 2

Input: nums = [-1,3,2,4,5], k = 3

Output: 11

The absolute difference between the first and last element must be 3 for a good subarray. All the good subarrays are: [-1,3,2], and [2,4,5]. The maximum subarray sum is 11 for the subarray [2,4,5].

Example 3

Input: nums = [-1,-2,-3,-4], k = 2

Output: -6

The absolute difference between the first and last element must be 2 for a good subarray. All the good subarrays are: [-1,-2,-3], and [-2,-3,-4]. The maximum subarray sum is -6 for the subarray [-1,-2,-3].

Constraints

2 <= nums.length <= 105
-109 <= nums[i] <= 109
1 <= k <= 109

Solution Approach

Use Prefix Sum with HashMap

Compute prefix sums for nums so any subarray sum can be quickly calculated. Store prefix sums in a hash map where keys are array elements. This helps quickly identify subarrays whose first and last elements differ by k.

Iterate and Check Differences

Scan the array from left to right, and for each element, check if there exists a previous element in the hash map such that the absolute difference is k. If so, calculate the subarray sum using prefix sums and update the maximum sum.

Maintain Maximum Efficiently

Track the running maximum as you iterate. Avoid recomputing sums from scratch by leveraging the prefix sum array. This ensures linear time complexity and prevents performance pitfalls on large inputs.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) since each element is processed once and hash lookups are O(1). Space complexity is O(n) for storing prefix sums and hash map entries.

What Interviewers Usually Probe

Checks if you understand prefix sums and hash table usage for subarray problems.
Wants to see how you optimize scanning large arrays without nested loops.
Assesses whether you handle negative numbers and zero-length edge cases properly.

Common Pitfalls or Variants

Common pitfalls

Recomputing subarray sums naively instead of using prefix sums causes timeouts.
Forgetting to handle negative numbers can lead to incorrect maximum sums.
Not checking both +k and -k differences when searching in the hash map.

Follow-up variants

Find minimum sum of good subarrays instead of maximum.
Return the number of good subarrays that meet the k difference condition.
Modify k dynamically based on subarray length or value ranges.

FAQ

What defines a good subarray in Maximum Good Subarray Sum?

A good subarray has its first and last elements differ by exactly k, meaning |nums[i] - nums[j]| == k.

Can the array contain negative numbers?

Yes, nums[i] can be negative, and prefix sums must account for them when calculating maximum subarray sums.

How does GhostInterview use hash maps in this problem?

It stores prefix sums keyed by element values to quickly find potential subarrays with the correct difference k.

What happens if there are no good subarrays?

The correct return value is 0, as no subarray meets the difference condition.

Is it necessary to check every subarray combination?

No, by scanning once and using prefix sums with a hash map, all candidate subarrays are efficiently evaluated without nested loops.

terminal

Solution

Solution 1: Prefix Sum + Hash Table

We use a hash table $p$ to record the sum $s$ of the prefix array $nums[0..i-1]$ for $nums[i]$. If there are multiple identical $nums[i]$, we only keep the smallest $s$. Initially, we set $p[nums[0]]$ to $0$. In addition, we use a variable $s$ to record the current prefix sum, initially $s = 0$. Initialize the answer $ans$ to $-\infty$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        ans = -inf
        p = {nums[0]: 0}
        s, n = 0, len(nums)
        for i, x in enumerate(nums):
            s += x
            if x - k in p:
                ans = max(ans, s - p[x - k])
            if x + k in p:
                ans = max(ans, s - p[x + k])
            if i + 1 < n and (nums[i + 1] not in p or p[nums[i + 1]] > s):
                p[nums[i + 1]] = s
        return 0 if ans == -inf else ans

Continue Practicing

#2875 minimum size subarray in infinite array #2848 points that intersect with cars #2845 count of interesting subarrays