DEV Community

ZeeshanAli-0704
ZeeshanAli-0704

Posted on • Updated on

Smallest Contiguous Subarray Sum Equals K

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;
};
Enter fullscreen mode Exit fullscreen mode

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;
};
Enter fullscreen mode Exit fullscreen mode

Top comments (0)