Subarray Sum Equals K LeetCode 560 Guide

LeetCode 560 gives you an integer array nums and an integer k and asks you to return the total number of contiguous subarrays whose elements sum to k. The subarrays must be contiguous — meaning the elements occupy consecutive positions in the array — but they can be any length from 1 to n. Crucially, the array can contain negative numbers, zero, and positive numbers in any order.

The brute-force solution uses two nested loops: the outer loop fixes the start index i, the inner loop fixes the end index j, and an innermost accumulation computes the sum of nums[i..j]. This gives O(n^2) or O(n^3) depending on whether you maintain a running sum. The problem expects an O(n) solution, which requires the prefix sum plus hashmap pattern — a fundamental algorithmic building block that appears across dozens of array and subarray problems.

Understanding why the O(n) solution works requires grasping the prefix sum relationship: the sum of a subarray from index i to j equals prefix[j+1] minus prefix[i], where prefix[x] is the sum of all elements from index 0 through x-1. If that difference equals k, then prefix[j+1] minus k equals prefix[i], meaning we need to count how many earlier prefix sums equal the current prefix sum minus k.

The sliding window technique works on subarray sum problems when the array contains only non-negative numbers. The logic relies on a simple monotonicity property: expanding the window by adding an element to the right always increases (or maintains) the sum, and shrinking the window by removing an element from the left always decreases (or maintains) the sum. This monotonicity allows you to make greedy decisions — if the current sum is too large, shrink from the left; if too small, expand to the right.

When negative numbers are present, this monotonicity completely breaks down. Adding a negative element to the right decreases the sum, and removing a negative element from the left increases the sum. A window that currently exceeds k might become valid if you expand further right and encounter a negative number, or it might never become valid regardless of how you shrink from the left. The sliding window has no way to know which direction to move without examining all possibilities, reducing it back to O(n^2) behavior in the worst case.

Consider the array [-1, 1, 2, -1, 1] with k=2. A sliding window that sees the sum exceed 2 at some point might shrink from the left and miss a valid subarray that required the negative element to balance a later positive. Sliding window is a powerful pattern but has a strict prerequisite: the values must be non-negative. When you see subarrays with negatives, immediately think prefix sum plus hashmap instead.

Define prefix[i] as the sum of the first i elements of nums: prefix[0] = 0, prefix[1] = nums[0], prefix[2] = nums[0] + nums[1], and so on. The sum of elements from index i to j (inclusive, 0-indexed) is exactly prefix[j+1] minus prefix[i]. This identity transforms the question "does this subarray sum to k?" into "does prefix[j+1] minus prefix[i] equal k?" — which rearranges to "does prefix[i] equal prefix[j+1] minus k?".

This rearrangement is the core insight. As you compute prefix sums left to right, for each new prefix sum p at position j+1, you want to count how many earlier prefix values equal p minus k. Each such earlier prefix value at position i corresponds to a valid subarray from index i to j that sums to k. Instead of checking all earlier positions (O(n) per position), you can look this count up in O(1) using a hashmap that stores the frequency of each prefix sum seen so far.

The prefix sum transforms a two-dimensional search (all pairs i, j) into a one-dimensional lookup: for each new prefix sum, do a single O(1) hashmap lookup for (prefixSum minus k) and add the result to the answer. The total work is O(n) for the single pass plus O(n) space for the hashmap. No nested loops required.

The algorithm maintains a hashmap (also called a frequency map or Counter) that maps each prefix sum seen so far to the number of times it has been seen. Initialize the map with {0: 1} before starting the loop — this accounts for the prefix sum of the empty prefix, which equals 0, and handles the case where a subarray starting from index 0 sums to k.

In the single pass loop, maintain a running prefix sum. Before updating the map, check if (prefixSum minus k) exists in the map and add its count to the answer. Then add or increment the current prefix sum in the map. The order matters: check first, then update. If you update first, a subarray of length 0 (the same index as both i and j) might be counted, which is incorrect.

After the loop, the answer contains the total count of subarrays that sum to k. The time complexity is O(n) for the single pass, with each step performing O(1) hashmap operations. The space complexity is O(n) in the worst case because the hashmap may store up to n+1 distinct prefix sums (one for each position plus the initial 0).

Trace through nums = [1, 2, 3, -1, 1] with k = 3. Start: prefixSum = 0, map = {0: 1}, count = 0. Index 0 (val=1): prefixSum = 1. Check map for 1-3 = -2: not found, add 0. Map: {0:1, 1:1}. Index 1 (val=2): prefixSum = 3. Check map for 3-3 = 0: found with count 1, so count = 1. Map: {0:1, 1:1, 3:1}. This corresponds to subarray [1, 2, 3] starting at index 0.

Index 2 (val=3): prefixSum = 6. Check map for 6-3 = 3: found with count 1, so count = 2. Map: {0:1, 1:1, 3:1, 6:1}. This corresponds to subarray [2, 3] from index 1 to 2 (prefix[3] - prefix[1] = 6 - 1... wait, that gives 5 — let me re-check: prefix at index 2 after consuming nums[2]=3 is 1+2+3=6; lookup 6-3=3 which is prefix after consuming [1,2], so subarray [3] alone? No — subarray nums[2..2] = [3] which sums to 3. Yes, that is correct.

Index 3 (val=-1): prefixSum = 5. Check map for 5-3 = 2: not found, add 0. Map: {0:1, 1:1, 3:1, 6:1, 5:1}. Index 4 (val=1): prefixSum = 6. Check map for 6-3 = 3: found with count 1, so count = 3. Map: {0:1, 1:1, 3:1, 6:2, 5:1}. This corresponds to subarray [-1, 1] from index 3 to 4 (prefix = 6 at end, prefix = 3 at index 2, difference = 3). Final answer: 3 subarrays — [1,2], wait let me state clearly: the three subarrays are [1,2] (sums to 3? no, 1+2=3 yes), [3] (sums to 3), and [3,-1,1] (sums to 3).

Python solution using collections.Counter (or a defaultdict): from collections import defaultdict. def subarraySum(nums, k): count = 0; prefixSum = 0; freq = defaultdict(int); freq[0] = 1; for n in nums: prefixSum += n; count += freq[prefixSum - k]; freq[prefixSum] += 1; return count. The defaultdict(int) returns 0 for missing keys automatically, so freq[prefixSum - k] safely returns 0 if not found. Eight lines including the import and function signature.

Java solution: public int subarraySum(int[] nums, int k) { int count = 0, prefixSum = 0; Map<Integer, Integer> freq = new HashMap<>(); freq.put(0, 1); for (int n : nums) { prefixSum += n; count += freq.getOrDefault(prefixSum - k, 0); freq.put(prefixSum, freq.getOrDefault(prefixSum, 0) + 1); } return count; }. The getOrDefault(key, 0) pattern handles missing keys cleanly without a null check. Time O(n), space O(n), ten lines of clean readable code.

Both solutions follow identical logic: initialize freq with {0:1}, accumulate prefix sums, look up (prefixSum - k) before updating the map, then increment the current prefix sum. The check-before-update order is critical — updating first would allow i == j (zero-length subarrays) to be counted. With this pattern, every subarray pair (i, j) where i < j is counted exactly once when j is processed.

The prefix sum plus hashmap pattern recurs across many medium and hard LeetCode problems. Continuous Subarray Sum (LeetCode 523) asks whether any subarray of length at least 2 has a sum that is a multiple of k — the trick is to store remainders (prefixSum mod k) in the map instead of raw prefix sums, and check if the same remainder was seen at least two indices ago. Path Sum III (LeetCode 437) extends the pattern to binary trees, using a DFS traversal and a hashmap of prefix sums along the current root-to-node path.

Product of Array Except Self (LeetCode 238) uses a related prefix product trick — computing prefix products from the left and suffix products from the right to avoid division. Maximum Subarray (LeetCode 53) is the simpler version of this problem family: instead of counting subarrays summing to k, find the maximum subarray sum, solvable with Kadane's O(n) algorithm which implicitly tracks a running prefix sum minimum. Both 53 and 560 share the "running accumulation over the array" motif.

The prefix sum pattern is a foundational building block in the subarray problem family. Once you internalize the identity sum(i,j) = prefix[j+1] - prefix[i] and the hashmap lookup trick, you can solve most subarray sum counting problems — with exact targets, divisibility conditions, or range constraints — all in O(n) time. It is one of the most high-leverage patterns to master for technical interviews at top companies.