Subarray Sum Equals K, applying Math.
Tags: javascript, algorithms, career, interview
Published: 2020-04-11 13:18:54

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/

<h2>Brute Force: O(n^2)</h2>

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.

```javascript
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.

<img src="https://media.giphy.com/media/777Aby0ZetYE8/giphy.gif"/>

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 
<strong>A[i..j] = A[0,j] - A[0,i-1]</strong>

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 :

<strong> SUM[i..j] = SUM[0..j] - SUM[0..i-1] = K </strong>

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 <strong>i</strong> so that at index <strong>j</strong>, if the above <strong>equation</strong> is satisfied, we can incerement the count. 

<strong>But</strong> we've to take one more case into consideration. 

```javascript
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 

<img src = "https://media.giphy.com/media/xL7PDV9frcudO/giphy.gif" /> 

<h2> Let's break it Down </h2>
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 <strong>5</strong>, we say ok cool. and save it in a container. 

Step 3> While adding the elements in our sum, we came across <strong>7</strong>, 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 <strong>5</strong> now, let's store it.

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

So we need a way, to 
1> Map <strong>5</strong> 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:
```javascript
hashtable : { 5, 2}
```

Let's code it : 

```javascript

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.

github: https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/MaximumSumSubarrayofSizeK.js