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] [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.

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