Problem

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

Examples

Example 1:

1
2

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

Example 2:

1
2

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

Solution

Let’s take an example not given in the question by taking negative numbers

1
2
3


Input: nums[]=[-1, -1, 1]  && k = 0
Output: 1

So, the answer should be ‘1’ as their is only one subarray whose sum is 0 i.e (-1 + 1)

Method 1 - Brute Force

  • Since we are very obedient person and don’t want to do anything extra from our side.
  • So, we will try to generate the sum of each subarray and if matches withk , then increment our answer.
  • Like, this is the most basic thing we can do.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

public int subarraySum(int[] nums, int k) {
	int n = nums.length;
	int ans = 0;

	for (int i = 0; i < nums.length; i++) {
		int sum = arr[i];
		// if element itself equal to k, then also increment count
		if(sum == k) {
            ans++;
        }
        for (int j = 0; j < n; i++) {
	        sum += arr[j]; // add elements with sum
	        // if at any point they become equal to k
			if(sum == k) {
	            ans++;
	        }
        }
        return ans;
	}
}

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(1)

Method 2 - Using Prefix Sum but Still Naive

  • Calculate the prefix sum of the array.
  • Now loop over the array in a nested way, prefix[j] - prefix[i] is equal to k. Increment our count: For eg. consider the array [1, 2, 3, 4, 5] and k=9, we have below prefix sum.
1
2
3
4

index :   0, 1, 2, 3,  4
  arr[]: [1, 2, 3, 4,  5]
prefix[]:[1, 3, 6, 10, 15]
          ↑         ↑

We see index 0 and index 3 has difference of k. Likewise index 2 and index 4 have difference k. That is our answer:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

public int subarraySum(int[] nums, int k) {
	int ans = 0;
	
	int[] prefix = new int[nums.length];
	prefix[0] = nums[0];
	for (int i = 1; i < nums.length; i++) {
		prefix[i] = prefix[i-1] + nums[i];
	}
	if(nums[0] == k){
		ans++;
	}
	for (int i = 0; i < nums.length; i++) {
		for (int j = 0; j < i; j++){
			if(prefix[i] - prefix[j] == k){
				ans++;
			}
		}
        return ans;
	}
}

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(n)

So, now we use map.

Method 3 - Using Prefix Sum with Map

  • Instead of traversing the whole array every time, can we able to store prefix sum already and then check with that.
  • So, with the help of an unordered map, we will store sum.

Intuition Before Code

So, suppose we have an array as arr[]: [1,2,3,4,5] and k = 9 Our answer will be ‘2’ i.e (2 + 3 + 4 and 4 + 5)

Now, if we store our prefix sum array then it should looks like:

1
2
3
4

index :   0, 1, 2, 3,  4
  arr[]: [1, 2, 3, 4,  5]
prefix[]:[1, 3, 6, 10, 15]
          ↑         ↑

How, we will find our subarray (2 + 3 + 4) using prefix sum, see:

  1. Look at prefix sum array. Index 0 and 3. Prefix sum at index 0 is 1 and index 3 is 10.
  2. Now question - How much prefix sum increased from index 0 to 3? Ans - Difference between 2 sums at index 0 and 3, i.e. (10-1) = 9.
  3. If (10 - 1) sum increases from index 0 to 3, then we can say that, ok, this difference, should be the sum of elements greater than index 0, and upto index 3, i.e from index 1 to index 3,right.
  4. Now, if we will see then we find out (10 - 1) is nothing but our ‘k’ that is 9.
  5. Why use map? So, we find out, that a subarray may also exist if this particular condition satisified, i.e (prefix[i] - k) should exist in our map, How? see, If prefix[i] - prefix[j] = k where i > j (i, j any index, in our case they are i = 3, j = 0) prefix[i] - k = prefix[j] , (simple maths) i.e if we are able to find (prefix[i] - k) is exist in our map, i.e prefix[j] so, we can say that from index j + 1 to i, the sum of the elements is k, right na, hence it proves that their exist an subarray from index j + 1 to i whose sum is k.

Now, for subarray (4 + 5) we again find this valid see -

1
2
3
4

index :   0, 1, 2, 3,  4
  arr[]: [1, 2, 3, 4,  5]
prefix[]:[1, 3, 6, 10, 15]
                ↑       ↑

  1. if we see our prefix sum at index 4 then it is 15 and also prefix sum at index 2 is 6. So, we can say that from index 2 to 4 our prefix sum increases from 6 to 15, right,

  2. So on putting a question, HOW MUCH ? means how much our sum increase from index 2 to index 4. Answer is 15-6=9, which is equal to k.

  3. So, we find out, that a subarray may also exist if this particular condition satisified, i.e (prefix[i] - k) should exist in our map, right na,

    How? see,

    If prefix[i] - prefix[j] = k where i > j (i, j any index, in our case they are i = 4, j = 2) prefix[i] - k = prefix[j] na, (simple maths)

    i.e if we are able to find (prefix[i] - k) is exist in our map, i.e prefix[j] so, we can say that from index j + 1 to i, the sum of the elements is k, right na, hence it proves that their exist an subarray from index j + 1 to i whose sum is k.

    I hope u got the reason now, why we will do (prefix[i] - k) in our code.

In the code below, we are not using prefix array, but sum variable, which stores current prefix value. And then we are saving it in the hashmap, instead of array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

public int subarraySum(int[] nums, int k) {
	int count =0;
	
	HashMap<Integer, Integer> map = new HashMap<>();
	map.put(0,1);
	int sum =0;
	
	for( int a: nums ){
		sum += a;

		if(map.containsKey(sum- k) ){
			count += map.get(sum- k);
		}
		map.put(sum, map.getOrDefault(sum,0) + 1);
	}
	return count;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)