leetcode-javascript/solutions/0930-binary-subarrays-with-sum.js at development · Anuj9826/leetcode-javascript · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * Binary Subarrays With Sum
 * Time Complexity: O(N)
 * Space Complexity: O(1)
 */
var numSubarraysWithSum = function (nums, goal) {
  const countSubarraysWithAtMostSum = (inputArray, upperLimit) => {
    if (upperLimit < 0) {
      return 0;
    }

    let leftBoundary = 0;
    let currentWindowSum = 0;
    let cumulativeCount = 0;

    for (
      let rightBoundary = 0;
      rightBoundary < inputArray.length;
      rightBoundary++
    ) {
      currentWindowSum += inputArray[rightBoundary];

      while (currentWindowSum > upperLimit) {
        currentWindowSum -= inputArray[leftBoundary];
        leftBoundary++;
      }
      cumulativeCount += rightBoundary - leftBoundary + 1;
    }
    return cumulativeCount;
  };

  let totalSubarraysUpToGoal = countSubarraysWithAtMostSum(nums, goal);
  let totalSubarraysUpToGoalMinusOne = countSubarraysWithAtMostSum(
    nums,
    goal - 1,
  );

  return totalSubarraysUpToGoal - totalSubarraysUpToGoalMinusOne;
};