⚠️ This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#560) before relying on it.
Home → Algorithms → Subarray Sum Equals K

#️⃣ Subarray Sum Equals K

An interactive visualization of the prefix sum + hash map technique. Watch how we count subarrays summing to k in a single pass by tracking prefix sum frequencies.

Hash Map Prefix Sum LeetCode 560 ↗ Medium

The Problem

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

A subarray is a contiguous non-empty sequence of elements within an array.

Interactive Visualization

Speed:
Array & Prefix Sums
Prefix Sum Progression
Hash Map: prefix_sum → count
Prefix Sum Count
Status
Press Step or Play to begin.
Code
fun subarraySum(nums: IntArray, k: Int): Int {    var count = 0    var prefixSum = 0    val seen = mutableMapOf(0 to 1)  // empty prefix    for (num in nums) {        prefixSum += num        if (prefixSum - k in seen) {            count += seen[prefixSum - k]!!        }        seen[prefixSum] = (seen[prefixSum] ?: 0) + 1    }    return count}

How It Works

Key Insight

If we define prefix_sum[j] as the sum of elements from index 0 to j, then the sum of any subarray from index i+1 to j equals prefix_sum[j] - prefix_sum[i]. So if we want a subarray sum equal to k, we need:

prefix_sum[j] - prefix_sum[i] = k, which means prefix_sum[i] = prefix_sum[j] - k.

Instead of checking all previous prefix sums (which would be O(n²)), we store them in a hash map. At each index j, we look up how many times prefix_sum - k has appeared before — each occurrence represents a valid subarray ending at j.

The Algorithm

  • Initialize: count = 0, prefix_sum = 0, hash map seen = {0: 1} (the empty prefix has sum 0, seen once)
  • For each element: add it to prefix_sum
  • Lookup: check if prefix_sum - k exists in seen. If so, add seen[prefix_sum - k] to count — that many subarrays ending here sum to k
  • Update: increment seen[prefix_sum] by 1 (record this prefix sum for future lookups)
  • Return: count is the total number of valid subarrays

Why Initialize with {0: 1}?

The entry {0: 1} handles the case where a subarray starting from index 0 sums to k. In that case, prefix_sum = k and we look up k - k = 0, which needs to be in the map. The "empty prefix" with sum 0 represents the start of the array.

Complexity

Time O(n)
Space O(n)

We iterate through the array once, and each hash map lookup/insert is O(1) on average. In the worst case, the hash map stores up to n + 1 distinct prefix sums.