DSA AnimatorDSA animations
Subarray Sum Equals K LC #560 Medium Prefix Sum
Problem

Given an array of integers nums and an integer k, return the number of subarrays whose sum equals k.

Example 1
Input: nums = [1,1,1], k = 2
Output: 2
Explanation: Subarrays [1,1] at indices [0..1] and [1..2] both sum to 2.
Constraints: 1 ≤ nums.length ≤ 2×10⁴  |  −1000 ≤ nums[i] ≤ 1000  |  −10⁷ ≤ k ≤ 10⁷
Try Examples
Custom:
Approach
Prefix Sum + HashMap
Track running prefix sum. At each index i, any subarray [j..i] that sums to k means prefixSum[i] - prefixSum[j-1] = k, i.e. prefixSum[j-1] = prefixSum[i] - k. The map counts how many times each prefix sum has appeared — O(n).
Arrays
Input: nums[] — current index highlighted
Prefix sums — cumulative sum at each position
HashMap: prefixSum → count
Variables
index i
—
prefixSum
—
k
—
count
—
Step Logic
Press ▶ Play or Next Step to begin.
🎉
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Initialize map={0:1}, sum=0, count=0 (base case: empty prefix)
2
For each n: sum += n (update running prefix sum)
3
count += map[sum−k] — subarrays ending here that sum to k
4
map[sum]++ — record this prefix sum, return count
Time
O(n)
Space
O(n)
Why It Works

If prefixSum[i] - prefixSum[j-1] = k, then the subarray from index j to i sums to k. Rearranging: prefixSum[j-1] = prefixSum[i] - k. By storing all previous prefix sums in a HashMap, we can check in O(1) how many valid starting points exist for each ending index. The base case map.put(0, 1) handles subarrays starting at index 0.

How to solve Subarray Sum Equals K

LeetCode 560 · Medium · Arrays · Pattern: Prefix Sum + Hash Map

Why the obvious approach is slow

Checking every subarray is O(n²). And with negatives, growing or shrinking a window tells you nothing.

The key idea

Use prefix sums. If the running sum now is S, and some earlier prefix was S minus k, the part between them sums to k. So a hash map counts how often each prefix sum has appeared.

Remember

A subarray sum is a difference of two prefix sums. Count earlier prefixes equal to sum minus k with a hash map.

Run the animation above on your own input, or watch the 1:18 video explanation of Subarray Sum Equals K with a dry run and Java code.

More Arrays problems