325. Maximum Size Subarray Sum Equals k
Problem Description
The problem asks us to find the maximum length of a subarray from the given array nums
, such that the sum of its elements is exactly equal to the given integer k
. A subarray is a contiguous part of an array. If such a subarray doesn't exist, we should return 0.
To clarify with an example, let's say our array is [1, -1, 5, -2, 3]
and k
is 3
. The subarray [1, -1, 5, -2]
sums to 3
, and its length is 4
, which would be the answer because there's no longer subarray that sums to 3
.
To approach this problem, we need to find a way to efficiently look up the sum of elements from the beginning of the array up to a certain point, and determine if there is a previous point where the sum was exactly k
less than the current sum. If we can find such a place, then the elements between these two points form a subarray that sums to k
.
Intuition
The intuition behind the solution lies in the use of a running sum and a hash table (or dictionary in Python). As we iterate through the array, we keep track of the cumulative sum of elements. The hash table stores the earliest index at which each cumulative sum appears.
Here's the reasoning:
- Start with a hash table
d
that maps a cumulative sum to the first index where it appears. Initialize it with the pair(0: -1)
, which says the sum0
is achieved before the first element. - Initialize variables for the current sum (
s
) and the maximum length found (ans
) to0
. - Iterate through
nums
, updating the running totals
by adding each elementx
to it. - Check if
s - k
has been seen before. If it has, we've found a subarray ending at the current index with a sum ofk
. - Update
ans
with the length of this subarray if it is longer than the maximum found so far. - Add the current sum to the hash table with its corresponding index, but only if this sum hasn't been seen before to maintain the earliest index.
The reason we only store the earliest occurrence of a sum is because we're looking for the longest subarray; any later occurrence of the same sum would yield a shorter subarray.
Learn more about Prefix Sum patterns.
Solution Approach
The solution leverages a hashing strategy to efficiently track the sum of elements in the subarrays and their starting indices. Here's a detailed walkthrough of the implementation:
-
Hash Table Initialization: We initiate a hash table (dictionary in Python) named
d
with a key-value pair{0: -1}
. This represents that the sum0
is achieved before starting the iterations, essentially before the first element at index-1
. This base case ensures that if the sum of elements from the beginning reachesk
, the length can be calculated correctly. -
Preparing Variables: Two variables are prepared:
ans
to store the maximum length of the subarray with sumk
found so far ands
to keep track of the running sum. -
Iteration & Running Sum: We use a loop to iterate over the array using
enumerate(nums)
which gives us both the indexi
and the valuex
. We increment the running sums
by the value ofx
. -
Checking for a Matching Subarray: During each iteration, after updating the running sum, we check if
s - k
is present in the hash tabled
. If it is, it means that from the earliest indexd[s - k]
to the current indexi
, the elements sum up exactly tok
. We then compare (i - d[s - k]
) withans
and store the larger one inans
. -
Updating the Hash Table: The hash table is updated with the running sum only if this running sum has not been recorded before. We do this because we are interested in the first occurrence of this running sum to ensure the longest possible subarray.
-
Returning the Result: After the loop ends,
ans
will be holding the length of the longest subarray that sums tok
. This value is returned as the final result.
This algorithm effectively uses the hashing technique to reduce the time complexity otherwise inevitable with brute force solutions. By using a hash table to record the first occurrence of each sum, the solution approaches an O(n)
time complexity, since it processes each element of nums
just once. The space complexity is also O(n)
in the worst case, as it might store each sum occurring in the array.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use the solution approach to walk through a small example. Consider the array nums = [3, 4, -3, 2, 1]
and the target sum k = 3
.
-
Hash Table Initialization: Initialize a hash table
d
with{0: -1}
. This signifies that before we start, the cumulative sum of0
is reached at an index before the array starts. -
Preparing Variables: The variables
ans
(maximum subarray length) ands
(running sum) are both set to0
. -
Iteration & Running Sum:
- For the first element
3
, the running sums
becomes3
. Sinces - k = 3 - 3 = 0
and the hash table contains0
with index-1
, we updateans
to1 - (-1) = 2
. - For the second element
4
,s
becomes7
. We look fors - k = 4
in the hash table, but it's not there, so no change toans
. - For the third element
-3
,s
is now4
. We look fors - k = 1
which is not in the hash table, non update toans
. - For the fourth element
2
,s
becomes6
. We look fors - k = 3
, and since it's not present, no update toans
. - For the last element
1
,s
increases to7
. We look fors - k = 4
. It has appeared before whens
was7
for the second element. The index then was1
. Now, the index is4
, so the length of the subarray is4 - 1 = 3
which is greater than the currentans
, so we updateans
to3
.
- For the first element
-
Checking for a Matching Subarray: Every iteration includes this check. We successfully find a matching sum during the first and last elements.
-
Updating the Hash Table: As we proceed, we update the hash table with the sums
3
,7
,4
, and6
at their respective first occurrences with the indices0
,1
,2
, and3
. -
Returning the Result: At the end of the iteration,
ans
holds the value3
, which is the length of the longest subarray with sumk = 3
. This is our final result.
The correct subarray that has the sum of 3
and the maximum length is [4, -3, 2]
. The running sum at the start of this subarray was 4
, and by adding the subarray elements, it became 7
. The subarray has 3
elements, hence ans = 3
is returned.
Solution Implementation
1class Solution:
2 def maxSubArrayLen(self, nums: List[int], target: int) -> int:
3 # Initialize a dictionary to store the cumulative sum up to all indices
4 sum_to_index = {0: -1}
5
6 # Initialize variables to store the maximum length of subarray and the cumulative sum
7 max_length = cumulative_sum = 0
8
9 # Iterate through the list of numbers
10 for index, num in enumerate(nums):
11 # Update the cumulative sum
12 cumulative_sum += num
13
14 # Check if there is a subarray whose sum equals 'target'
15 if (cumulative_sum - target) in sum_to_index:
16 # Update max_length with the larger of the previous max_length and the current subarray length
17 max_length = max(max_length, index - sum_to_index[cumulative_sum - target])
18
19 # If this cumulative sum has not been seen before, add it to the dictionary
20 if cumulative_sum not in sum_to_index:
21 sum_to_index[cumulative_sum] = index
22
23 # Return the maximum length of subarray found that adds up to 'target'
24 return max_length
25
1import java.util.HashMap;
2import java.util.Map;
3
4class Solution {
5 public int maxSubArrayLen(int[] nums, int k) {
6 // Create a hashmap to store the sum up to the current index as the key
7 // and the index as the value.
8 Map<Long, Integer> sumToIndexMap = new HashMap<>();
9 // Initialize the map with base case: a sum of 0 before index -1
10 sumToIndexMap.put(0L, -1);
11
12 // This will hold the maximum length of the subarray found so far
13 int maxLength = 0;
14
15 // This will keep track of the running sum
16 long sum = 0;
17
18 // Loop through every element in the array
19 for (int i = 0; i < nums.length; ++i) {
20 // Update the running sum with the current element
21 sum += nums[i];
22
23 // If a subarray ending at index i has a sum of (sum - k),
24 // then a subarray with sum k exists.
25 if (sumToIndexMap.containsKey(sum - k)) {
26 // Compare and store the maximum length found so far
27 maxLength = Math.max(maxLength, i - sumToIndexMap.get(sum - k));
28 }
29
30 // If the current sum has not been seen before,
31 // add it to the map with the corresponding index.
32 sumToIndexMap.putIfAbsent(sum, i);
33 }
34
35 // Return the maximum length of the subarray found
36 return maxLength;
37 }
38}
39
1#include <vector>
2#include <unordered_map>
3#include <algorithm> // For using max function
4
5class Solution {
6public:
7 int maxSubArrayLen(vector<int>& nums, int k) {
8 // Create a hashmap to store the cumulative sum and its index.
9 unordered_map<long long, int> indexByCumulativeSum{{0, -1}};
10 // Initialize variables to store the cumulative sum 's' and max length 'maxLen'.
11 int maxLen = 0;
12 long long cumulativeSum = 0;
13
14 // Loop through the array to compute the cumulative sum.
15 for (int i = 0; i < nums.size(); ++i) {
16 cumulativeSum += nums[i];
17
18 // If the current cumulative sum minus 'k' is found in the map, we found a subarray.
19 if (indexByCumulativeSum.count(cumulativeSum - k)) {
20 maxLen = max(maxLen, i - indexByCumulativeSum[cumulativeSum - k]);
21 }
22
23 // Only add the current cumulative sum and its index to the map if it's not already there.
24 // This ensures we keep the smallest index to get the longest subarray.
25 if (!indexByCumulativeSum.count(cumulativeSum)) {
26 indexByCumulativeSum[cumulativeSum] = i;
27 }
28 }
29
30 // Return the maximum length found.
31 return maxLen;
32 }
33};
34
1/**
2 * Finds the maximum length of a subarray with a sum equal to k.
3 * @param nums - The input array of numbers.
4 * @param k - The target sum to look for.
5 * @returns The length of the longest subarray which sums to k.
6 */
7function maxSubArrayLen(nums: number[], k: number): number {
8 // Initialize a map to store the cumulative sum as the key and its index as the value.
9 const cumSumIndexMap: Map<number, number> = new Map();
10 cumSumIndexMap.set(0, -1); // Base case: set the sum of an empty subarray before the first element to -1.
11
12 let maxLength = 0; // Initialize the maximum subarray length to zero.
13 let cumulativeSum = 0; // Variable to store the cumulative sum of elements.
14
15 // Iterate over the elements of the array.
16 for (let i = 0; i < nums.length; ++i) {
17 cumulativeSum += nums[i]; // Increment the cumulative sum with the current element.
18
19 // If cumulativeSum - k exists in the map, there's a subarray with sum k ending at the current index.
20 if (cumSumIndexMap.has(cumulativeSum - k)) {
21 // Update maxLength with the higher value between the previous maxLength and the new subarray length.
22 maxLength = Math.max(maxLength, i - cumSumIndexMap.get(cumulativeSum - k)!);
23 }
24
25 // If the current cumulativeSum isn't in the map, set it with the current index.
26 if (!cumSumIndexMap.has(cumulativeSum)) {
27 cumSumIndexMap.set(cumulativeSum, i);
28 }
29 }
30
31 // Return the maxLength found.
32 return maxLength;
33}
34
Time and Space Complexity
The provided Python code finds the length of the longest subarray which sums up to k
. It makes use of a hashmap (dictionary in Python terms) to store the cumulative sum at each index, which helps in finding subarrays that sum up to k
in constant time.
Time Complexity
The time complexity of the code is O(n)
, where n
is the number of elements in the input list nums
. This is because the algorithm iterates through the list once, and for each element it performs a constant time operation of adding the element to the running sum, checking if (s - k)
is in the dictionary d
and updating the maximum length ans
. All these operations are constant time operations: arithmetic operations, dictionary lookup and dictionary insertion (when s
is not already in d
).
Space Complexity
The space complexity of the code is O(n)
. In the worst case, every running sum is unique, and hence, each sum (represented by s
in the code) would be stored in the dictionary d
along with its corresponding index. Since there are n
such running sums in the worst case, the dictionary could contain up to n
key-value pairs.
Learn more about how to find time and space complexity quickly using problem constraints.
What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)
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
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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