Skip to main content

560. Subarray Sum Equals K

mediumAsked at Twilio

Subarray Sum Equals K is Twilio's prefix-sum probe: given an integer array and target k, count the contiguous subarrays whose sum equals k. The grading rubric weighs whether you reach for the prefix-sum-plus-hash-map trick to drop from O(n^2) to O(n), and articulate why two equal prefix sums imply a zero-sum subarray.

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

Source citations

Public interview reports confirming this problem appears in Twilio loops.

  • Glassdoor (2026-Q1)— Reported in Twilio backend SWE on-site rounds, often after a sorted-array two-pointer warm-up.
  • LeetCode Discuss (2025-12)— Listed in Twilio interview reports as a 'cleverness test' for the prefix-sum pattern.

Problem

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals k. A subarray is a contiguous non-empty sequence of elements within an array.

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

Explanation: Subarrays [1,1] (positions 0-1) and [1,1] (positions 1-2).

Example 2

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

Explanation: Subarrays [1,2] and [3].

Approaches

1. Brute-force double loop

For every starting index i, accumulate sums incrementally as j moves right.

Time
O(n^2)
Space
O(1)
function subarraySumBrute(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: At n = 2 * 10^4 that's 4 * 10^8 ops — borderline. Twilio's bar is that you propose this then immediately reach for the prefix-sum trick.

2. Prefix sum + hash map (optimal)

Maintain running prefix sum. Count occurrences of each prefix sum seen so far. For each new running sum, add count[runningSum - k] to the answer.

Time
O(n)
Space
O(n)
function subarraySum(nums, k) {
  const counts = new Map();
  counts.set(0, 1); // empty prefix has sum 0
  let sum = 0, result = 0;
  for (const n of nums) {
    sum += n;
    if (counts.has(sum - k)) result += counts.get(sum - k);
    counts.set(sum, (counts.get(sum) || 0) + 1);
  }
  return result;
}

Tradeoff: Single pass. The insight: if running sum at index j is S and we want a subarray ending at j summing to k, the starting index i must have prefix sum S - k. Counting all prior occurrences of S - k gives all valid (i, j) pairs ending at j.

Twilio-specific tips

Twilio's bar on Subarray Sum Equals K is the prefix-sum insight. Walk through the proof out loud: 'sum(i..j) = prefix(j) - prefix(i-1), so if we want sum(i..j) = k, we need prefix(i-1) = prefix(j) - k. So counting prior prefix sums equal to (current - k) gives the answer for this endpoint.' Forgetting to seed counts.set(0, 1) is the most common bug — it handles the case where the prefix itself equals k.

Common mistakes

  • Forgetting to seed `counts.set(0, 1)` — misses subarrays starting from index 0 whose entire prefix equals k.
  • Inserting `sum` into the map BEFORE checking — accidentally counts the empty subarray ending at j with itself.
  • Trying to use a sliding window — sliding window doesn't work because nums can have negative values.

Follow-up questions

An interviewer at Twilio may pivot to one of these next:

  • What if nums was guaranteed to be all positive? (Sliding window in O(n), O(1) space — strict less-than makes it work.)
  • Return the actual subarray indices, not just count. (Same hash map but store the prior INDEX of each prefix sum; pick any matching pair.)
  • What if you wanted subarrays with sum divisible by K (LC 974)? (Same trick on `(prefix % k + k) % k`.)

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why doesn't sliding window work here?

Because the array can contain negative numbers. Sliding window requires that extending the window monotonically changes the running sum — adding a negative can cause sum to go down, breaking the 'shrink from the left until sum <= k' invariant.

Why is `counts.set(0, 1)` necessary?

Because the running prefix sum at index j INCLUDES nums[0..j]. To count a subarray that starts at index 0 and sums to k, we need to match running sum k against prior prefix 0 — and the only way to do that is to seed prefix 0 with count 1 (representing the empty prefix before index 0).

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →