Skip to main content

560. Subarray Sum Equals K

mediumAsked at Meta

Given an integer array and integer k, return the count of contiguous subarrays whose sum equals k. Meta asks this to test whether you reach for the prefix-sum + hash map pattern and articulate the 'count[prefixSum - k]' trick.

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

Source citations

Public interview reports confirming this problem appears in Meta loops.

  • Glassdoor (2026-Q1)— Meta E4 onsite reports cite this as the prefix-sum staple.
  • Blind (2025-11)— Recurring Meta interview problem.

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 prefix sums

Build prefix sums. For each (i, j), check whether prefix[j] - prefix[i] === k.

Time
O(n^2)
Space
O(n)
function subarraySumBrute(nums, k) {
  const prefix = [0];
  for (const x of nums) prefix.push(prefix[prefix.length - 1] + x);
  let count = 0;
  for (let i = 0; i < prefix.length; i++) {
    for (let j = i + 1; j < prefix.length; j++) {
      if (prefix[j] - prefix[i] === k) count++;
    }
  }
  return count;
}

Tradeoff: Quadratic — TLE at the upper bound. Mention to anchor.

2. Prefix sums + hash map (optimal)

Walk the array tracking running sum. For each position, check how many earlier prefix sums equal running - k. Increment count by that lookup.

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

Tradeoff: Linear. The trick: any subarray nums[i..j] with sum k corresponds to two prefix sums whose difference is k. Tracking the COUNT of each prefix sum lets us add multiple matches per position.

Meta-specific tips

Meta interviewers want the prefix-sum + hash map trick articulated. State out loud: 'The sum of nums[i..j] is prefix[j+1] - prefix[i]. So a subarray summing to k corresponds to finding an earlier prefix that differs from the current by exactly k.' That framing makes the hash map natural.

Common mistakes

  • Forgetting counts[0] = 1 (the empty prefix sum) — misses subarrays starting at index 0.
  • Updating the hash AFTER lookup but using AND in the same step — the order matters: lookup first, then add.
  • Treating the problem as 'subarrays with sum at most k' — different problem class (sliding window doesn't work with negatives).

Follow-up questions

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

  • Continuous Subarray Sum (LC 523) — divisibility variant.
  • Subarray Product Less Than K (LC 713) — uses sliding window (works because all positive).
  • What if the array were sorted (different optimal approach)?

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 does sliding window NOT work here?

Sliding window requires monotonic behavior — when we shrink the window, the sum decreases. With negatives, that doesn't hold, so sliding window fails.

Why count occurrences instead of just tracking presence?

Multiple earlier positions can have the same prefix sum. Each one contributes a valid subarray ending at the current position.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →