Skip to main content

19. Subarray Sum Equals K

mediumAsked at Confluent

Count contiguous subarrays summing to k — Confluent uses it because the prefix-sum hash trick is the same shape as counting offset windows that hit a target inside a Kafka log.

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

Problem

Given an integer array nums and an integer k, return the total number of contiguous subarrays whose elements sum to k. Arrays can contain negatives.

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. Two nested loops

Try every start, accumulate the sum, increment count when sum hits k.

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

Tradeoff:

2. Prefix sum hash map

Walk once tracking running prefix sum. For each prefix, the number of previous prefixes equal to (prefix - k) gives the number of valid subarrays ending here.

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

Tradeoff:

Confluent-specific tips

Confluent loves when you frame prefix-sum maps as partition-local state — call out that exactly-once semantics require the running prefix and its map be checkpointed before emitting the count downstream.

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 Confluent interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →