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.
Which of the following is a good use case for backtracking?
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.
Depth first search can be used to find whether two components in a graph are connected.
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.
pdoesn't containx - k = -1orx + k = 3, so we do not updateans.
Updatepwithnums[i + 1] = 5ands = 1. -
Second iteration (i=1):
x = nums[1] = 5,s = 1 + x = 6.
pcontainsx - k = 3from the future iteration but we don't use it yet.
Updatepwithnums[i + 1] = 3(next element) ands = 6. -
Third iteration (i=2):
x = nums[2] = 3,s = 6 + x = 9.
pcontainsx - k = 1, the prefix sum for1is1(from iteration i=0).
So, we find a good subarray(1, 3)with a sum of9 - 1 = 8. Updateansto8.
We also check ifx + k = 5, thoughpcontains it, it refers to a future value we'll get to. -
Fourth iteration (i=3):
x = nums[3] = 2,s = 9 + x = 11.
pcontainsx + k = 4, but no such value has been encountered yet, so we don't updateans.
Thenpis not updated this time, because we already stored5with a smaller prefix sum6. -
Fifth iteration (i=4):
x = nums[4] = 5,s = 11 + x = 16.
Again check ifpcontainsx - k = 3(from i=2) and it does.
We find another good subarray(3, 5)with a sum of16 - 9 = 7, but7 < 8, soansremains8.
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
391class 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}
371#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};
471// 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}
37Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?
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.
What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.
Recommended Readings
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.