# LeetCode - Subarray Sum Equals K

## Problem statement

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

A subarray is a contiguous non-empty sequence of elements within an array.

Problem statement taken from: https://leetcode.com/problems/subarray-sum-equals-k

Example 1:

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

Example 2:

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

Constraints:

``````- 1 <= nums.length <= 2 * 10^4
- -1000 <= nums[i] <= 1000
- -10^7 <= k <= 10^7
``````

### Explanation

#### Brute Force approach

The brute force approach is evaluate the sum of each subarray. If the sum equals `k`, we increment the subarray count by 1.

A C++ snippet of this approach is as follows:

``````int count = 0;

for (int i = 0; i < n; i++) {
int sum = 0;

for (int j = i; j < n; j++) {
sum += arr[j];

if (sum == k)
count++;
}
}

return count``````

The time complexity of the above approach is O(n^2). The space-complexity is O(1).

#### Efficient approach

The time complexity can be reduced to O(n), by using a HashMap. While traversing the array we store the sum so far in a variable currentSumTillNow. We maintain the different values of currentSumTillNow we encounter while traversing in a HashMap. If the value of the currentSumTillNow till now is equal to the sum at any instance we increment the count of the subarray by 1.

When the value of the currentSumTillNow exceeds the sum, we evaluate currentSumTillNow - sum. If this value is present in the HashMap, we exclude the number of subarrays we encountered previously. We increment the count of number of the subarrays by 1 even in the case when currentSumTillNow equals k.

Let's check the algorithm first.

#### Algorithm

``````- initialize map previousSum
set count = 0, currentSumTillNow = 0

- loop for i = 0; i < nums.size(); i++
- update currentSumTillNow = currentSumTillNow + nums[i]

- if currentSumTillNow == k
- update count = count + 1
- if end

- if previousSum.find(currentSumTillNow - k) != previousSum.end()
- count = count + previousSum[currentSumTillNow - k]
- if end

- update previousSum[currentSumTillNow] = previousSum[currentSumTillNow] + 1
- for end

- return count
``````

The time complexity of the above approach is O(n). We are using an additional space in form of HashMap, so the space complexity is O(n).

Let's check our algorithm in C++, Golang, and Javascript.

#### C++ solution

``````class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> previousSum;
int count = 0, currentSumTillNow = 0;

for(int i = 0; i < nums.size(); i++) {
currentSumTillNow += nums[i];

if(currentSumTillNow == k) {
count++;
}

if(previousSum.find(currentSumTillNow - k) != previousSum.end()) {
count += previousSum[currentSumTillNow - k];
}

previousSum[currentSumTillNow]++;
}

return count;
}
};``````

#### Golang solution

``````func subarraySum(nums []int, k int) int {
previousSum := make(map[int]int)
count, currentSumTillNow := 0, 0

for i := 0; i < len(nums); i++ {
currentSumTillNow += nums[i]

if currentSumTillNow == k {
count++
}

if previousSum[currentSumTillNow - k] > 0 {
count += previousSum[currentSumTillNow - k]
}

previousSum[currentSumTillNow]++
}

return count
}``````

#### JavaScript solution

``````var subarraySum = function(nums, k) {
let previousSum = new Map();
let count = 0, currentSumTillNow = 0;

for(let i = 0; i < nums.length; i++) {
currentSumTillNow += nums[i];

if(currentSumTillNow === k) {
count++;
}

if(previousSum.has(currentSumTillNow - k)) {
count += previousSum.get(currentSumTillNow - k);
}

let value = previousSum.get(currentSumTillNow);

if (value === null)
previousSum.set(currentSumTillNow, 1);
else
previousSum.set(currentSumTillNow, value + 1);
}

return count;
};``````

#### Dry Run

Let's dry-run our algorithm to see how the solution works.

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

Step 1: unordered_map<int, int> previousSum
count = 0, currentSumTillNow = 0

Step 2: loop for i = 0; i < nums.size()
0 < 3
true

currentSumTillNow = currentSumTillNow + nums[i]
= 0 + nums[0]
= 0 + 1
= 1

if currentSumTillNow == k
1 == 3
false

if previousSum.find(currentSumTillNow - k) != previousSum.end()
previousSum.find(1 - 3) != previousSum.end()
previousSum.find(-2) != previousSum.end()
false

previousSum[currentSumTillNow]++
previousSum[1]++
previousSum[1] = 1
previousSum = { 1: 1 }

i++
i = 1

Step 3: loop for i < nums.size()
1 < 3
true

currentSumTillNow = currentSumTillNow + nums[i]
= 1 + nums[1]
= 1 + 2
= 3

if currentSumTillNow == k
3 == 3
true

count = count + 1
= 0 + 1
= 1

if previousSum.find(currentSumTillNow - k) != previousSum.end()
previousSum.find(3 - 3) != previousSum.end()
previousSum.find(0) != previousSum.end()
false

previousSum[currentSumTillNow]++
previousSum[3]++
previousSum[3] = 1
previousSum = { 1: 1, 3: 1 }

i++
i = 2

Step 4: loop for i < nums.size()
2 < 3
true

currentSumTillNow = currentSumTillNow + nums[i]
= 3 + nums[2]
= 3 + 3
= 6

if currentSumTillNow == k
6 == 3
true

if previousSum.find(currentSumTillNow - k) != previousSum.end()
previousSum.find(6 - 3) != previousSum.end()
previousSum.find(3) != previousSum.end()
true

count = count + previousSum[currentSumTillNow - k]
= 1 + previousSum[6 - 3]
= 1 + 1
= 2

previousSum[currentSumTillNow]++
previousSum[6]++
previousSum[6] = 1
previousSum = { 1: 1, 3: 1, 6: 1}

i++
i = 3

Step 5: loop for i < nums.size()
3 < 3
false

Step 6: return count

We return the answer as 2.
``````