Maximum Good Subarray Sum

Med

#2694Time: O(n^2). The nested loops iterate through all possible start and end points of subarrays, resulting in a quadratic number of pairs to check. The prefix sum calculation takes O(n), but it's dominated by the nested loops.Space: O(n). We need an auxiliary array of size `n+1` to store the prefix sums.3 companies

Patterns

Prefix Sum

Data structures

Array Hash Table

Companies

Atlassian Zepto Groww

Prompt

You are given an array nums of length n and a positive integer k.

A subarray of nums is called good if the absolute difference between its first and last element is exactly k, in other words, the subarray nums[i..j] is good if |nums[i] - nums[j]| == k.

Return the maximum sum of a good subarray of nums. If there are no good subarrays, return 0.

Example 1:

Input: nums = [1,2,3,4,5,6], k = 1
Output: 11
Explanation: 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
Explanation: 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
Explanation: 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 <= 10⁵
-10⁹ <= nums[i] <= 10⁹
1 <= k <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through all possible subarrays, checks if they are 'good', and calculates their sum to find the maximum. To optimize sum calculation, it uses a precomputed prefix sum array.

Algorithm

Create a prefix sum array prefix of size n+1, where prefix[i] stores the sum of elements from nums[0] to nums[i-1].
Initialize a variable maxSum to a very small value (e.g., Long.MIN_VALUE) and a boolean flag foundGoodSubarray to false.
Iterate through the array with a start index i from 0 to n-1.
For each i, iterate with an end index j from i+1 to n-1.
Check if the subarray nums[i..j] is good: if (Math.abs(nums[i] - nums[j]) == k).
If it's a good subarray, calculate its sum using the prefix sum array: currentSum = prefix[j+1] - prefix[i].
Update maxSum = Math.max(maxSum, currentSum) and set foundGoodSubarray to true.
After the loops, if foundGoodSubarray is true, return maxSum. Otherwise, return 0.

Walkthrough

The most straightforward way to solve this problem is to examine every possible subarray. A subarray is defined by its start and end indices, i and j.

We can use nested loops to generate all pairs of (i, j) where i < j. For each pair, we check if it forms a 'good' subarray by testing the condition |nums[i] - nums[j]| == k. If the condition is met, we then need to calculate the sum of the elements in nums[i..j].

A naive sum calculation for each good subarray would involve another loop, leading to an O(n^3) solution. We can optimize this by pre-calculating prefix sums. A prefix sum array, prefix, allows us to find the sum of any subarray nums[i..j] in O(1) time using the formula sum = prefix[j+1] - prefix[i]. This optimization reduces the overall time complexity to O(n^2).

We maintain a variable maxSum to keep track of the maximum sum found so far. Since the problem requires returning 0 if no good subarray exists, we use a boolean flag to track whether at least one has been found.

1class Solution {2    public long maximumSubarraySum(int[] nums, int k) {3        int n = nums.length;4        long[] prefix = new long[n + 1];5        for (int i = 0; i < n; i++) {6            prefix[i + 1] = prefix[i] + nums[i];7        }8 9        long maxSum = Long.MIN_VALUE;10        boolean found = false;11 12        for (int i = 0; i < n; i++) {13            for (int j = i + 1; j < n; j++) {14                if (Math.abs((long)nums[i] - nums[j]) == k) {15                    found = true;16                    long currentSum = prefix[j + 1] - prefix[i];17                    if (currentSum > maxSum) {18                        maxSum = currentSum;19                    }20                }21            }22        }23 24        return found ? maxSum : 0;25    }26}

Complexity

Time

O(n^2). The nested loops iterate through all possible start and end points of subarrays, resulting in a quadratic number of pairs to check. The prefix sum calculation takes O(n), but it's dominated by the nested loops.

Space

O(n). We need an auxiliary array of size `n+1` to store the prefix sums.

Trade-offs

Pros

Simple to understand and implement.

Cons

Inefficient for large inputs due to its quadratic time complexity, which will likely result in a 'Time Limit Exceeded' error on platforms with large test cases.

This approach improves upon the brute-force method by using a hash map to efficiently find the required starting elements for good subarrays. It processes the array in a single pass, achieving linear time complexity.

Algorithm

Compute a prefix sum array prefix of size n+1.
Initialize maxSum = Long.MIN_VALUE, a boolean foundGoodSubarray = false, and a hash map minPrefixSumMap to store (value, min_prefix_sum) pairs.
Iterate through the array with index j from 0 to n-1.
For the current element nums[j], consider it as the end of a subarray. Look for a valid start i < j.
Check for the two possible starting values: target1 = nums[j] - k and target2 = nums[j] + k.
If minPrefixSumMap contains target1, calculate the sum currentSum = prefix[j+1] - minPrefixSumMap.get(target1) and update maxSum and foundGoodSubarray.
If minPrefixSumMap contains target2, do the same.
After checking, update the map for nums[j] to be a potential start for future subarrays. Store prefix[j] for the key nums[j], keeping the minimum if the key already exists: map.put(nums[j], Math.min(map.getOrDefault(nums[j], Long.MAX_VALUE), prefix[j])).
After the loop, if a good subarray was found, return maxSum. Otherwise, return 0.

Walkthrough

To optimize the search for the maximum good subarray sum, we can rephrase the problem. For each possible endpoint j of a subarray, we want to find the best possible starting point i < j that satisfies |nums[i] - nums[j]| == k and maximizes the sum sum(nums[i..j]).

Using prefix sums, the sum is prefix[j+1] - prefix[i]. For a fixed j, maximizing this sum is equivalent to minimizing prefix[i].

The condition |nums[i] - nums[j]| == k means we are looking for a starting element nums[i] that is equal to either nums[j] - k or nums[j] + k.

This leads to an efficient O(n) algorithm. We iterate through the array from left to right (index j from 0 to n-1). We use a hash map to store the minimum prefix sum encountered so far for each number value. Let this map be minPrefixSumMap, where map.get(v) gives the minimum prefix[i] for all i processed so far where nums[i] == v.

In each iteration j:

Find a good subarray: We check if the map contains keys for nums[j] - k or nums[j] + k. If it does, we have found a potential starting point i < j. We calculate the sum using the stored minimum prefix sum (prefix[j+1] - minPrefixSumMap.get(target)) and update our maxSum.
Update the map: We then update the map with the information from the current index j. We record prefix[j] as a possible minimum prefix sum for the value nums[j]. This makes nums[j] available as a starting point for subsequent elements.

The order of these two steps is crucial. By checking for a subarray before updating the map, we ensure that we only consider starting indices i that are strictly less than the current ending index j.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public long maximumSubarraySum(int[] nums, int k) {6        int n = nums.length;7        long[] prefix = new long[n + 1];8        for (int i = 0; i < n; i++) {9            prefix[i + 1] = prefix[i] + nums[i];10        }11 12        long maxSum = Long.MIN_VALUE;13        boolean found = false;14        Map<Integer, Long> minPrefixSumMap = new HashMap<>();15 16        for (int j = 0; j < n; j++) {17            int val = nums[j];18            19            // 1. Check for good subarrays ending at j20            int target1 = val - k;21            if (minPrefixSumMap.containsKey(target1)) {22                long currentSum = prefix[j + 1] - minPrefixSumMap.get(target1);23                maxSum = Math.max(maxSum, currentSum);24                found = true;25            }26 27            int target2 = val + k;28            if (minPrefixSumMap.containsKey(target2)) {29                long currentSum = prefix[j + 1] - minPrefixSumMap.get(target2);30                maxSum = Math.max(maxSum, currentSum);31                found = true;32            }33 34            // 2. Update map with info from index j35            long currentPrefix = prefix[j];36            if (!minPrefixSumMap.containsKey(val) || currentPrefix < minPrefixSumMap.get(val)) {37                minPrefixSumMap.put(val, currentPrefix);38            }39        }40 41        return found ? maxSum : 0;42    }43}

Complexity

Time

O(n). We iterate through the array once. Hash map operations (get, put) take O(1) on average. The prefix sum calculation also takes O(n). The overall complexity is linear.

Space

O(n). We use an O(n) prefix sum array and a hash map that can store up to `n` unique elements in the worst case, leading to O(n) space.

Trade-offs

Pros

Highly efficient with linear time complexity, making it suitable for large inputs.
This is the optimal solution for the given constraints.

Cons

Requires extra space for the hash map and prefix sum array.
Slightly more complex to reason about than the brute-force approach.

Solutions

Solution

1public class Solution {2    public long MaximumSubarraySum(int[] nums, int k) {3        Dictionary < int, long > p = new Dictionary < int, long > ();4        p[nums[0]] = 0 L;5        long s = 0;6        int n = nums.Length;7        long ans = long.MinValue;8        for (int i = 0; i < n; ++i) {9            s += nums[i];10            if (p.ContainsKey(nums[i] - k)) {11                ans = Math.Max(ans, s - p[nums[i] - k]);12            }13            if (p.ContainsKey(nums[i] + k)) {14                ans = Math.Max(ans, s - p[nums[i] + k]);15            }16            if (i + 1 < n && (!p.ContainsKey(nums[i + 1]) || p[nums[i + 1]] > s)) {17                p[nums[i + 1]] = s;18            }19        }20        return ans == long.MinValue ? 0 : ans;21    }22}

1class Solution {2public3  long maximumSubarraySum(int[] nums, int k) {4    Map<Integer, Long> p = new HashMap<>();5    p.put(nums[0], 0L);6    long s = 0;7    int n = nums.length;8    long ans = Long.MIN_VALUE;9    for (int i = 0; i < n; ++i) {10      s += nums[i];11      if (p.containsKey(nums[i] - k)) {12        ans = Math.max(ans, s - p.get(nums[i] - k));13      }14      if (p.containsKey(nums[i] + k)) {15        ans = Math.max(ans, s - p.get(nums[i] + k));16      }17      if (i + 1 < n &&18          (!p.containsKey(nums[i + 1]) || p.get(nums[i + 1]) > s)) {19        p.put(nums[i + 1], s);20      }21    }22    return ans == Long.MIN_VALUE ? 0 : ans;23  }24}

1class Solution {2public:3  long long maximumSubarraySum(vector<int> &nums, int k) {4    unordered_map<int, long long> p;5    p[nums[0]] = 0;6    long long s = 0;7    const int n = nums.size();8    long long ans = LONG_LONG_MIN;9    for (int i = 0;; ++i) {10      s += nums[i];11      auto it = p.find(nums[i] - k);12      if (it != p.end()) {13        ans = max(ans, s - it->second);14      }15      it = p.find(nums[i] + k);16      if (it != p.end()) {17        ans = max(ans, s - it->second);18      }19      if (i + 1 == n) {20        break;21      }22      it = p.find(nums[i + 1]);23      if (it == p.end() || it->second > s) {24        p[nums[i + 1]] = s;25      }26    }27    return ans == LONG_LONG_MIN ? 0 : ans;28  }29};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem