Maximum Size Subarray Sum Equals k

Leetcode 325. Maximum Size Subarray Sum Equals k

Problem

Given an integer array nums and an integer k, return the maximum length of a subarray that sums to k. If there is not one, return 0 instead.

Example 1:

Input: nums = [1,-1,5,-2,3], k = 3
Output: 4
Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest.

Example 2:

Input: nums = [-2,-1,2,1], k = 1
Output: 2
Explanation: The subarray [-1, 2] sums to 1 and is the longest.

Constraints:

• 1 <= nums.length <= 2 * 105
• -104 <= nums[i] <= 104
• -109 <= k <= 109

Source: Leetcode 325. Maximum Size Subarray Sum Equals k

Solution

The idea

The idea is to go through the array and take cumulative sum. If the cumulative sum equals k, we find a length whose sum fulfills the criteria. Since the cumulative sum started from the beginning of the array, we can know the length of the sum from the current index. Pretty simple, right?

The problem happens if the sum is a result of some indices of which the beginning index in not the first index of the array. For example, the sum can be a result of index starting from 4 and ending up at 7 or some arbitrary number.

For those cases, we can take the cumulative sum and keep them in a map with their corresponding index. Then if at any point (say at index i1) we find that the cumulative sum – k was seen in the map before at an index i2, we can say that the values from index i1 to i2 sums up k! Thus the distance between i2 and i1 is the length of sum = k.

We can do this process for the entire array and keep getting the lengths and take the maximum length as our desired answer!

Detail explanation

If you are getting hard time understanding the idea, let’s go through a practical example as below.

Let’s say we have an array [5, 5, 2, 3, 7] and k=10 as below. We have a map seen_so_far which will be used to store the cumulative sum and index. At the beginning, i = 0, ans = 0 and cumulative_sum = 0 initialized.

At i = 0, we have cumulative_sum = 5 and we put this sum in the map with the corresponding index of i = 0.

Now, i moved forwarded to 1 and we find cumulative_sum = 5 + 5 = 10 = k! So, we update ans to be the length of cumulative_sum so far and update our map. At this point, if the array was of this size, ans = 2 would have been our final ans. But this is not the case and we have to move further to the array. Let’s increment i and see what happens next!

Now, i = 2 and nothing special happened here. We updated our cumulative_sum and the map as below. Let’s move forward i further.

Now i is at 3 and we update cumulative_sum = 15. Here is the func part!

We see that, now cumulative_sum – k = 5, in other words, cumulative_sum – 5 = k. This means, if we take the length from current index and the index where 5 was seen last, we get the length of the partial array whose sum is equal to k!

From the image below, we see this length is 3. But the length in our ans is currently 2. That means we got a longer length from the previous! So, we need to update our ans 🙂

If you have understood so far, you do not need to go further and we highly recommend you to implement the solution in your favourite programming language! 🙂

Now at i = 4, we again get the cumulative_sum – k seen before and we update everything as below. Here we found again a new length (3). But this is not longer than that one stored in ans variable. So, we won’t update ans here.

Finally, after all the values checked we find ans = 3 is the final maximum length of the subarray whose sum equals k!

Conclusion

C++ Code

class Solution {
public:
    int maxSubArrayLen(vector<int>& nums, int k) {
        map<int, int> seen_so_far;
        int cumulative_sum = 0;
        int len = nums.size();
        int ans = 0;
        
        for(int i = 0; i < len; i++){
            cumulative_sum += nums[i];
            if(cumulative_sum == k)
                ans = i + 1;
            if(seen_so_far.find(cumulative_sum - k) != seen_so_far.end()){
                ans = max(ans, i - seen_so_far[cumulative_sum - k]);
            }
            if(seen_so_far.find(cumulative_sum) == seen_so_far.end())
                seen_so_far[cumulative_sum] = i;
        }
        return ans;
    }
};

Conclusion

We hope the solution was explained well. If you still have any confusion, please write to the comment box below. If you like it or hate it, please give us feedback.

Lastly, one quick question, which type of problems you find most difficult to solve? For example, binary tree, recursion, two pointers, dynamic programming etc. Please write down below and we will try to have new articles covering your demands.

Happy coding! 😀