Skip to main content

20. Subarray Sum Equals K

mediumAsked at Intuit

Given an integer array and an integer k, return the number of contiguous subarrays whose sum equals k. Intuit asks this to test the prefix-sum + hash-map pattern and to reframe it as 'count ledger windows that reconcile to a target balance.'

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

Source citations

Public interview reports confirming this problem appears in Intuit loops.

  • Glassdoor (2026-Q1)— Intuit SWE II onsite — prefix-sum hash variant under the 'ledger reconciliation window' framing.
  • LeetCode Discuss (2025-12)— QuickBooks engineer cited Subarray Sum K as the hash-prefix bellwether 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

Explanation: Subarrays [1,1] starting at index 0 and at index 1.

Example 2

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

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

Approaches

1. Brute force all subarrays

For every (i, j) pair, sum nums[i..j] and check if it 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: Quadratic — fine to mention, then propose the prefix-sum optimization.

2. Prefix sum + hash count (optimal)

Maintain running prefix sum. At each index, the number of valid subarrays ending here = number of previous prefix sums equal to (current - k). Hash counts of prefix sums seen.

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

Tradeoff: Linear time, linear space. The 0-prefix seed handles subarrays starting at index 0.

Intuit-specific tips

Intuit reframes this as 'how many account-statement windows reconcile to k cents?' — same algorithm, integer-cent inputs. They grade for whether you seed the hash with counts.set(0, 1) (a common missing piece). Bonus signal: discuss why sliding-window won't work here (negatives break the monotonic-sum invariant) and that this generalizes to subarray sum divisible by k (LC 974).

Common mistakes

  • Forgetting to seed counts.set(0, 1) — misses subarrays that start at index 0.
  • Trying to use a sliding window with negative numbers — fails because removing a negative can increase the sum.
  • Using floats for nums when the problem implies money — accumulates drift over long ledgers.

Follow-up questions

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

  • Subarray Sum Divisible by K (LC 974).
  • Continuous Subarray Sum — find any sub-array whose sum is a multiple of k (LC 523).
  • Maximum Size Subarray Sum Equals K (LC 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 a sliding window work here?

Sliding window assumes growing the window only increases the sum (or shrinking only decreases). With negative numbers in nums, that invariant breaks — adding a negative can decrease the sum. Prefix-sum + hash is the correct tool.

How does this map to ledger reconciliation?

Treat each transaction as a value. The 'window sum' is the net change between two timestamps. Counting windows equal to k = counting time-spans where the account moved exactly k cents — useful for finding offsetting entries.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →