Subarray Sum Equals K

Leetcode 560. Subarray Sum Equals K

Problem

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

Example 1:

Input: nums = [1,1,1], k = 2
Output: 2

Example 2:

Input: nums = [1,2,3], k = 3
Output: 2

Constraints:

• 1 <= nums.length <= 2 * 104
• -1000 <= nums[i] <= 1000
• -107 <= k <= 107

Source: Leetcode 560. Subarray Sum Equals K

Solution Approach – 1

Approach – 1: Brute force (bad approach)

You may skip reading this as this is the bad approach! But if you do not come up any idea in an interview setting, you can think of this approach as a starting point.

This is a very simple approach which is just taking all the subarray combinations and check if their sum equals K or not. During this process, if the sum is K, just increment a counter.

Approach – 1: Time and Space Complexity

Time complexity – O(n2), since we will apply a nested for loop to take all combinations of subarrays.

Space complexity – O(1), since it can be solved using constant space.

If you want to understand this approach more, please have a look at the below code. But we will highly recommend to understand the next approach since this will lay a foundation to solve many other problems with the same technique!

Code of Approach – 1

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int total_sub_arrays = 0;
        for(int i = 0; i < nums.size(); i++){
            int cumulative_sum = 0;
            for(int j = i; j < nums.size(); j++){
                cumulative_sum += nums[j];
                if(cumulative_sum == k)
                    total_sub_arrays += 1;
            }
        }
        return total_sub_arrays;
    }
};

Solution Approach – 2

Approach – 2: Cumulative sum with Hashing (smart approach!)

The idea of this approach is to take cumulative sum of each element. Then subtract K from them and check if we have seen that subtracted value before in any of the cumulative sums. If we see that value, that means the difference is K between our current position and the position where we have seen the value. In other words, if we sum up all the values from where current value minus K was seen until current value, we get the subarray sum equals K.

Confused?

Let’s walk through the idea visually! This might help 🙂

Let’s say we have an array as below and K = 10. We take a variable cumulative_sum = 0 and a map to keep track of cumulative sums that are already seen named map_seen_before. We put map_seen_before[0] = 1 which tells that, hey, I have already seen cumulative sum of 0! How and Why is that?

Let’s say our entire array’s sum is equal to K. So, we should take the entire array as a subarray whose sum equals K, right? But, K – K is 0 and we have not found any cumulative sum equals 0 that represent the entire array. To overcome this problem, we initialize our map with the idea of 0 is already seen!

Now, let’s start our journey of adding cumulative_sum. As below image, we will add -3 and make cumulative_sum = -3 and in the map we keep -3 which means, “I have seen -3 before”.

Moving forward, we will add the next element (1) and do the same as below image.

Also, we will do the same with the third element (7) as below image.

When we are at the fourth element (2, at index 3), the fun starts! You see in the image, the cumulative_sum (including 2) minus K is -3 which is already seen at index 0! That means, from index 0 (not including) up to index 3 (including), if we add all the elements (1,7 and 2), we get 10 which is K! In the map, value of -3 is 1, that means we have -3 once, so we will add 1 to our answer. (This is a very important thing to understand. If we had seen -3 twice, say for example imagine at index 1, we would have added 2 in our answer. Because in that case value at index 2 and 3 would also summed up to 10.)

If you still get hard time understanding what just happened at the fourth element, have a look at the below image and try to think about it!

Finally, when we are at the last element, we find that cumulative_sum is 10 and 10 – 10 is 0 which we have seen already! (Remember we initialized our map with 0? 🙂 )

Below image should be self explanatory for you to understand the final step.

Approach – 2: Time and Space Complexity

Time complexity – O(n), since we will have to traverse the entire array.

Space complexity – O(n), this is space required for the map. In worst case, we might have to save all the cumulative_sum values in the map when no value is seen before! Consider this array, [1, 2, 3, 4] and K = 0. We will get cumulative sums as [1, 3, 6, 10]. For this, there is no value minus K can bee seen before! So, we will have to keep each of them in the map and occupy space equals to the array size n = 4.

Approach – 2 : C++ Code

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int cumulative_sum = 0;
        int total_sub_arrays = 0;
        map<int, int> map_seen_before;
        map_seen_before[0] = 1;
        
        for(int i = 0; i < nums.size(); i++){
            
            cumulative_sum += nums[i];
            
            if(map_seen_before.find(cumulative_sum - k) != map_seen_before.end())
                /*
                when we found this value is seen before, we are adding in our answer
                the frequency i.e. how many times that value was seen before.
                */
                total_sub_arrays += map_seen_before[cumulative_sum - k];
            
            if(map_seen_before.find(cumulative_sum) == map_seen_before.end())
                map_seen_before[cumulative_sum] = 1;
            else
                map_seen_before[cumulative_sum] += 1;
        }
        
        return total_sub_arrays;
    }
};

Approach – 2 : Java Code

class Solution {
    public int subarraySum(int[] nums, int k) {
        int cumulative_sum = 0;
        int total_sub_arrays = 0;
        HashMap<Integer, Integer> map_seen_before = new HashMap<> ();
        map_seen_before.put(0, 1);
        
        for(int i = 0; i < nums.length; i++){
            
            cumulative_sum += nums[i];
            
            if(map_seen_before.containsKey(cumulative_sum - k))
                /*
                when we found this value is seen before, we are adding in our answer
                the frequency i.e. how many times that value was seen before.
                */
                total_sub_arrays += map_seen_before.get(cumulative_sum - k);
            
            map_seen_before.put(cumulative_sum, map_seen_before.getOrDefault(cumulative_sum, 0) + 1);
        }
        
        return total_sub_arrays;
        
    }
}

Approach – 2 : Python Code

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        cumulative_sum = 0;
        total_sub_arrays = 0;
        map_seen_before = { };
        map_seen_before[0] = 1;
        
        for num in nums:
            cumulative_sum += num;
            
            if cumulative_sum - k in map_seen_before:
                #when we found this value is seen before, we are adding in our answer
                #the frequency i.e. how many times that value was seen before.
                total_sub_arrays += map_seen_before[cumulative_sum - k];
            
            if cumulative_sum not in map_seen_before:
                map_seen_before[cumulative_sum] = 1;
            else:
                map_seen_before[cumulative_sum] += 1;
        
        return total_sub_arrays;

Similar problems you should try out

Subarray Product Less Than K

Maximum Size Subarray Sum Equals k

Subarray Product Less than K

Continuous Subarray Sum

Subarray Sums Divisible by K

Minimum Operations to Reduce X to Zero

K Radius Subarray Averages

Find Pivot Index

Moving Average from Data Stream

Conclusion

Hope you enjoyed this post. Please write your comment if you found any issue in any of this part. Also, visit our homepage to find other articles.

Oh and another point, if you want solution of a specific problem which is giving you hard time, please write down the problem name or link below so that we can work on it for you!

Happy coding! 🙂