Skip to main content

20. Subarray Sum Equals K

mediumAsked at Redis

Count the number of contiguous subarrays that sum to k; Redis uses it to test prefix-sum + hashmap intuition, the same trick that powers GETSET cumulative counters.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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

Constraints

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

Examples

Example 1

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

Example 2

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

Approaches

1. Nested sum

Enumerate every (i, j) subarray; add nums[j] to running sum and compare.

Time
O(n^2)
Space
O(1)
let count = 0;
for (let i = 0; i < nums.length; i++) {
  let s = 0;
  for (let j = i; j < nums.length; j++) {
    s += nums[j];
    if (s === k) count++;
  }
}
return count;

Tradeoff:

2. Prefix sum + hash map

Walk once with running sum S; for each S add seen[S - k] to count, then bump seen[S]. Maps onto how Redis HINCRBY-based counters answer range-sum queries via cumulative deltas.

Time
O(n)
Space
O(n)
function subarraySum(nums, k) {
  const seen = new Map();
  seen.set(0, 1);
  let sum = 0, count = 0;
  for (const n of nums) {
    sum += n;
    count += seen.get(sum - k) || 0;
    seen.set(sum, (seen.get(sum) || 0) + 1);
  }
  return count;
}

Tradeoff:

Redis-specific tips

Redis interviewers like to hear how you'd persist the running prefix-sum hash to a Redis HASH so multiple stream consumers can answer the same range-count without re-scanning.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Subarray Sum Equals K and other Redis interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →