Leetcode 560. Subarray Sum Equals K
Count the number of contiguous, non-empty subarrays whose elements sum to k. Because nums can include negatives (so two-pointer sliding window doesn't work), use cumulative prefix sums with a hash map of frequencies to count matching previous sums in O(n) time.
Asked at:
Meta
DESCRIPTION
Count the number of contiguous, non-empty subarrays whose elements sum to k. Because nums can include negatives (so two-pointer sliding window doesn't work), use cumulative prefix sums with a hash map of frequencies to count matching previous sums in O(n) time.
Input:
nums = [1, 1, 1], k = 2
Output:
2
Explanation: Two subarrays sum to 2: [1,1] from indices 0-1, and [1,1] from indices 1-2
Constraints:
- 1 <= nums.length <= 2 * 10^4
- -1000 <= nums[i] <= 1000
- -10^7 <= k <= 10^7
- Array can contain negative numbers, zero, and positive numbers
Understanding the Problem
Let's understand what we're being asked to do. We have an array like [1, 1, 1] and a target sum k = 2. We need to count how many contiguous subarrays sum to exactly 2.
Tracing through: subarray [1,1] (indices 0-1) sums to 2 ✓, subarray [1,1] (indices 1-2) also sums to 2 ✓. So the answer is 2.
Important constraint: The array can contain negative numbers, zero, and positive numbers. This means a subarray's sum can increase, decrease, or stay the same as we extend it!
Edge cases to consider: What if the entire array sums to k? What if k = 0 and we have zeros in the array? What if no subarray sums to k? What about subarrays of length 1?
Brute Force Approach
The brute force approach checks all possible subarrays explicitly using nested loops. For each starting index i, iterate through all ending indices j >= i, computing the sum of elements from i to j. If the sum equals k, increment the count. This approach is straightforward but inefficient because it recalculates overlapping sums repeatedly and doesn't leverage any mathematical properties of prefix sums.
def subarray_sum(nums, k):"""Count subarrays with sum equal to k using brute force.Check all possible contiguous subarrays explicitly."""count = 0n = len(nums)# Outer loop: iterate through all starting indicesfor i in range(n):current_sum = 0# Inner loop: iterate through all ending indices from ifor j in range(i, n):# Add current element to sumcurrent_sum += nums[j]# Check if sum equals kif current_sum == k:count += 1return count
Start brute force: check all subarrays
0 / 35
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(n²) We use nested loops to check all possible subarrays. For each of n starting positions, we potentially check n ending positions, leading to quadratic time complexity
Space Complexity: O(1) We only use a constant amount of extra space for the counter and loop variables, regardless of input size
Building Intuition
For any subarray from index i to j, its sum equals prefixSum[j] - prefixSum[i-1]. If this equals k, then prefixSum[j] - prefixSum[i-1] = k, which means prefixSum[i-1] = prefixSum[j] - k.
This transforms the problem: at each position j, we ask 'how many previous positions had a prefix sum of exactly currentSum - k?'
By tracking prefix sums in a hash map with their frequencies, we can instantly look up how many previous positions would form a valid subarray ending at the current position.
This avoids checking all possible subarrays explicitly, which would be O(n²). Instead, we process each element once while maintaining running counts.
Imagine you're tracking your bank balance day by day. If you want to know 'on which days did I earn exactly $100?', you'd look at balance differences.
If today's balance is $500 and you want to find days where you earned $100 since then, you'd look for previous days with balance $500 - $100 = $400. The number of such days is how many ways you earned exactly $100 ending today.
The hash map stores 'how many times have I seen each balance before?' so you can instantly count matching previous balances.
Common Mistakes
Optimal Solution
The optimal approach uses cumulative prefix sums with a hash map to count matching subarrays in a single pass. As we iterate through the array, we maintain a running sum and store the frequency of each prefix sum seen so far. At each position, we check if currentSum - k exists in the hash map - if it does, those previous positions form valid subarrays ending at the current position. This works because if prefixSum[j] - prefixSum[i] = k, then prefixSum[i] = prefixSum[j] - k. We initialize the hash map with {0: 1} to handle subarrays starting from index 0.
def subarray_sum(nums, k):"""Count subarrays with sum equal to k using prefix sums.Time: O(n), Space: O(n)"""# Hash map to store frequency of prefix sumsprefix_count = {0: 1}current_sum = 0count = 0# Iterate through arrayfor num in nums:# Update running sumcurrent_sum += num# Check if (current_sum - k) exists in map# If yes, those positions form valid subarraysif current_sum - k in prefix_count:count += prefix_count[current_sum - k]# Add current prefix sum to mapif current_sum in prefix_count:prefix_count[current_sum] += 1else:prefix_count[current_sum] = 1return count
Start subarray sum algorithm
0 / 13
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(n) We iterate through the array once, and each hash map lookup/insert operation is O(1) on average, resulting in linear time complexity
Space Complexity: O(n) In the worst case, all prefix sums are unique, requiring O(n) space to store them in the hash map
What We've Learned
- Prefix sum with hashmap pattern: When you need to find subarrays with a specific sum and the array contains negative numbers (ruling out sliding window), use cumulative prefix sums stored in a hashmap - if `prefixSum - k` exists in the map, you've found subarrays ending at the current index.
- Frequency map over boolean tracking: Store the count/frequency of each prefix sum rather than just checking existence - multiple occurrences of the same prefix sum mean multiple valid subarrays, so `count += map.get(prefixSum - k)` captures all possibilities in one lookup.
- Initialize with base case: Always seed your hashmap with `map.put(0, 1)` before iterating - this handles subarrays that start from index 0 where the prefix sum itself equals k, a critical edge case that's easy to miss.
- Single-pass O(n) transformation: By maintaining a running sum and looking backward via hashmap (instead of checking all subarray combinations), you convert an O(n²) brute force into O(n) time with O(n) space - the hashmap trades space for dramatic time savings.
- Subarray sum decomposition principle: The key insight is that `sum(i, j) = prefixSum[j] - prefixSum[i-1]`, so finding subarrays summing to k becomes finding pairs where `prefixSum[j] - prefixSum[i-1] = k`, which rearranges to looking up `prefixSum[j] - k` in your history.
- Range query optimization pattern: This prefix sum + hashmap technique extends to any problem asking about contiguous subarray properties (sum equals k, divisible by k, difference equals target) - whenever you see 'subarray' with a target condition, consider if prefix sums can transform it into a lookup problem.
Related Concepts and Problems to Practice
medium
This is the exact same problem as the one being analyzed. It uses prefix sums with a hashmap to count subarrays that sum to k in O(n) time, handling negative numbers where sliding window fails.
medium
This problem also uses prefix sum techniques to efficiently count elements across subarrays. While it counts vowels rather than sums, it reinforces the same pattern of using cumulative data to answer range queries efficiently.
Test Your Understanding
Why is hashmap the right data structure for this problem?
hashmap provides the optimal access pattern
It's the only data structure that works
It's the easiest to implement
It uses the least memory
Select an answer to see the explanation
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Mid November, 2025
Meta
Senior
Late October, 2025
Meta
Mid-level
Mid October, 2025
Meta
Senior
Comments
Hello Interview Premium
Your account is free and you can post anonymously if you choose.