560. Subarray Sum Equals K
mediumAsked at ShopifyShopify 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 Sam K., 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
nums = [1,1,1], k = 22Explanation: Two subarrays: [1,1] starting at index 0 and [1,1] starting at index 1.
Example 2
nums = [1,2,3], k = 32Approaches
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.
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.