What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

Theory Context•Two Pointers & Sliding Window

Builds on Hash Map and Prefix Sums, which you haven’t finished yet.

P2MediumBuilt on Prefix Sums~4 min speedrun

Prefix Sum + Hash Map

Built on

Prefix SumsKeep a map from each earlier prefix sum to how often it occurred, so a range with the target sum is found in one pass.

Unlocks

Difference Array Fenwick Tree Segment Tree

Subarray Sum Equals K (LC 560)(opens leetcode.com)

You have an array of integers nums and a target integer k. Count how many contiguous, non-empty subarrays of nums add up to exactly k, and return that count.

Example 1

Input:nums = [1,1,1], k = 2

Output:2

[1,1] at positions 0-1 and [1,1] at positions 1-2 both sum to 2.

Prefix Sum Map

prefix[R+1] - prefix[L] = target (Algebraic Point Lookup)

Spot it when: You count or find subarrays with an exact sum (or equal numbers of 0s and 1s, or a sum divisible by k), especially when values can be negative.

Prefix Sum Map

Python

1	from typing import Callable, Hashable, List
2	from collections import defaultdict
3
4
5	def count_by_prefix(nums: List[int], key: Callable[[int], Hashable], needed_key: Callable[[int], Hashable]) -> int:
6	"""Prefix Sum Map: count the subarrays nums[L..R] where key(P[L]) == needed_key(P[R + 1]).
7	P[i] is the sum of the first i values, so P[0] = 0 is the empty prefix.
8	The subarray nums[L..R] sums to P[R + 1] - P[L].
9	For an exact sum k, key(p) = p and needed_key(p) = p - k.
10	For a sum divisible by k, key(p) = needed_key(p) = p % k.
11	A longest subarray (Contiguous Array) stores the first index of each key instead of a count: see that gotcha.
12	N = len(nums). T = the cost of one key or needed_key call.
13	Time: O(N * T) \| Space: O(N)
14	"""
15	# prefix_counts: how many earlier prefixes (keyed by key()) have occurred so far
16	prefix_counts = defaultdict(int)
17	prefix_counts[key(0)] = 1 # The empty prefix P[0] = 0 occurs once
18
19	running_sum = 0
20	total_matches = 0
21
22	for num in nums:
23	# 1. Extend The Running Prefix:
24	# running_sum becomes P[R + 1] once num is folded in.
25	running_sum += num
26	# 2. Look Up The Matching Earlier Prefix:
27	# Every earlier prefix P[L] already counted under needed_key(running_sum) ends a subarray nums[L..R] that matches, so add how many there were before this prefix is added.
28	total_matches += prefix_counts.get(needed_key(running_sum), 0)
29	# 3. Record The Current Prefix:
30	# Add running_sum after the lookup, so a subarray never matches against itself.
31	prefix_counts[key(running_sum)] += 1
32
33	return total_matches

Invariant: Before num is added, prefix_counts holds how often each prefix sum of the elements before it has occurred, including the empty prefix 0.

The sum of nums[L..R] equals P[R+1] - P[L], where P is the running prefix sum. So the number of subarrays ending here with sum k is how many earlier prefixes equal running_sum - k: look up needed_prefix in prefix_counts, then add the current running_sum. Each subarray is counted once, at its last element, and nothing depends on the values being positive, so it works with negative numbers, where sliding windows fail. The trap is the empty prefix: start with prefix_counts[0] = 1, or every subarray that begins at index 0 is missed.

See it run

Prefix Sum Map, step by step

running_sum 0prefix_counts {}total_matches 0

Row nums holds the input. Row prefix holds the prefix sums, where prefix[0] = 0 is the empty prefix. Row needed holds running_sum - k.

num the value nums[i] added to running_sum in this step
running_sum the prefix sum that ends at the current value
stored a prefix sum written into prefix_counts in this step
needed the value running_sum - k that is looked up in prefix_counts
match an earlier prefix sum equal to needed_prefix
empty prefix the empty prefix, with sum 0, that starts the map

Start: nums = [1, 2, 3, -3, 3] and k = 3. The map must know the empty prefix before the loop starts.

nums

-3

prefix

needed

1 / 19

Gotchas1 of 4

The trap
Gotcha 1: Leaving out prefix_counts[0] = 1
Mistake
```
prefix_counts = defaultdict(int)
```
Fix
```
prefix_counts = defaultdict(int)
prefix_counts[0] = 1
```
What happens: A subarray that starts at index 0 has the sum running_sum. So its needed_prefix is 0. Prefix sum 0 belongs to the empty prefix, before any element. Without prefix_counts[0] = 1, that lookup finds nothing, and those subarrays are not counted.
Example: nums = [1, 1, 1], k = 2
Mistake: returns 1Fix: returns 2
Gotcha 2: Adding the current prefix before the lookup
Mistake
```
prefix_counts[running_sum] += 1
needed_prefix = running_sum - k
```
Fix
```
needed_prefix = running_sum - k
```
What happens: The lookup must see only the prefixes before the current one. If running_sum is added first, the lookup can find the current prefix itself. With k = 0, needed_prefix equals running_sum. So every element counts one empty subarray.
Example: nums = [1], k = 0
Mistake: returns 1Fix: returns 0
Gotcha 3: Overwriting the first index of a prefix sum
Mistake
```
first_index[running_sum] = i
```
Fix
```
if running_sum not in first_index:
    first_index[running_sum] = i
```
What happens: Maximum Size Subarray Sum Equals k (LC 325) and Contiguous Array (LC 525) want the longest subarray, not a count. So the map stores the first index where each prefix sum appears. The longest subarray ending at i starts right after that first index. Writing a later index over it makes every subarray found shorter.
Gotcha 4: Keying on running_sum when the question is divisibility
Mistake
```
prefix_counts[running_sum] += 1
```
Fix
```
prefix_counts[running_sum % k] += 1
```
What happens: Subarray Sums Divisible by K (LC 974) and Continuous Subarray Sum (LC 523) ask about sums divisible by k. Two prefixes with the same remainder running_sum % k enclose a sum divisible by k. So the key is the remainder, not the sum. Python's % never returns a negative remainder. In Java or C++, add k to a negative remainder first.

Not this one if…

All values are positive and you want the shortest subarray whose sum is at least a target, as in Minimum Size Subarray Sum (LC 209), not a count of exact sums. See Shortest Window
The input is a list of updates that each add to a whole range, and you need every final value, as in Range Addition (LC 370), not subarrays with a given sum. See Difference Array

Deep Dive

From a search over ranges to a lookup

The Prefix Sums card answers a question about a range you already know. Here the ranges are unknown. You must count the ranges nums[L..R] whose sum is k.

The range sum is P[R + 1] - P[L]. It equals k exactly when P[L] = P[R + 1] - k. So at each element, the question is how many earlier prefixes have the value running_sum - k. That value is needed_prefix.

A hash map answers the question in constant time. prefix_counts[v] is the number of earlier prefixes with the value v. The loop adds prefix_counts[needed_prefix] to total_matches, and it counts each subarray once, at its last element.

The map keeps a count and not a yes or no, because several earlier prefixes can have the same value. Each of them is the start of a different subarray.

Nothing in this argument uses the sign of a value. It works with negative numbers. A shrinking window does not: for nums = [1, -1, 1] and k = 1, a window that shrinks when the sum is above k finds 2 subarrays, but the answer is 3.

The loop traced on [1, 2, 3, -3, 3] with k = 3

The prefix sums are 0, 1, 3, 6, 3, 6. The map starts as {0: 1}, because the empty prefix occurs once.

At nums[1], running_sum = 3 and needed_prefix = 0. The map holds 0 once. That match is the subarray [1, 2], which starts at index 0.

At nums[2], running_sum = 6 and needed_prefix = 3. The prefix 3 occurred once, so the subarray [3] is counted.

At nums[3] = -3, running_sum returns to 3 and needed_prefix = 0. The subarray [1, 2, 3, -3] is counted. Then prefix_counts[3] becomes 2.

At nums[4], running_sum = 6 and needed_prefix = 3. The map holds 3 twice, so two subarrays are counted: [3, -3, 3] and [3]. The total is 5.

The trap is the first line of the code. Without prefix_counts[0] = 1, the matches that use the empty prefix are missed. Here that loses [1, 2] and [1, 2, 3, -3], and the answer would be 3.

Order of the lookup and the record

The loop looks up needed_prefix first and records running_sum after. The lookup must see only earlier prefixes.

If the record comes first and k = 0, then needed_prefix equals running_sum. The lookup finds the current prefix itself and counts an empty subarray. For nums = [1] and k = 0, the answer would be 1 instead of 0.

Changing the key for other questions

The template takes a key and a needed_key. Only these two change between problems. The loop stays the same.

For a sum divisible by k, as in Subarray Sums Divisible by K (LC 974), two prefixes with the same remainder P % k enclose a sum divisible by k. The key is the remainder. For nums = [4, 5, 0, -2, -3, 1] and k = 5, the answer is 7.

For the longest subarray, as in Maximum Size Subarray Sum Equals k (LC 325), store the first index of each prefix and not a count. The longest subarray that ends at i starts right after the first index of running_sum - k. For nums = [1, -1, 5, -2, 3] and k = 3, the answer is 4.

For equal numbers of 0 and 1, as in Contiguous Array (LC 525), replace each 0 by -1. A subarray with equal numbers now has the sum 0. For [0, 1, 0], the answer is 2.

The cost of every version is O(N) time. The map holds up to N + 1 prefixes, so the extra space is O(N).

60-Second Pitch

"I need the number of subarrays with sum k, and values can be negative, so a window will not work. A subarray from L to R has the sum P[R + 1] - P[L]. It equals k when P[L] equals running_sum - k. So at each element I look up how many earlier prefixes have that value. I keep the counts in a hash map and start with prefix_counts[0] = 1 for the empty prefix. I look up first and record after, so a subarray never matches itself. The time is O(N) and the space is O(N). For divisibility the key becomes the remainder, and for the longest subarray the map stores the first index."

Common Questions

Why does a sliding window fail here, and this method does not?: A window moves by a rule such as "shrink while the sum is too big". That rule needs the sum to grow when the window grows, which fails with negative values. The map method only uses the identity P[R + 1] - P[L] = k, which holds for any values.
Why does the map store counts and not just which prefixes exist?: Several earlier prefixes can have the same value. Each one starts a different subarray that ends at the current element. The count says how many.
Why is prefix_counts[0] = 1 needed before the loop?: A subarray that starts at index 0 has the sum running_sum, so its needed prefix is 0. The prefix 0 is the empty prefix, before any element. The map must hold it, or those subarrays are missed.
How do you find the longest subarray and not the count?: Store the first index where each prefix sum appears, with 0 at index -1. At index i, if running_sum - k is in the map, the length is i minus that first index. Never overwrite a stored index, because the first index gives the longest subarray.
What is the cost, and what does the map cost in space?: The time is O(N) with an average constant cost per map operation. The map holds up to N + 1 different prefixes, so the extra space is O(N). The Prefix Sums card needs the same space but answers only known ranges.

SWE Reasoning

Spot it

The question counts or finds subarrays with an exact sum, or with a sum divisible by k, or with equal numbers of two kinds of values.
Values can be negative, so a window that grows and shrinks cannot decide which way to move.
The ranges are unknown. The target is known.
Example problems: Subarray Sum Equals K (LC 560), Subarray Sums Divisible by K (LC 974), Contiguous Array (LC 525).

The invariant, step by step

Before the loop, prefix_counts[0] = 1: the empty prefix occurs once.
For each num, running_sum becomes the prefix sum that ends at num.
prefix_counts holds the earlier prefixes only, so the lookup of needed_prefix = running_sum - k counts the subarrays that end at num and sum to k.
Only then is running_sum added to prefix_counts, so a subarray never matches itself.
Every subarray ends at exactly one element, so total_matches counts each subarray once.

Traps

Leaving out prefix_counts[0] = 1. Every subarray that starts at index 0 is missed. For [1, 1, 1] and k = 2, the answer is 1 instead of 2.
Recording before the lookup. With k = 0 the lookup finds the current prefix and counts an empty subarray.
Using a set and not a count. Two earlier prefixes with the same value are two different subarrays, and a set counts them once.
Keeping the last index for the longest subarray. The first index gives the longest one. A later index overwrites it and makes the answer shorter.
Using the sum as the key for divisibility. The key is running_sum % k.

Practice

Canonical LeetCode:Subarray Sum Equals K (LC 560)Contiguous Array (LC 525)Continuous Subarray Sum (LC 523)Number of Sub-arrays With Odd Sum (LC 1524)Subarray Sums Divisible by K (LC 974)Binary Subarrays With Sum (LC 930)Path Sum III (LC 437)Maximum Size Subarray Sum Equals k (LC 325)Count Triplets That Can Form Two Arrays of Equal XOR (LC 1442)

Theory Context•Two Pointers & Sliding Window

Builds on Hash Map and Prefix Sums, which you haven’t finished yet.

P2MediumBuilt on Prefix Sums~4 min speedrun

Prefix Sum + Hash Map

Built on

Prefix SumsKeep a map from each earlier prefix sum to how often it occurred, so a range with the target sum is found in one pass.

Unlocks

Difference Array Fenwick Tree Segment Tree

Subarray Sum Equals K (LC 560)(opens leetcode.com)

You have an array of integers nums and a target integer k. Count how many contiguous, non-empty subarrays of nums add up to exactly k, and return that count.

Example 1

Input:nums = [1,1,1], k = 2

Output:2

[1,1] at positions 0-1 and [1,1] at positions 1-2 both sum to 2.

Prefix Sum Map

prefix[R+1] - prefix[L] = target (Algebraic Point Lookup)

Spot it when: You count or find subarrays with an exact sum (or equal numbers of 0s and 1s, or a sum divisible by k), especially when values can be negative.

Prefix Sum Map

Python

1	from typing import Callable, Hashable, List
2	from collections import defaultdict
3
4
5	def count_by_prefix(nums: List[int], key: Callable[[int], Hashable], needed_key: Callable[[int], Hashable]) -> int:
6	"""Prefix Sum Map: count the subarrays nums[L..R] where key(P[L]) == needed_key(P[R + 1]).
7	P[i] is the sum of the first i values, so P[0] = 0 is the empty prefix.
8	The subarray nums[L..R] sums to P[R + 1] - P[L].
9	For an exact sum k, key(p) = p and needed_key(p) = p - k.
10	For a sum divisible by k, key(p) = needed_key(p) = p % k.
11	A longest subarray (Contiguous Array) stores the first index of each key instead of a count: see that gotcha.
12	N = len(nums). T = the cost of one key or needed_key call.
13	Time: O(N * T) \| Space: O(N)
14	"""
15	# prefix_counts: how many earlier prefixes (keyed by key()) have occurred so far
16	prefix_counts = defaultdict(int)
17	prefix_counts[key(0)] = 1 # The empty prefix P[0] = 0 occurs once
18
19	running_sum = 0
20	total_matches = 0
21
22	for num in nums:
23	# 1. Extend The Running Prefix:
24	# running_sum becomes P[R + 1] once num is folded in.
25	running_sum += num
26	# 2. Look Up The Matching Earlier Prefix:
27	# Every earlier prefix P[L] already counted under needed_key(running_sum) ends a subarray nums[L..R] that matches, so add how many there were before this prefix is added.
28	total_matches += prefix_counts.get(needed_key(running_sum), 0)
29	# 3. Record The Current Prefix:
30	# Add running_sum after the lookup, so a subarray never matches against itself.
31	prefix_counts[key(running_sum)] += 1
32
33	return total_matches

Invariant: Before num is added, prefix_counts holds how often each prefix sum of the elements before it has occurred, including the empty prefix 0.

See it run

Prefix Sum Map, step by step

running_sum 0prefix_counts {}total_matches 0

Row nums holds the input. Row prefix holds the prefix sums, where prefix[0] = 0 is the empty prefix. Row needed holds running_sum - k.

num the value nums[i] added to running_sum in this step
running_sum the prefix sum that ends at the current value
stored a prefix sum written into prefix_counts in this step
needed the value running_sum - k that is looked up in prefix_counts
match an earlier prefix sum equal to needed_prefix
empty prefix the empty prefix, with sum 0, that starts the map

Start: nums = [1, 2, 3, -3, 3] and k = 3. The map must know the empty prefix before the loop starts.

nums

-3

prefix

needed

1 / 19

Gotchas1 of 4

The trap
Gotcha 1: Leaving out prefix_counts[0] = 1
Mistake
```
prefix_counts = defaultdict(int)
```
Fix
```
prefix_counts = defaultdict(int)
prefix_counts[0] = 1
```
What happens: A subarray that starts at index 0 has the sum running_sum. So its needed_prefix is 0. Prefix sum 0 belongs to the empty prefix, before any element. Without prefix_counts[0] = 1, that lookup finds nothing, and those subarrays are not counted.
Example: nums = [1, 1, 1], k = 2
Mistake: returns 1Fix: returns 2
Gotcha 2: Adding the current prefix before the lookup
Mistake
```
prefix_counts[running_sum] += 1
needed_prefix = running_sum - k
```
Fix
```
needed_prefix = running_sum - k
```
What happens: The lookup must see only the prefixes before the current one. If running_sum is added first, the lookup can find the current prefix itself. With k = 0, needed_prefix equals running_sum. So every element counts one empty subarray.
Example: nums = [1], k = 0
Mistake: returns 1Fix: returns 0
Gotcha 3: Overwriting the first index of a prefix sum
Mistake
```
first_index[running_sum] = i
```
Fix
```
if running_sum not in first_index:
    first_index[running_sum] = i
```
What happens: Maximum Size Subarray Sum Equals k (LC 325) and Contiguous Array (LC 525) want the longest subarray, not a count. So the map stores the first index where each prefix sum appears. The longest subarray ending at i starts right after that first index. Writing a later index over it makes every subarray found shorter.
Gotcha 4: Keying on running_sum when the question is divisibility
Mistake
```
prefix_counts[running_sum] += 1
```
Fix
```
prefix_counts[running_sum % k] += 1
```
What happens: Subarray Sums Divisible by K (LC 974) and Continuous Subarray Sum (LC 523) ask about sums divisible by k. Two prefixes with the same remainder running_sum % k enclose a sum divisible by k. So the key is the remainder, not the sum. Python's % never returns a negative remainder. In Java or C++, add k to a negative remainder first.

Not this one if…

All values are positive and you want the shortest subarray whose sum is at least a target, as in Minimum Size Subarray Sum (LC 209), not a count of exact sums. See Shortest Window
The input is a list of updates that each add to a whole range, and you need every final value, as in Range Addition (LC 370), not subarrays with a given sum. See Difference Array

Deep Dive

From a search over ranges to a lookup

The Prefix Sums card answers a question about a range you already know. Here the ranges are unknown. You must count the ranges nums[L..R] whose sum is k.

The map keeps a count and not a yes or no, because several earlier prefixes can have the same value. Each of them is the start of a different subarray.

The loop traced on [1, 2, 3, -3, 3] with k = 3

The prefix sums are 0, 1, 3, 6, 3, 6. The map starts as {0: 1}, because the empty prefix occurs once.

At nums[1], running_sum = 3 and needed_prefix = 0. The map holds 0 once. That match is the subarray [1, 2], which starts at index 0.

At nums[2], running_sum = 6 and needed_prefix = 3. The prefix 3 occurred once, so the subarray [3] is counted.

At nums[3] = -3, running_sum returns to 3 and needed_prefix = 0. The subarray [1, 2, 3, -3] is counted. Then prefix_counts[3] becomes 2.

At nums[4], running_sum = 6 and needed_prefix = 3. The map holds 3 twice, so two subarrays are counted: [3, -3, 3] and [3]. The total is 5.

The trap is the first line of the code. Without prefix_counts[0] = 1, the matches that use the empty prefix are missed. Here that loses [1, 2] and [1, 2, 3, -3], and the answer would be 3.

Order of the lookup and the record

The loop looks up needed_prefix first and records running_sum after. The lookup must see only earlier prefixes.

Changing the key for other questions

The template takes a key and a needed_key. Only these two change between problems. The loop stays the same.

For equal numbers of 0 and 1, as in Contiguous Array (LC 525), replace each 0 by -1. A subarray with equal numbers now has the sum 0. For [0, 1, 0], the answer is 2.

The cost of every version is O(N) time. The map holds up to N + 1 prefixes, so the extra space is O(N).

60-Second Pitch

Common Questions

Why does a sliding window fail here, and this method does not?: A window moves by a rule such as "shrink while the sum is too big". That rule needs the sum to grow when the window grows, which fails with negative values. The map method only uses the identity P[R + 1] - P[L] = k, which holds for any values.
Why does the map store counts and not just which prefixes exist?: Several earlier prefixes can have the same value. Each one starts a different subarray that ends at the current element. The count says how many.
Why is prefix_counts[0] = 1 needed before the loop?: A subarray that starts at index 0 has the sum running_sum, so its needed prefix is 0. The prefix 0 is the empty prefix, before any element. The map must hold it, or those subarrays are missed.
How do you find the longest subarray and not the count?: Store the first index where each prefix sum appears, with 0 at index -1. At index i, if running_sum - k is in the map, the length is i minus that first index. Never overwrite a stored index, because the first index gives the longest subarray.
What is the cost, and what does the map cost in space?: The time is O(N) with an average constant cost per map operation. The map holds up to N + 1 different prefixes, so the extra space is O(N). The Prefix Sums card needs the same space but answers only known ranges.

SWE Reasoning

Spot it

The question counts or finds subarrays with an exact sum, or with a sum divisible by k, or with equal numbers of two kinds of values.
Values can be negative, so a window that grows and shrinks cannot decide which way to move.
The ranges are unknown. The target is known.
Example problems: Subarray Sum Equals K (LC 560), Subarray Sums Divisible by K (LC 974), Contiguous Array (LC 525).

The invariant, step by step

Before the loop, prefix_counts[0] = 1: the empty prefix occurs once.
For each num, running_sum becomes the prefix sum that ends at num.
prefix_counts holds the earlier prefixes only, so the lookup of needed_prefix = running_sum - k counts the subarrays that end at num and sum to k.
Only then is running_sum added to prefix_counts, so a subarray never matches itself.
Every subarray ends at exactly one element, so total_matches counts each subarray once.

Traps

Leaving out prefix_counts[0] = 1. Every subarray that starts at index 0 is missed. For [1, 1, 1] and k = 2, the answer is 1 instead of 2.
Recording before the lookup. With k = 0 the lookup finds the current prefix and counts an empty subarray.
Using a set and not a count. Two earlier prefixes with the same value are two different subarrays, and a set counts them once.
Keeping the last index for the longest subarray. The first index gives the longest one. A later index overwrites it and makes the answer shorter.
Using the sum as the key for divisibility. The key is running_sum % k.

Practice

Theory Context•Two Pointers & Sliding Window

Builds on Hash Map and Prefix Sums, which you haven’t finished yet.

P2MediumBuilt on Prefix Sums~4 min speedrun

Prefix Sum + Hash Map

Built on

Prefix SumsKeep a map from each earlier prefix sum to how often it occurred, so a range with the target sum is found in one pass.

Unlocks

Difference Array Fenwick Tree Segment Tree

Subarray Sum Equals K (LC 560)(opens leetcode.com)

You have an array of integers nums and a target integer k. Count how many contiguous, non-empty subarrays of nums add up to exactly k, and return that count.

Example 1

Input:nums = [1,1,1], k = 2

Output:2

[1,1] at positions 0-1 and [1,1] at positions 1-2 both sum to 2.

Prefix Sum Map

prefix[R+1] - prefix[L] = target (Algebraic Point Lookup)

Spot it when: You count or find subarrays with an exact sum (or equal numbers of 0s and 1s, or a sum divisible by k), especially when values can be negative.

Prefix Sum Map

Python

1	from typing import Callable, Hashable, List
2	from collections import defaultdict
3
4
5	def count_by_prefix(nums: List[int], key: Callable[[int], Hashable], needed_key: Callable[[int], Hashable]) -> int:
6	"""Prefix Sum Map: count the subarrays nums[L..R] where key(P[L]) == needed_key(P[R + 1]).
7	P[i] is the sum of the first i values, so P[0] = 0 is the empty prefix.
8	The subarray nums[L..R] sums to P[R + 1] - P[L].
9	For an exact sum k, key(p) = p and needed_key(p) = p - k.
10	For a sum divisible by k, key(p) = needed_key(p) = p % k.
11	A longest subarray (Contiguous Array) stores the first index of each key instead of a count: see that gotcha.
12	N = len(nums). T = the cost of one key or needed_key call.
13	Time: O(N * T) \| Space: O(N)
14	"""
15	# prefix_counts: how many earlier prefixes (keyed by key()) have occurred so far
16	prefix_counts = defaultdict(int)
17	prefix_counts[key(0)] = 1 # The empty prefix P[0] = 0 occurs once
18
19	running_sum = 0
20	total_matches = 0
21
22	for num in nums:
23	# 1. Extend The Running Prefix:
24	# running_sum becomes P[R + 1] once num is folded in.
25	running_sum += num
26	# 2. Look Up The Matching Earlier Prefix:
27	# Every earlier prefix P[L] already counted under needed_key(running_sum) ends a subarray nums[L..R] that matches, so add how many there were before this prefix is added.
28	total_matches += prefix_counts.get(needed_key(running_sum), 0)
29	# 3. Record The Current Prefix:
30	# Add running_sum after the lookup, so a subarray never matches against itself.
31	prefix_counts[key(running_sum)] += 1
32
33	return total_matches

Invariant: Before num is added, prefix_counts holds how often each prefix sum of the elements before it has occurred, including the empty prefix 0.

See it run

Prefix Sum Map, step by step

running_sum 0prefix_counts {}total_matches 0

Row nums holds the input. Row prefix holds the prefix sums, where prefix[0] = 0 is the empty prefix. Row needed holds running_sum - k.

num the value nums[i] added to running_sum in this step
running_sum the prefix sum that ends at the current value
stored a prefix sum written into prefix_counts in this step
needed the value running_sum - k that is looked up in prefix_counts
match an earlier prefix sum equal to needed_prefix
empty prefix the empty prefix, with sum 0, that starts the map

Start: nums = [1, 2, 3, -3, 3] and k = 3. The map must know the empty prefix before the loop starts.

nums

-3

prefix

needed

1 / 19

Gotchas1 of 4

The trap
Gotcha 1: Leaving out prefix_counts[0] = 1
Mistake
```
prefix_counts = defaultdict(int)
```
Fix
```
prefix_counts = defaultdict(int)
prefix_counts[0] = 1
```
What happens: A subarray that starts at index 0 has the sum running_sum. So its needed_prefix is 0. Prefix sum 0 belongs to the empty prefix, before any element. Without prefix_counts[0] = 1, that lookup finds nothing, and those subarrays are not counted.
Example: nums = [1, 1, 1], k = 2
Mistake: returns 1Fix: returns 2
Gotcha 2: Adding the current prefix before the lookup
Mistake
```
prefix_counts[running_sum] += 1
needed_prefix = running_sum - k
```
Fix
```
needed_prefix = running_sum - k
```
What happens: The lookup must see only the prefixes before the current one. If running_sum is added first, the lookup can find the current prefix itself. With k = 0, needed_prefix equals running_sum. So every element counts one empty subarray.
Example: nums = [1], k = 0
Mistake: returns 1Fix: returns 0
Gotcha 3: Overwriting the first index of a prefix sum
Mistake
```
first_index[running_sum] = i
```
Fix
```
if running_sum not in first_index:
    first_index[running_sum] = i
```
What happens: Maximum Size Subarray Sum Equals k (LC 325) and Contiguous Array (LC 525) want the longest subarray, not a count. So the map stores the first index where each prefix sum appears. The longest subarray ending at i starts right after that first index. Writing a later index over it makes every subarray found shorter.
Gotcha 4: Keying on running_sum when the question is divisibility
Mistake
```
prefix_counts[running_sum] += 1
```
Fix
```
prefix_counts[running_sum % k] += 1
```
What happens: Subarray Sums Divisible by K (LC 974) and Continuous Subarray Sum (LC 523) ask about sums divisible by k. Two prefixes with the same remainder running_sum % k enclose a sum divisible by k. So the key is the remainder, not the sum. Python's % never returns a negative remainder. In Java or C++, add k to a negative remainder first.

Not this one if…

All values are positive and you want the shortest subarray whose sum is at least a target, as in Minimum Size Subarray Sum (LC 209), not a count of exact sums. See Shortest Window
The input is a list of updates that each add to a whole range, and you need every final value, as in Range Addition (LC 370), not subarrays with a given sum. See Difference Array

Deep Dive

From a search over ranges to a lookup

The Prefix Sums card answers a question about a range you already know. Here the ranges are unknown. You must count the ranges nums[L..R] whose sum is k.

The map keeps a count and not a yes or no, because several earlier prefixes can have the same value. Each of them is the start of a different subarray.

The loop traced on [1, 2, 3, -3, 3] with k = 3

The prefix sums are 0, 1, 3, 6, 3, 6. The map starts as {0: 1}, because the empty prefix occurs once.

At nums[1], running_sum = 3 and needed_prefix = 0. The map holds 0 once. That match is the subarray [1, 2], which starts at index 0.

At nums[2], running_sum = 6 and needed_prefix = 3. The prefix 3 occurred once, so the subarray [3] is counted.

At nums[3] = -3, running_sum returns to 3 and needed_prefix = 0. The subarray [1, 2, 3, -3] is counted. Then prefix_counts[3] becomes 2.

At nums[4], running_sum = 6 and needed_prefix = 3. The map holds 3 twice, so two subarrays are counted: [3, -3, 3] and [3]. The total is 5.

The trap is the first line of the code. Without prefix_counts[0] = 1, the matches that use the empty prefix are missed. Here that loses [1, 2] and [1, 2, 3, -3], and the answer would be 3.

Order of the lookup and the record

The loop looks up needed_prefix first and records running_sum after. The lookup must see only earlier prefixes.

Changing the key for other questions

The template takes a key and a needed_key. Only these two change between problems. The loop stays the same.

For equal numbers of 0 and 1, as in Contiguous Array (LC 525), replace each 0 by -1. A subarray with equal numbers now has the sum 0. For [0, 1, 0], the answer is 2.

The cost of every version is O(N) time. The map holds up to N + 1 prefixes, so the extra space is O(N).

60-Second Pitch

Common Questions

Why does a sliding window fail here, and this method does not?: A window moves by a rule such as "shrink while the sum is too big". That rule needs the sum to grow when the window grows, which fails with negative values. The map method only uses the identity P[R + 1] - P[L] = k, which holds for any values.
Why does the map store counts and not just which prefixes exist?: Several earlier prefixes can have the same value. Each one starts a different subarray that ends at the current element. The count says how many.
Why is prefix_counts[0] = 1 needed before the loop?: A subarray that starts at index 0 has the sum running_sum, so its needed prefix is 0. The prefix 0 is the empty prefix, before any element. The map must hold it, or those subarrays are missed.
How do you find the longest subarray and not the count?: Store the first index where each prefix sum appears, with 0 at index -1. At index i, if running_sum - k is in the map, the length is i minus that first index. Never overwrite a stored index, because the first index gives the longest subarray.
What is the cost, and what does the map cost in space?: The time is O(N) with an average constant cost per map operation. The map holds up to N + 1 different prefixes, so the extra space is O(N). The Prefix Sums card needs the same space but answers only known ranges.

SWE Reasoning

Spot it

The question counts or finds subarrays with an exact sum, or with a sum divisible by k, or with equal numbers of two kinds of values.
Values can be negative, so a window that grows and shrinks cannot decide which way to move.
The ranges are unknown. The target is known.
Example problems: Subarray Sum Equals K (LC 560), Subarray Sums Divisible by K (LC 974), Contiguous Array (LC 525).

The invariant, step by step

Before the loop, prefix_counts[0] = 1: the empty prefix occurs once.
For each num, running_sum becomes the prefix sum that ends at num.
prefix_counts holds the earlier prefixes only, so the lookup of needed_prefix = running_sum - k counts the subarrays that end at num and sum to k.
Only then is running_sum added to prefix_counts, so a subarray never matches itself.
Every subarray ends at exactly one element, so total_matches counts each subarray once.

Traps

Leaving out prefix_counts[0] = 1. Every subarray that starts at index 0 is missed. For [1, 1, 1] and k = 2, the answer is 1 instead of 2.
Recording before the lookup. With k = 0 the lookup finds the current prefix and counts an empty subarray.
Using a set and not a count. Two earlier prefixes with the same value are two different subarrays, and a set counts them once.
Keeping the last index for the longest subarray. The first index gives the longest one. A later index overwrites it and makes the answer shorter.
Using the sum as the key for divisibility. The key is running_sum % k.

Practice

Theory Context•Two Pointers & Sliding Window

Builds on Hash Map and Prefix Sums, which you haven’t finished yet.

P2MediumBuilt on Prefix Sums~4 min speedrun

Prefix Sum + Hash Map

Built on

Prefix SumsKeep a map from each earlier prefix sum to how often it occurred, so a range with the target sum is found in one pass.

Unlocks

Difference Array Fenwick Tree Segment Tree

Subarray Sum Equals K (LC 560)(opens leetcode.com)

You have an array of integers nums and a target integer k. Count how many contiguous, non-empty subarrays of nums add up to exactly k, and return that count.

Example 1

Input:nums = [1,1,1], k = 2

Output:2

[1,1] at positions 0-1 and [1,1] at positions 1-2 both sum to 2.

Prefix Sum Map

prefix[R+1] - prefix[L] = target (Algebraic Point Lookup)

Spot it when: You count or find subarrays with an exact sum (or equal numbers of 0s and 1s, or a sum divisible by k), especially when values can be negative.

Prefix Sum Map

Python

1	from typing import Callable, Hashable, List
2	from collections import defaultdict
3
4
5	def count_by_prefix(nums: List[int], key: Callable[[int], Hashable], needed_key: Callable[[int], Hashable]) -> int:
6	"""Prefix Sum Map: count the subarrays nums[L..R] where key(P[L]) == needed_key(P[R + 1]).
7	P[i] is the sum of the first i values, so P[0] = 0 is the empty prefix.
8	The subarray nums[L..R] sums to P[R + 1] - P[L].
9	For an exact sum k, key(p) = p and needed_key(p) = p - k.
10	For a sum divisible by k, key(p) = needed_key(p) = p % k.
11	A longest subarray (Contiguous Array) stores the first index of each key instead of a count: see that gotcha.
12	N = len(nums). T = the cost of one key or needed_key call.
13	Time: O(N * T) \| Space: O(N)
14	"""
15	# prefix_counts: how many earlier prefixes (keyed by key()) have occurred so far
16	prefix_counts = defaultdict(int)
17	prefix_counts[key(0)] = 1 # The empty prefix P[0] = 0 occurs once
18
19	running_sum = 0
20	total_matches = 0
21
22	for num in nums:
23	# 1. Extend The Running Prefix:
24	# running_sum becomes P[R + 1] once num is folded in.
25	running_sum += num
26	# 2. Look Up The Matching Earlier Prefix:
27	# Every earlier prefix P[L] already counted under needed_key(running_sum) ends a subarray nums[L..R] that matches, so add how many there were before this prefix is added.
28	total_matches += prefix_counts.get(needed_key(running_sum), 0)
29	# 3. Record The Current Prefix:
30	# Add running_sum after the lookup, so a subarray never matches against itself.
31	prefix_counts[key(running_sum)] += 1
32
33	return total_matches

Invariant: Before num is added, prefix_counts holds how often each prefix sum of the elements before it has occurred, including the empty prefix 0.

See it run

Prefix Sum Map, step by step

running_sum 0prefix_counts {}total_matches 0

Row nums holds the input. Row prefix holds the prefix sums, where prefix[0] = 0 is the empty prefix. Row needed holds running_sum - k.

num the value nums[i] added to running_sum in this step
running_sum the prefix sum that ends at the current value
stored a prefix sum written into prefix_counts in this step
needed the value running_sum - k that is looked up in prefix_counts
match an earlier prefix sum equal to needed_prefix
empty prefix the empty prefix, with sum 0, that starts the map

Start: nums = [1, 2, 3, -3, 3] and k = 3. The map must know the empty prefix before the loop starts.

nums

-3

prefix

needed

1 / 19

Gotchas1 of 4

The trap
Gotcha 1: Leaving out prefix_counts[0] = 1
Mistake
```
prefix_counts = defaultdict(int)
```
Fix
```
prefix_counts = defaultdict(int)
prefix_counts[0] = 1
```
What happens: A subarray that starts at index 0 has the sum running_sum. So its needed_prefix is 0. Prefix sum 0 belongs to the empty prefix, before any element. Without prefix_counts[0] = 1, that lookup finds nothing, and those subarrays are not counted.
Example: nums = [1, 1, 1], k = 2
Mistake: returns 1Fix: returns 2
Gotcha 2: Adding the current prefix before the lookup
Mistake
```
prefix_counts[running_sum] += 1
needed_prefix = running_sum - k
```
Fix
```
needed_prefix = running_sum - k
```
What happens: The lookup must see only the prefixes before the current one. If running_sum is added first, the lookup can find the current prefix itself. With k = 0, needed_prefix equals running_sum. So every element counts one empty subarray.
Example: nums = [1], k = 0
Mistake: returns 1Fix: returns 0
Gotcha 3: Overwriting the first index of a prefix sum
Mistake
```
first_index[running_sum] = i
```
Fix
```
if running_sum not in first_index:
    first_index[running_sum] = i
```
What happens: Maximum Size Subarray Sum Equals k (LC 325) and Contiguous Array (LC 525) want the longest subarray, not a count. So the map stores the first index where each prefix sum appears. The longest subarray ending at i starts right after that first index. Writing a later index over it makes every subarray found shorter.
Gotcha 4: Keying on running_sum when the question is divisibility
Mistake
```
prefix_counts[running_sum] += 1
```
Fix
```
prefix_counts[running_sum % k] += 1
```
What happens: Subarray Sums Divisible by K (LC 974) and Continuous Subarray Sum (LC 523) ask about sums divisible by k. Two prefixes with the same remainder running_sum % k enclose a sum divisible by k. So the key is the remainder, not the sum. Python's % never returns a negative remainder. In Java or C++, add k to a negative remainder first.

Not this one if…

All values are positive and you want the shortest subarray whose sum is at least a target, as in Minimum Size Subarray Sum (LC 209), not a count of exact sums. See Shortest Window
The input is a list of updates that each add to a whole range, and you need every final value, as in Range Addition (LC 370), not subarrays with a given sum. See Difference Array

Deep Dive

From a search over ranges to a lookup

The Prefix Sums card answers a question about a range you already know. Here the ranges are unknown. You must count the ranges nums[L..R] whose sum is k.

The map keeps a count and not a yes or no, because several earlier prefixes can have the same value. Each of them is the start of a different subarray.

The loop traced on [1, 2, 3, -3, 3] with k = 3

The prefix sums are 0, 1, 3, 6, 3, 6. The map starts as {0: 1}, because the empty prefix occurs once.

At nums[1], running_sum = 3 and needed_prefix = 0. The map holds 0 once. That match is the subarray [1, 2], which starts at index 0.

At nums[2], running_sum = 6 and needed_prefix = 3. The prefix 3 occurred once, so the subarray [3] is counted.

At nums[3] = -3, running_sum returns to 3 and needed_prefix = 0. The subarray [1, 2, 3, -3] is counted. Then prefix_counts[3] becomes 2.

At nums[4], running_sum = 6 and needed_prefix = 3. The map holds 3 twice, so two subarrays are counted: [3, -3, 3] and [3]. The total is 5.

The trap is the first line of the code. Without prefix_counts[0] = 1, the matches that use the empty prefix are missed. Here that loses [1, 2] and [1, 2, 3, -3], and the answer would be 3.

Order of the lookup and the record

The loop looks up needed_prefix first and records running_sum after. The lookup must see only earlier prefixes.

Changing the key for other questions

The template takes a key and a needed_key. Only these two change between problems. The loop stays the same.

For equal numbers of 0 and 1, as in Contiguous Array (LC 525), replace each 0 by -1. A subarray with equal numbers now has the sum 0. For [0, 1, 0], the answer is 2.

The cost of every version is O(N) time. The map holds up to N + 1 prefixes, so the extra space is O(N).

60-Second Pitch

Common Questions

Why does a sliding window fail here, and this method does not?: A window moves by a rule such as "shrink while the sum is too big". That rule needs the sum to grow when the window grows, which fails with negative values. The map method only uses the identity P[R + 1] - P[L] = k, which holds for any values.
Why does the map store counts and not just which prefixes exist?: Several earlier prefixes can have the same value. Each one starts a different subarray that ends at the current element. The count says how many.
Why is prefix_counts[0] = 1 needed before the loop?: A subarray that starts at index 0 has the sum running_sum, so its needed prefix is 0. The prefix 0 is the empty prefix, before any element. The map must hold it, or those subarrays are missed.
How do you find the longest subarray and not the count?: Store the first index where each prefix sum appears, with 0 at index -1. At index i, if running_sum - k is in the map, the length is i minus that first index. Never overwrite a stored index, because the first index gives the longest subarray.
What is the cost, and what does the map cost in space?: The time is O(N) with an average constant cost per map operation. The map holds up to N + 1 different prefixes, so the extra space is O(N). The Prefix Sums card needs the same space but answers only known ranges.

SWE Reasoning

Spot it

The question counts or finds subarrays with an exact sum, or with a sum divisible by k, or with equal numbers of two kinds of values.
Values can be negative, so a window that grows and shrinks cannot decide which way to move.
The ranges are unknown. The target is known.
Example problems: Subarray Sum Equals K (LC 560), Subarray Sums Divisible by K (LC 974), Contiguous Array (LC 525).

The invariant, step by step

Before the loop, prefix_counts[0] = 1: the empty prefix occurs once.
For each num, running_sum becomes the prefix sum that ends at num.
prefix_counts holds the earlier prefixes only, so the lookup of needed_prefix = running_sum - k counts the subarrays that end at num and sum to k.
Only then is running_sum added to prefix_counts, so a subarray never matches itself.
Every subarray ends at exactly one element, so total_matches counts each subarray once.

Traps

Leaving out prefix_counts[0] = 1. Every subarray that starts at index 0 is missed. For [1, 1, 1] and k = 2, the answer is 1 instead of 2.
Recording before the lookup. With k = 0 the lookup finds the current prefix and counts an empty subarray.
Using a set and not a count. Two earlier prefixes with the same value are two different subarrays, and a set counts them once.
Keeping the last index for the longest subarray. The first index gives the longest one. A later index overwrites it and makes the answer shorter.
Using the sum as the key for divisibility. The key is running_sum % k.