Start by scanning the array while maintaining prefix sums to quickly calculate subarray sums. Track potential good subarrays using a hash map keyed by element differences. This ensures O(n) performance for finding the maximum sum of subarrays where the first and last elements differ exactly by k.
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.
How GhostInterview Helps
- Automatically tracks prefix sums and potential good subarrays, reducing manual bookkeeping.
- Highlights optimal scanning and hash lookup patterns to maximize sum efficiently.
- Flags edge cases like negative numbers or missing good subarrays to ensure correctness.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
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.
Need direct help with Maximum Good Subarray Sum instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Maximum Good Subarray Sum from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Find the shortest subarray in an infinite array that sums to a given target using array scanning and hash lookup.
Open problem page#2848 Points That Intersect With CarsCount covered integer points by merging overlapping car intervals or marking visited positions on the number line.
Open problem page#2845 Count of Interesting SubarraysCount all subarrays where the number of elements satisfying a modulo condition equals a target k using efficient prefix sums.
Open problem page