Skip to main content

560. Subarray Sum Equals K

mediumAsked at Pinterest

Subarray Sum Equals K is Pinterest's prefix-sum classic: given an array and an integer k, count the contiguous subarrays whose sum equals k. The interviewer wants the prefix-sum + hash-map count pattern that handles negative numbers correctly.

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

Source citations

Public interview reports confirming this problem appears in Pinterest loops.

  • Glassdoor (2026-Q1)— Pinterest SWE onsite reports list this as the prefix-sum round on array problems.
  • LeetCode Pinterest tag (2026-Q1)— On the Pinterest company-tagged problem list.

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

Example 2

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

Approaches

1. Brute force: every subarray

Two nested loops; for each start i, accumulate sum and increment counter when it equals k.

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 += 1;
    }
  }
  return count;
}

Tradeoff: n=20000 means 4*10^8 ops — borderline TLE. Anchor with this, then move to prefix sums.

2. Prefix sum + hash map (optimal)

Walk left to right tracking running prefix sum. For each i, the number of subarrays ending at i with sum k equals the count of prior prefix sums equal to (currentPrefix - k). Use a Map<prefix, count> and increment as you go.

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

Tradeoff: O(n) single pass. The key insight: sum(i..j) = prefix[j] - prefix[i-1]; for it to equal k we need prefix[i-1] = prefix[j] - k. The Map counts how many such prior prefixes we've seen. Initialize with {0: 1} so subarrays starting from index 0 are counted.

Pinterest-specific tips

Pinterest interviewers love this problem because the sliding-window pattern DOES NOT work — negative numbers break the monotonicity sliding window relies on. Volunteer this distinction unprompted: 'sliding window assumes the sum is monotonic in window size, which fails with negative numbers. Prefix-sum + hash-map sidesteps that.' That's the senior signal.

Common mistakes

  • Trying sliding window — fails on negative numbers like [1, -1, 1, -1, 1] with k=0.
  • Forgetting to seed counts.set(0, 1) — misses subarrays that start at index 0.
  • Updating counts BEFORE reading — overcounts by 1 when sum == k (the empty prefix matches itself).
  • Returning the subarrays themselves instead of just the count — the problem asks for the count.

Follow-up questions

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

  • Continuous Subarray Sum (LeetCode 523) — subarray sum is a multiple of k.
  • Subarray Sums Divisible by K (LeetCode 974).
  • Return the actual subarrays, not just the count.
  • Maximum Size Subarray Sum Equals k (LeetCode 325).

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?

Sliding window requires that growing the window monotonically changes the sum (always increases or always decreases). With negative numbers, growing the window can decrease the sum, so 'shrink left when sum > k' fails.

Why does Pinterest care about this specific problem?

Prefix-sum + hash-map is a universal pattern for 'count contiguous things matching a property'. Pinterest interviewers use this as a litmus test for whether candidates know the pattern beyond the easier Maximum Subarray.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →