Subarray Sum Equals K Visualization & Animation

Counts subarrays with sum exactly equal to k using prefix sums and a HashMap; O(n) time and space.

## What is it? Find the total number of contiguous subarrays whose elements sum to exactly `k`. Uses a prefix sum combined with a HashMap for an O(n) solution. ## How it works - Maintain a running `prefixSum = 0` and a HashMap `count` initialized with `{0: 1}` - For each element: - `prefixSum += arr[i]` - If `prefixSum - k` is in the map → add its count to the result (a subarray ending here sums to k) - Increment `count[prefixSum]` in the map - Return result **Why:** `sum(l, r) = k` iff `prefix[r+1] - prefix[l] = k` iff `prefix[l] = prefix[r+1] - k` ## When to use - Count subarrays with a target sum (LeetCode 560) - Count subarrays with at most k distinct elements - Any "count subarrays with sum constraint" problem ## Key Points - O(n) time and space - The `{0: 1}` initialization handles subarrays starting from index 0 - Works for negative numbers (unlike sliding window which requires non-negative values)

Category: algorithms

Difficulty: intermediate

Time Complexity: O(n)

Space Complexity: O(n)

Subarray Sum Equals K

intermediate

Counts subarrays with sum exactly equal to k using prefix sums and a HashMap; O(n) time and space.

GFGLeetCode
1
0
2
1
3
2
-2
3
2
4
Prefix Sum
Count
0→
1
Current index
Array element
prefixSum added to map
Target found (hit)
Initialise: prefixSum = 0, map = {0: 1}. The seed "0" accounts for subarrays starting at index 0.