Honestly guys, this question will elevate your Math thinking.

Question: Given an unsorted array of integers, find the number of subarrays having sum exactly equal to a given number k.

Eg: If the given array : [5,2,7,9,10,-4,5,7,0,4,3,6] and K = 7 output = 6

Subarrays are : [5,2] [7] [7] [7,0] [0,4,3] [4,3]

First try it yourself: https://leetcode.com/problems/subarray-sum-equals-k/

## Brute Force: O(n^2)

The brute force approach would be to iterate over the array and generate all possible subarray and count the subarray's whose sum equals K.

```
var subarraySum = function(nums, k) {
let count = 0;
for(let i=0;i<nums.length;i++){
let sum = nums[i];
if(sum == k) count++;
for(let j=i+1;j<nums.length;j++){
sum+=nums[j];
if(sum == k) count++;
}
}
return count;
};
```

Now that you've got the gist of what the problem is asking us to do, let's optimize it.

We're being asked to count the number of subarray's whose sum = K;

Question > What's a subarray?

For a given Array A, where length of A = n, subarray would be A[i...j] where i>=0 and j < A.length;

So we're being asked to find such A[i..j] whose sum equals K.

Subarray A[i..j] can be written as

**A[i..j] = A[0,j] - A[0,i-1]**

which means SUM[i..j] = SUM[0,..j] - SUM[0...,i-1]

And since we want to count subarray's whose sum equals K this leads us to :

** SUM[i..j] = SUM[0..j] - SUM[0..i-1] = K **

To boil it down, for an arbitary array Arr and K = 2, the above expression can be visualized as :

Let SUM[0..j], ie sum of elements from Arr(0..j) = 7

Let SUM[0..i], ie sum of elements from Arr(0..i) = 5

Since i<=j and SUM[0..j] - SUM[0..i] = 7 - 5 = 2. We increment the count.

This leads to us to our second problem of storing the sum of elements till index **i** so that at index **j**, if the above **equation** is satisfied, we can incerement the count.

**But** we've to take one more case into consideration.

```
What if there are negative integers and we're faced with following situation:
For i < j < a < b
Let SUM[0..i] = 5,
Let SUM[0..j] = 7,
Let SUM[0..a] = 5,
Let SUM[0..b] = 7
Arr = [0,...............,5,........,7,......,5,.........,7,.............,n]
i j a b
This means that SUM[i..j] = 2 and SUM[a..b] = 2 and SUM[i..b] = 2.
```

You might be thinking

## Let's break it Down

Step 1> We keep on adding elements and we get a sum, let's call this "Presum" or prefix sum.

Step 2> Somewhere along the line while adding we came across **5**, we say ok cool. and save it in a container.

Step 3> While adding the elements in our sum, we came across **7**, and since 7 - 5 = 2 which equals K, We increment the count.

Step 4> We keep on adding elements, we come across 5 again. So we say, ok cool, I have 2 **5** now, let's store it.

Step 5> While adding we come across 7, and since 7 - 5 = 2, we incerement our count, **BUT** since we've seen **5 twice**, we increment count by 2.

So we need a way, to

1> Map **5** to till running frequency

2> Retrieves 5 in O(1) time.

The Data Structure which satisfies both is a HashTable, which will look something like:

```
hashtable : { 5, 2}
```

Let's code it :

```
var subarraySum = function(nums, k) {
let sum = 0
let count = 0
const map = new Map()
for (let i = 0; i < nums.length; i++){
if (!map.has(sum)){ //check if we've seen the "sum" before
map.set(sum, 1) // if not then add it to map
} else {
map.set(sum, map.get(sum) + 1) // if yes then increment it's count
}
sum += nums[i] // add the element
if (map.has(sum-k)){ // here we compute 7-2 = 5 since 7-2=5 <==> 7-5=2
count += map.get(sum-k) // add the count
}
}
return count
};
```

Now you know how to solve such complex math problems by observing it's patterns.

## Discussion (0)