Skip to main content

15. Subarray Sum Equals K

mediumAsked at Rappi

Count contiguous subarrays summing to k — Rappi frames this as counting time-windows where cumulative delivery revenue exactly matches a guaranteed payout.

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. Brute pair sums

Sum every subarray (i,j) directly.

Time
O(n^2)
Space
O(1)
let cnt = 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) cnt++; }
}
return cnt;

Tradeoff:

2. Prefix-sum hash map

Track running prefix sums in a map; the count of subarrays ending at i with sum k is the number of prior prefixes equal to prefix - k.

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

Tradeoff:

Rappi-specific tips

Rappi expects the prefix-sum + hash-map trick — their settlement service uses exactly this shape to count payout-matching windows across courier shift logs.

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

Practice these live with InterviewChamp.AI →