3026. Maximum Good Subarray Sum

Problem Description

Given an array named nums with length n and a positive integer k, we define a subarray of nums as being good if the absolute difference between the first and last elements of the subarray is exactly k. In more formal terms, the subarray nums[i..j] is considered good if |nums[i] - nums[j]| == k. Our task is to identify the good subarray that has the maximum sum among all such good subarrays and return this maximum sum. If no such good subarray exists, we return 0.

To visualize this, imagine sliding a window along the array and at each step, checking if the window results in a good subarray by comparing the difference of the first and last elements with k. Simultaneously we'd need to calculate the sum of elements within this window. If the window qualifies as a good subarray, we compare its sum with the best sum available until that point (the 'maximum sum' we've found). Ultimately, we aim to find the subarray that both meets the good subarray condition and has the largest sum in comparison to all other good subarrays.

Intuition

The key to solving this problem lies in two concepts: prefix sum and efficient lookups using a hash table. The insight is that in order to quickly assess if a subarray ending at position i is good, we can consider the current element nums[i] and look for previously encountered elements that would satisfy the criteria for a good subarray when paired with nums[i]. This means looking for values nums[i] - k and nums[i] + k among the values we've seen.

Firstly, prefix sum comes into play because it helps us calculate the sum of any subarray efficiently. By keeping a running total as we work through the array, we can find the sum of any subarray in O(1) time using subtraction.

Secondly, a hash table is used to achieve O(1) lookup time for previously encountered values. This is critical because it helps us avoid checking every possible subarray one by one, which would result in O(n^2) complexity. Instead, we maintain a hash table where each entry is a pair of the form (value, prefix_sum). The value is an element from the array, and prefix_sum is the sum of all elements up to but not including value. As we iterate through the array, the hash table is updated with the smallest prefix sum encountered for each value.

In practice, if nums[i] - k is in the hash table, this means there exists a subarray ending at i that could potentially be a good subarray. By referencing the stored prefix sum for nums[i] - k, we can quickly calculate the sum of this subarray. The same applies if nums[i] + k is found in the hash table. We then update the answer with the larger of the current answer and this new sum, ensuring we always hold the maximum sum encountered so far.

At the end of the iteration, if the answer is still the placeholder for the smallest number (-infinity in programming contexts), we know no good subarray was found, and we return 0. Otherwise, we return the answer which represents the maximum sum among all good subarrays identified.

Learn more about Prefix Sum patterns.

Solution Approach

The implementation takes advantage of data structures and algorithms such as prefix sums, hash tables, and the iteration of array elements.

Starting off, a hash table p is used to store the smallest prefix sum encountered so far for each value in the array nums. The prefix sum s represents the sum of numbers from the start of the array up to the current index. This allows for efficient computation of subarray sums. A variable ans is initialized to negative infinity to keep track of the maximum subarray sum.

As the array is iterated over with the variable i tracking the index and x being the value of nums[i], the current prefix sum s is updated by adding x. The search for a good subarray involves checking if x - k or x + k exists in the hash table. If it does, the current subarray is potentially a good subarray, and the sum of this subarray can be calculated using the current prefix sum s minus the prefix sum stored for x - k or x + k in the hash table. If the calculated sum is greater than the current answer ans, it is updated with this new sum.

Moreover, for each iteration, if the next element nums[i + 1] is not present in the table, or if it exists but the associated prefix sum is greater than s, the table is updated with nums[i + 1]: s. This ensures that the hash table always contains the smallest prefix sum for each value, which is essential for calculating the maximum sum of a good subarray accurately.

Finally, if after iteration the answer ans remains negative infinity, this indicates that no good subarray was found; in this case 0 is returned. Otherwise, the maximum subarray sum that has been calculated by checking all the good subarrays is returned.

This solution effectively reduces the problem to a runtime of O(n) by avoiding iterative comparison of all possible subarrays, taking advantage of the properties of prefix sums for rapid calculation, and hash table lookups for constant-time access to the prefix sums needed to check for good subarrays and calculate their sums.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a small example:

Imagine we have an array nums = [1, 5, 3, 2, 5] and k = 2. We need to find the maximum sum among all the good subarrays where a good subarray has an absolute difference of k between its first and last elements.

We begin by initializing an empty hash table p, a variable s to keep track of the current prefix sum (starting with 0), and a variable ans with the value negative infinity to store the maximum sum found.

First iteration (i=0):
x = nums[0] = 1, s = 0 + x = 1.
p doesn't contain x - k = -1 or x + k = 3, so we do not update ans.
Update p with nums[i + 1] = 5 and s = 1.
Second iteration (i=1):
x = nums[1] = 5, s = 1 + x = 6.
p contains x - k = 3 from the future iteration but we don't use it yet.
Update p with nums[i + 1] = 3 (next element) and s = 6.
Third iteration (i=2):
x = nums[2] = 3, s = 6 + x = 9.
p contains x - k = 1, the prefix sum for 1 is 1 (from iteration i=0).
So, we find a good subarray (1, 3) with a sum of 9 - 1 = 8. Update ans to 8.
We also check if x + k = 5, though p contains it, it refers to a future value we'll get to.
Fourth iteration (i=3):
x = nums[3] = 2, s = 9 + x = 11.
p contains x + k = 4, but no such value has been encountered yet, so we don't update ans.
Then p is not updated this time, because we already stored 5 with a smaller prefix sum 6.
Fifth iteration (i=4):
x = nums[4] = 5, s = 11 + x = 16.
Again check if p contains x - k = 3 (from i=2) and it does.
We find another good subarray (3, 5) with a sum of 16 - 9 = 7, but 7 < 8, so ans remains 8.

After finishing the iteration, our answer ans = 8 is the maximum sum of all good subarrays. Thus, we return 8 as the result since ans did not remain negative infinity.

This walk-through exemplifies how we compute the maximum sum of a good subarray in linear time by utilizing prefix sums and hash table lookups.

Solution Implementation

1from typing import List
2
3# Class to define the solution
4class Solution:
5    def maximum_subarray_sum(self, nums: List[int], k: int) -> int:
6        # Initialize the maximum answer to negative infinity
7        max_sum = float('-inf')
8  
9        # A dictionary to keep track of the prefix sums encountered
10        prefix_sums = {nums[0]: 0}
11      
12        # Initialize the sum variable to 0
13        current_sum = 0
14  
15        # Loop through the list of numbers
16        for index, num in enumerate(nums):
17            current_sum += num  # Update the runnning sum with the current number
18          
19            # Check if the difference (current_sum - k) exists as a prefix sum
20            if current_sum - k in prefix_sums:
21                # Update the maximum subarray sum if a larger sum is found
22                max_sum = max(max_sum, current_sum - prefix_sums[current_sum - k])
23          
24            # Check if the difference (current_sum + k) exists as a prefix sum
25            if current_sum + k in prefix_sums:
26                # Update the maximum subarray sum if a larger sum is found
27                max_sum = max(max_sum, current_sum - prefix_sums[current_sum + k])
28          
29            # Prepare for the next iteration; check the next element if it's not the last
30            if index + 1 < len(nums):
31                next_value = nums[index + 1]
32                # Save the current sum in the prefix_sums dictionary if the
33                # next number has not been seen or a smaller sum has been seen before it         
34                if next_value not in prefix_sums or prefix_sums[next_value] > current_sum:
35                    prefix_sums[next_value] = current_sum
36      
37        # Return the maximum sum if found; otherwise, return 0
38        return max_sum if max_sum != float('-inf') else 0
39

1class Solution {
2    public long maximumSubarraySum(int[] nums, int k) {
3        // A map to store the prefix sum along with the corresponding number just after it.
4        Map<Integer, Long> prefixSums = new HashMap<>();
5        // Initialize the first value of the map.
6        prefixSums.put(nums[0], 0L);
7      
8        // Initialize a variable to keep track of the sum.
9        long currentSum = 0;
10        // Get the length of the input array.
11        int arrayLength = nums.length;
12        // Initialize the answer with the smallest possible value.
13        long maxSubarraySum = Long.MIN_VALUE;
14      
15        // Iterate through the elements of the array.
16        for (int i = 0; i < arrayLength; ++i) {
17            // Add the current value to the sum.
18            currentSum += nums[i];
19            // Check if there's a prefix sum that is current sum minus k
20            if (prefixSums.containsKey(nums[i] - k)) {
21                maxSubarraySum = Math.max(maxSubarraySum, currentSum - prefixSums.get(nums[i] - k));
22            }
23            // Check if there's a prefix sum that is the current sum plus k
24            if (prefixSums.containsKey(nums[i] + k)) {
25                maxSubarraySum = Math.max(maxSubarraySum, currentSum - prefixSums.get(nums[i] + k));
26            }
27            // If we're not on the last element and the upcoming element is either 
28            // not in the map or has a larger sum than the current, update the map.
29            if (i + 1 < arrayLength && (!prefixSums.containsKey(nums[i + 1]) || prefixSums.get(nums[i + 1]) > currentSum)) {
30                prefixSums.put(nums[i + 1], currentSum);
31            }
32        }
33        // If the answer hasn't been updated, return 0; otherwise, return the calculated max sum.
34        return maxSubarraySum == Long.MIN_VALUE ? 0 : maxSubarraySum;
35    }
36}
37

1#include <vector>
2#include <unordered_map>
3#include <algorithm>
4#include <climits>
5
6class Solution {
7public:
8    long long maximumSubarraySum(std::vector<int>& nums, int k) {
9        std::unordered_map<int, long long> prefixSumMap; // Stores prefix sums and their indices
10        prefixSumMap[nums[0]] = 0; // Initialize with the first element
11        long long currentSum = 0; // Current running sum
12        const int n = nums.size(); // Size of the input array
13        long long maxSum = LLONG_MIN; // Initialize max sum as minimum possible long long value
14
15        for (int i = 0;; ++i) {
16            currentSum += nums[i]; // Update the running sum
17
18            // Check if there is a prefix sum (currentSum - k), and update maxSum if needed
19            auto it = prefixSumMap.find(currentSum - k);
20            if (it != prefixSumMap.end()) {
21                maxSum = std::max(maxSum, currentSum - it->second);
22            }
23
24            // Similarly, check for (currentSum + k)
25            it = prefixSumMap.find(currentSum + k);
26            if (it != prefixSumMap.end()) {
27                maxSum = std::max(maxSum, currentSum - it->second);
28            }
29
30            // Break the loop if we've reached the end of the array
31            if (i + 1 == n) {
32                break;
33            }
34
35            // Update the prefix sum map for the next element if needed
36            // If a prefix sum for nums[i+1] does not exist or there's a greater sum found, update it
37            it = prefixSumMap.find(nums[i + 1]);
38            if (it == prefixSumMap.end() || it->second > currentSum) {
39                prefixSumMap[nums[i + 1]] = currentSum;
40            }
41        }
42
43        // If maxSum was not updated, return 0; otherwise, return the updated maxSum
44        return maxSum == LLONG_MIN ? 0 : maxSum;
45    }
46};
47

1// Function to calculate the maximum subarray sum with sum at most `k`
2function maximumSubarraySum(nums: number[], k: number): number {
3    // Initialize a map to keep track of prefix sums and their indices
4    const prefixSumIndices: Map<number, number> = new Map();
5  
6    // Set the prefix sum for the first element
7    prefixSumIndices.set(0, -1);
8  
9    // Initialize the answer with the smallest possible number
10    let maxSum: number = -Infinity;
11  
12    // Initialize summation variable to keep track of the running sum
13    let sum: number = 0;
14  
15    // Loop through the array
16    for (let i = 0; i < nums.length; ++i) {
17        // Add current number to the running sum
18        sum += nums[i];
19      
20        // Check if there's a prefix sum such that current sum - previous sum equals to k
21        if (prefixSumIndices.has(sum - k)) {
22            // Update maxSum with the largest sum found so far
23            maxSum = Math.max(maxSum, sum - prefixSumIndices.get(sum - k)!);
24        }
25      
26        // If this sum has not been seen before or the previous index is greater,
27        // update the map with the current index for this sum.
28        // This helps in finding the smallest index (leftmost) for this prefixSum
29        if (!prefixSumIndices.has(sum) || prefixSumIndices.get(sum)! > i) {
30            prefixSumIndices.set(sum, i);
31        }
32    }
33  
34    // If maxSum was not updated, there's no valid subarray sum; return 0. Otherwise, return maxSum.
35    return maxSum === -Infinity ? 0 : maxSum;
36}
37

Time and Space Complexity

Time Complexity

The function iterates over all the elements in the given nums list with a single loop, which results in a time complexity of O(n) where n is the length of the array nums. Despite the updates and lookups in the dictionary p, these operations are done in constant time on average, so they do not change the overall linear time complexity.

Space Complexity

The space complexity of the code is determined by the space needed to store the dictionary p which can potentially contain an entry for each unique number that appears as a running sum at each index of nums. Therefore, the space complexity is O(n) where n is the length of the array nums.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

The three-steps of Depth First Search are:

Identify states;
Draw the state-space tree;
DFS on the state-space tree.

True

False

I don’t know