Skip to main content

29. Subarray Sum Equals K

mediumAsked at Doordash

Count contiguous subarrays whose values sum to a target — Doordash applies this prefix-sum hash-map technique to detect delivery batches that hit an exact revenue threshold in a stream of order values.

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

Problem

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

Constraints

  • 1 <= nums.length <= 2 * 10^4
  • -1000 <= nums[i] <= 1000
  • -10^7 <= k <= 10^7
  • Array can contain negative numbers

Examples

Example 1

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

Explanation: Subarrays [1,1] at indices [0,1] and [1,2] each sum to 2.

Example 2

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

Explanation: [1,2] and [3] both equal 3.

Approaches

1. Brute force O(n^2)

For every pair (i, j), compute sum of nums[i..j] directly; increment count when sum equals k.

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

Tradeoff:

2. Prefix sum with hash map

Maintain a running prefix sum and a frequency map of past prefix sums. For each position, check if (prefixSum - k) exists in the map — that means a subarray ending here sums to k.

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

Tradeoff:

Doordash-specific tips

Doordash poses this as: 'given a stream of order GMVs, count windows where total GMV equals exactly k dollars.' The prefix-sum trick is elegant but the negative-value edge case (standard sliding-window breaks) is a deliberate trap — call it out immediately. Initializing the map with {0: 1} (empty prefix sum seen once) is the insight that prevents off-by-one errors. They'll follow up: 'what if k is a range [lo, hi]?' — answer is two calls of this function subtracted.

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

Practice these live with InterviewChamp.AI →