Skip to main content

560. Subarray Sum Equals K

mediumAsked at Shopify

Shopify uses this to grade whether you recognize prefix-sum + hash-map as one pattern. Real-life mirror: 'count promotion windows whose cumulative revenue equals exactly K dollars'. The interviewer wants the O(n) hashmap version, not the O(n^2) two-loop.

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

Source citations

Public interview reports confirming this problem appears in Shopify loops.

  • Glassdoor (2026-Q1)— Shopify Senior Backend onsites include Subarray Sum Equals K with explicit emphasis on handling negative numbers.
  • Reddit r/cscareerquestions (2025-11)— Shopify new-grad reports cite this as a medium hashmap round.

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: Two subarrays: [1,1] starting at index 0 and [1,1] starting at index 1.

Example 2

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

Approaches

1. Brute-force enumerate all subarrays

For each (i, j), sum nums[i..j] and check.

Time
O(n^3)
Space
O(1)
function subarraySumBrute(nums, k) {
  let count = 0;
  for (let i = 0; i < nums.length; i++) {
    for (let j = i; j < nums.length; j++) {
      let s = 0;
      for (let l = i; l <= j; l++) s += nums[l];
      if (s === k) count++;
    }
  }
  return count;
}

Tradeoff: Cubic. n = 20000 means 8 * 10^12 ops — won't finish. Mention it; ditch it.

2. Cumulative sum, O(n^2)

Precompute prefix sums; for each (i, j) compute the subarray sum in O(1).

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

Tradeoff: n^2 = 4 * 10^8 — borderline. Same logic as the optimal but missing the hash insight. Useful to verbalize before the optimal.

3. Prefix sum + hash map (optimal)

Walk the array maintaining a running prefix sum. For each new prefix p, the number of subarrays ending here with sum k equals the count of (p - k) already in the map. Increment the map entry for p.

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

Tradeoff: Single pass. The key insight: a subarray with sum k ending at index i exists iff there's some earlier prefix p_j with p_i - p_j = k, i.e. p_j = p_i - k. Counting matches in the map gives the answer. The map seed counts.set(0, 1) is crucial — without it, subarrays starting from index 0 are missed.

Shopify-specific tips

Shopify will hint 'the array can contain negatives, so sliding window doesn't work directly'. That's the cue for prefix-sum + hash map. Without that hint, candidates often reach for sliding window and get stuck. Volunteer 'sliding window fails because negatives can make a too-large window suddenly correct again' BEFORE coding.

Common mistakes

  • Reaching for sliding window without thinking about negatives.
  • Forgetting the counts.set(0, 1) seed — undercounts subarrays whose prefix equals exactly k.
  • Using a Set instead of a Map — you need COUNTS of each prefix, not just presence (e.g. nums = [1,-1,1,-1,1] with k=0 has the same prefix value many times).
  • Updating the map BEFORE checking it — would count the empty subarray ending at current index.

Follow-up questions

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

  • Subarray Sum Equals K with at most one element negated.
  • Continuous Subarray Sum divisible by K (LeetCode 523).
  • Longest Subarray with sum K — track first index per prefix, not count.
  • Maximum number of non-overlapping subarrays with sum K.
  • 2D version: count submatrices with sum 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?

Sliding window requires monotonicity — expanding the window strictly increases (or decreases) the sum. Negatives break that: a window that's already too large can become valid again by including a negative number. Prefix-sum + hash sidesteps the issue.

Why seed counts with {0: 1}?

It represents the empty prefix before index 0. Without it, a subarray starting at index 0 whose sum equals k wouldn't match anything in the map. The seed lets the algorithm count those cleanly.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →