# Subarray Sum Equals K, applying Math.

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,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.