Problem Statement #

Given an array of positive numbers and a positive number ‘S’, find the length of the smallest contiguous subarray whose sum is greater than or equal to ‘S’. Return 0, if no such subarray exists.

Example 1:

Input: [2, 1, 5, 2, 3, 2], S=7

Output: 2

Explanation: The smallest subarray with a sum great than or equal to '7' is [5, 2].

Subarray Sum Equals K - Brute Force Approach:

```
var subarraySum = function (nums, k) {
let n = nums.length;
let count = 0;
for (let i = 0; i < n; i++) {
let sum = 0;
for (let j = i; j < n; j++) {
// Calculate required sum
sum += nums[j];
// Check if sum is equal to
// required sum
if (sum == k) count++;
}
}
return count;
};
```

2) Using Map / HasMap:

Above logic works on principal of prefix sum array or cumulative sum array.

If SUM - K exist in hasMap that means somehow some combination of previous item can give us sum = k;

Equation will be like

currSum - k = Val (this val value is one which can be derived from previous combination)

```
var subarraySum = function (nums, k) {
const obj = {};
let res = 0;
let sum = 0;
for (let i = 0; i < nums.length; i++) {
sum += nums[i];
if (sum == k) res++;
if (obj[sum - k]) res += obj[sum - k];
obj[sum] ? (obj[sum] += 1) : (obj[sum] = 1);
}
return res;
};
```

## Top comments (0)