Prefix sum with a hash map
Use it when you must count, or measure, runs of consecutive entries whose total meets an exact condition, and entries may be negative. Signal words: consecutive entries, add up to, how many streaks, the longest streak, negative values.
the whole pattern cardfold it
Start a map from running total to a count, or to a position, that holds the total 0 for the empty start.
Step add the entry to the running total. Look up total - target. Use what is found. Then store the current total.
Stop when the entries run out.
It does not answer "at least" or "at most" questions. A lookup finds one exact total.
Cost: O(n) time on average and O(n) space. Trying every streak costs O(n^2) time.
In this lesson you learn to count the runs of consecutive entries that add up to a target, even when some entries are negative. You keep a running total, and a hash table remembers the totals you have already passed.
1. Scenario: streaks of a ledger#
A payments app keeps a ledger for each merchant. Each entry is the net change it made to the merchant's balance, so a refund is a negative number. Your team lead brings a question from Finance.
Your team lead says: How many streaks of consecutive entries add up to exactly the disputed payout?
A ledger holds 100,000 entries, and Finance runs the question for 2,000 merchants every night.
Here is a short test. The entries are [1, -3, 2, 5, 3, -3] and the payout is 5. Four streaks add up to 5. Two of them end at the fourth entry, and two end at the sixth.
So the task is this: count the streaks of consecutive entries that add up to a target, without adding up every streak.
Imagine a hiking trail with an altitude board at every checkpoint. The path goes up and down, so the altitude does not only grow.
You want every stretch of trail with a net climb of exactly 60 metres. You do not measure each stretch. At each board, you look back at the boards you have passed. A stretch ends here and climbs 60 metres for every earlier board that shows an altitude 60 metres lower.
The boards are the running totals, and the list of boards you remember is the hash table of this lesson. A drop in the path is a negative entry, and it needs no special rule.
Like altitude boards on a trail: at each board, look back for the board that would start a stretch with exactly the climb you want.
2. Struggle: solve it by hand first#
Before you write code, solve the test by hand. It shows how much work one ledger takes.
Solve it by hand: The ledger, counted with running totals. The hand-solve sheet loads in your browser.
You pick each entry in turn as the start of a streak. You extend the streak one entry at a time, add up the entries, and mark every sum that reaches 5.
Entries: [1, -3, 2, 5, 3, -3]. The payout is 5.
| Start at entry | Sums as the streak grows | Streaks checked | Result |
|---|---|---|---|
| 1 (value 1) | 1, −2, 0, 5, 8, 5 | 6 | two streaks add up to 5, ending at entries 4 and 6 |
| 2 (value −3) | −3, −1, 4, 7, 4 | 5 | none |
| 3 (value 2) | 2, 7, 10, 7 | 4 | none |
| 4 (value 5) | 5, 8, 5 | 3 | two streaks, ending at entries 4 and 6 |
| 5 (value 3) | 3, 0 | 2 | none |
| 6 (value −3) | −3 | 1 | none |
The search looked at 6 + 5 + 4 + 3 + 2 + 1 = 21 streaks, and 4 of them add up to 5.
Look at what grows. Six entries have 21 streaks. A ledger of n entries has n × (n + 1) / 2.
The first attempt#
You turn the hand method into code.
Start with a correct version. For each start, extend the streak one entry at a time, and count each time the sum equals the target.
def count_runs(amounts, target):
count = 0
for start in range(len(amounts)):
total = 0
for end in range(start, len(amounts)): # every end of a streak
total += amounts[end]
if total == target:
count += 1
return countThis is correct. It looks at every streak once, so it makes n × (n + 1) / 2 additions: O(n^2). The team keeps it as the reference.
The scale check#
Now check real ledgers.
A real ledger holds 100,000 entries, and Finance asks the question for 2,000 merchants.
Here is the count:
- One ledger: 100,000 × 100,001 / 2, which is about 5 × 10^9 streaks.
- Time: at about 10^8 simple operations a second, that is about 50 seconds.
- A night: 2,000 ledgers take about 100,000 seconds, more than a day.
So the nightly report cannot finish in a night, let alone by the morning.
Predict the cost
Q A ledger holds 100,000 entries. The first attempt adds up every streak. About how long does one ledger take at 10^8 additions a second?
Answer & explanation
Answer: C
The number of streaks is n × (n + 1) / 2, which is about 5 × 10^9 for 100,000 entries. At 10^8 additions a second, that is about 50 seconds for a single ledger.
The first attempt is correct, but it adds up streaks, and there are far too many streaks. Now the team looks for a way to avoid them.
3. See: look back at the running totals#
Can we do better?#
Look at the row of entries on the whiteboard.
Write the running total under each entry: the sum of the entries so far. Before any entry, the running total is 0. For [1, -3, 2, 5, 3, -3], the running totals are 0, 1, −2, 0, 5, 8, 5.
Now look at any streak, say entries 4 and 5. Its sum is 5 + 3 = 8. The running total after entry 5 is 8, and before entry 4 it was 0, so the sum is 8 − 0. The sum of any streak is the difference of two running totals.
So a streak ends at the current entry and adds up to the target exactly when an earlier running total equals the current running total minus the target. You do not have to add up the streak. You look for one number.
Keep a hash table from each running total to how often it occurred. This is the running-total table. For each entry:
- Add the entry to the running total.
- Look up
total - target. The count found is the number of streaks that end at this entry. - Add one to the count of the current total.
Look first, store afterwards. The table starts with the total 0 once, for the empty start before any entry, so streaks that begin at the first entry are found. This is the classic LeetCode 560: Subarray Sum Equals K.
| Position | Entry | Running total | Looks up (total − 5) | Found | Streaks so far | Table after |
|---|---|---|---|---|---|---|
| start | 0 | 0 | 0: 1 | |||
| 1 | 1 | 1 | −4 | 0 | 0 | 0: 1, 1: 1 |
| 2 | −3 | −2 | −7 | 0 | 0 | adds −2: 1 |
| 3 | 2 | 0 | −5 | 0 | 0 | 0: 2 |
| 4 | 5 | 5 | 0 | 2 | 2 | adds 5: 1 |
| 5 | 3 | 8 | 3 | 0 | 2 | adds 8: 1 |
| 6 | −3 | 5 | 0 | 2 | 4 | 5: 2 |
The table is a count, not a yes or no. At position 4 the total 0 was seen twice, at the start and after entry 3. Each one starts a different streak that ends at entry 4.
The start gives the streak of the first four entries. The total after entry 3 gives the streak made of entry 4 alone, whose value is 5. Together they add 2.
The table made 6 lookups and 6 inserts. The streak scan looked at 21 streaks. And a lookup does not grow with the ledger.
Why negative entries do no harm#
The table relies on one fact only: the sum of a streak is the later running total minus the earlier one. That subtraction is true for any whole numbers, positive, zero or negative, so the lookup works whether the running totals rise, fall or repeat.
A sliding window relies on more. When its total is above the target, it drops the entry on its left and expects the total to fall. That holds only when no entry is negative.
On this ledger, at the fifth entry the window's total is 8. It drops the 1 and gets 7, then drops the −3 and gets 10: the total rose, and the window keeps shrinking past streaks it needed. Exhibit 3 below shows what it loses.
Race: Add up every streak, against one lookup and one insert per entry. The operation counter loads in your browser.
The race counts the work to add up every streak, against the table. At 10,000 entries the streak scan makes 50,005,000 additions. The table makes 20,000 operations, one lookup and one insert for each entry. That is about 2,500 times less, and the gap grows with n.
A running total is the sum so far, and any streak is the difference of two running totals.
For each entry, look up the running total minus the target. The count found is the number of streaks that end at this entry.
The entries are [3, -3, 3, -3] and the target is 0. The running total keeps returning to the same two values, so the table counts matter. The player stops at five steps and asks you to predict.
Dry run: Predict each step: running totals that repeat. The step-by-step player loads in your browser.
Reading without the player? Cover the last columns and predict them row by row.
| Position | Entry | Running total | Looks up (total − 0) | Found | Streaks so far | Table after |
|---|---|---|---|---|---|---|
| start | 0 | 0 | 0: 1 | |||
| 1 | 3 | 3 | 3 | 0 | 0 | 0: 1, 3: 1 |
| 2 | −3 | 0 | 0 | 1 | 1 | 0: 2, 3: 1 |
| 3 | 3 | 3 | 3 | 1 | 2 | 0: 2, 3: 2 |
| 4 | −3 | 0 | 0 | 2 | 4 | 0: 3, 3: 2 |
Look at position 2. The total 0 is in the table because of the empty start. Without that start, the table would be empty here, and the streak made of the first two entries would be missed. At position 4, the total 0 has been seen twice, so two streaks end here.
4. Shape: the pattern#
Here is the rule that keeps both templates correct. Every line exists to protect it.
Before each entry is read, the table counts every earlier running total, the empty start included, so one lookup counts all the runs that end at that entry.
At the start, the table holds the total 0 once, which is the empty start, so the rule holds. Say it holds before entry j. The template looks up total - target, which counts the runs that end at entry j, and then adds the new total. Now the table covers one more position, so the rule holds before entry j + 1.
No run is missed. A run from entry a to entry b has a start position and an end position. When entry b is read, the start position is already in the table, and the lookup finds it.
Use it when you must count, or measure, runs of consecutive entries whose total meets an exact condition, and entries may be negative. Signal words: consecutive entries, add up to, how many streaks, the longest streak, negative values.
Start: a map from running total to a count, or to a position, that holds the total 0 for the empty start.
Step: add the entry to the running total. Look up total - target. Use what is found. Then store the current total.
Stop: when the entries run out.
It does not answer "at least" or "at most" questions. A lookup finds one exact total.
Cost: O(n) time on average and O(n) space. Trying every streak costs O(n^2) time.
Template 1: count the runs#
def count_runs(amounts, target):
# [1] A table of how often each running total has occurred. The empty start has total 0, once.
seen = {0: 1}
total = 0
count = 0
for amount in amounts:
# [2] The running total after this entry.
total += amount
# [3] Each earlier running total equal to total - target ends a run that adds up to the target.
count += seen.get(total - target, 0)
# [4] Record this running total, after the lookup.
seen[total] = seen.get(total, 0) + 1
# [5] The number of runs.
return countpublic long countRuns(int[] amounts, int target) {
// [1] A table of how often each running total has occurred. The empty start has total 0, once.
java.util.HashMap<Long, Integer> seen = new java.util.HashMap<>();
seen.put(0L, 1);
long total = 0;
long count = 0;
for (int amount : amounts) {
// [2] The running total after this entry.
total += amount;
// [3] Each earlier running total equal to total - target ends a run that adds up to the target.
count += seen.getOrDefault(total - target, 0);
// [4] Record this running total, after the lookup.
seen.put(total, seen.getOrDefault(total, 0) + 1);
}
// [5] The number of runs.
return count;
}long long countRuns(vector<int>& amounts, int target) {
// [1] A table of how often each running total has occurred. The empty start has total 0, once.
unordered_map<long long, int> seen;
seen[0] = 1;
long long total = 0;
long long count = 0;
for (int amount : amounts) {
// [2] The running total after this entry.
total += amount;
// [3] Each earlier running total equal to total - target ends a run that adds up to the target.
auto it = seen.find(total - target);
if (it != seen.end()) {
count += it->second;
}
// [4] Record this running total, after the lookup.
seen[total] += 1;
}
// [5] The number of runs.
return count;
}function countRuns(amounts, target) {
// [1] A table of how often each running total has occurred. The empty start has total 0, once.
const seen = new Map([[0, 1]]);
let total = 0;
let count = 0;
for (const amount of amounts) {
// [2] The running total after this entry.
total += amount;
// [3] Each earlier running total equal to total - target ends a run that adds up to the target.
count += seen.get(total - target) ?? 0;
// [4] Record this running total, after the lookup.
seen.set(total, (seen.get(total) ?? 0) + 1);
}
// [5] The number of runs.
return count;
}Rebuild the template: put its lines back in order. Loads in your browser.
The template in order: seed the table with total zero, update the running total, look up total minus target, then store the total.
Template 2: the longest run#
def longest_run(amounts, target):
# [1] A table from each running total to the first position where it occurred. Position 0 is the empty start.
first_at = {0: 0}
total = 0
best = 0
for position in range(1, len(amounts) + 1):
# [2] The running total after reading this many entries.
total += amounts[position - 1]
# [3] If total - target occurred earlier, the entries after that position add up to the target.
if total - target in first_at:
best = max(best, position - first_at[total - target])
# [4] Record only the first position of a total: the earliest start gives the longest run.
if total not in first_at:
first_at[total] = position
# [5] The length of the longest run, or 0 when there is none.
return bestpublic int longestRun(int[] amounts, int target) {
// [1] A table from each running total to the first position where it occurred. Position 0 is the empty start.
java.util.HashMap<Long, Integer> firstAt = new java.util.HashMap<>();
firstAt.put(0L, 0);
long total = 0;
int best = 0;
for (int position = 1; position <= amounts.length; position++) {
// [2] The running total after reading this many entries.
total += amounts[position - 1];
// [3] If total - target occurred earlier, the entries after that position add up to the target.
if (firstAt.containsKey(total - target)) {
best = Math.max(best, position - firstAt.get(total - target));
}
// [4] Record only the first position of a total: the earliest start gives the longest run.
if (!firstAt.containsKey(total)) {
firstAt.put(total, position);
}
}
// [5] The length of the longest run, or 0 when there is none.
return best;
}int longestRun(vector<int>& amounts, int target) {
// [1] A table from each running total to the first position where it occurred. Position 0 is the empty start.
unordered_map<long long, int> firstAt;
firstAt[0] = 0;
long long total = 0;
int best = 0;
for (int position = 1; position <= (int)amounts.size(); position++) {
// [2] The running total after reading this many entries.
total += amounts[position - 1];
// [3] If total - target occurred earlier, the entries after that position add up to the target.
auto it = firstAt.find(total - target);
if (it != firstAt.end()) {
best = max(best, position - it->second);
}
// [4] Record only the first position of a total: the earliest start gives the longest run.
if (!firstAt.count(total)) {
firstAt[total] = position;
}
}
// [5] The length of the longest run, or 0 when there is none.
return best;
}function longestRun(amounts, target) {
// [1] A table from each running total to the first position where it occurred. Position 0 is the empty start.
const firstAt = new Map([[0, 0]]);
let total = 0;
let best = 0;
for (let position = 1; position <= amounts.length; position++) {
// [2] The running total after reading this many entries.
total += amounts[position - 1];
// [3] If total - target occurred earlier, the entries after that position add up to the target.
if (firstAt.has(total - target)) {
best = Math.max(best, position - firstAt.get(total - target));
}
// [4] Record only the first position of a total: the earliest start gives the longest run.
if (!firstAt.has(total)) {
firstAt.set(total, position);
}
}
// [5] The length of the longest run, or 0 when there is none.
return best;
}Finance asks for the longest stretch of entries where payments and refunds cancel out, so the net is 0. The entries are [3, -3, 5, -2, -3, 2, 4].
This is Template 2 with target = 0. The table starts with the total 0 at position 0.
| Position | Entry | Running total | Looks up (total − 0) | First seen at | Length | Best |
|---|---|---|---|---|---|---|
| 1 | 3 | 3 | 3 | not seen: store position 1 | 0 | |
| 2 | −3 | 0 | 0 | position 0 | 2 | 2 |
| 3 | 5 | 5 | 5 | not seen: store position 3 | 2 | |
| 4 | −2 | 3 | 3 | position 1 | 3 | 3 |
| 5 | −3 | 0 | 0 | position 0 | 5 | 5 |
| 6 | 2 | 2 | 2 | not seen: store position 6 | 5 | |
| 7 | 4 | 6 | 6 | not seen: store position 7 | 5 |
The result is 5: the first five entries, 3, -3, 5, -2, -3, add up to 0. The table kept the first position of the total 0, so the run starts at the very beginning.
Complexity in plain words#
- Time. The pass reads each entry once and makes one lookup and at most one insert. With a hash table that stays roomy, each costs one step on average. So n entries cost O(n).
- Worst case. If many totals share one bucket, each lookup walks a long chain, and the pass degrades towards O(n^2). A good hash and a resizing table make this unlikely.
- Space. The table holds up to n + 1 different totals: O(n).
- Size. Running totals can reach 10^5 entries × 10^6 each, which is 10^11. That needs a 64-bit integer. The count of runs can reach about 5 × 10^9, which needs one too.
- Trade. The streak scan uses O(1) extra space and O(n^2) time. The table uses O(n) space and O(n) time. At 100,000 entries, the table turns 5 × 10^9 additions into about 200,000 operations.
5. Stretch: edges, mistakes and variations#
Edge cases#
Real production data brings edge cases.
Before the first entry, amounts = []. The loop never runs, and the template returns 0: there are no runs. A target that no streak reaches, such as [2, 2, 2] with target 7, also returns 0.
For [1, -1, 1] with target 0, the answer is 2: the streaks [1, -1] and [-1, 1]. Look up before you store. If the new total were stored first, the lookup of total - 0 would find the total that this entry has made, and a streak of no entries would count.
For [0, 0, 0] with target 0, every streak adds up to 0, so the answer is 6: three of one entry, two of two entries and one of three. A ledger of 100,000 zeros gives 5,000,050,000 runs, which needs a 64-bit integer.
For [-3, 1, -2, 4] with target -2, the running totals are 0, −3, −2, −4, 0. The answer is 2: the streak [-3, 1] and the single entry [-2]. The template needs no special case, because total - target works for negative numbers too.
The mistake museum#
This version starts with an empty table.
Counterexample: amounts = [5], target = 5. After the first entry, the total is 5 and the lookup is for 0. The table is empty, so the bug returns 0. The streak [5] begins at the first entry, so the right answer is 1.
Start the table with the total 0 once.
The classic bug: start with an empty table, and every streak that begins at the first entry is missed.
This version adds the new total to the table first, and then looks up total - target.
Counterexample: amounts = [3], target = 0. The bug stores the total 3, looks up 3, finds the total it has stored, and returns 1. No streak adds up to 0, so the right answer is 0.
Look first, store afterwards.
A tempting method grows a window to the right and shrinks it from the left while the total is above the target. It works when entries are never negative. With negative entries, a longer window can have a smaller total.
Counterexample: amounts = [1, -3, 2, 5, 3, -3], target = 5. The window finds [1, -3, 2, 5]. At total 8 it shrinks from the left, but removing −3 raises the total, so it drops entries that later streaks need. It returns 1, and the right answer is 4.
A window needs entries that are not negative. The table does not.
A sliding window fails with negative entries: removing a negative entry raises the total, so the window drops entries that later streaks need.
This version keeps a set of the totals seen, instead of how often each occurred. A total that occurred twice still counts once.
Counterexample: amounts = [3, -3, 3, -3], target = 0. The running totals are 0, 3, 0, 3, 0. The set version finds 3 runs, and the right answer is 4. The total 0 occurred three times, and the last entry ends two runs.
When the question asks how many, store how often.
When the pattern does not apply#
Your team lead asks for the streaks that add up to at least 100 units, or at most 100. Many different totals qualify, and one lookup finds one exact total. The table cannot answer a question about a range.
If every entry is positive, a window works. With negative entries, counting such streaks needs the running totals kept in sorted order, and the shortest one needs a monotonic deque. Both are different tools. The table is for an exact total.
Product variations#
Your team lead brings four product changes. Each one asks what to store for each running total, or how to change the entries.
Finance wants the longest streak that adds up to the target, not the number of streaks. Store the first position of each running total, and keep the largest gap. This is Template 2.
A platform team wants the streaks whose total is a multiple of the shard count k. Two running totals differ by a multiple of k exactly when they leave the same remainder. So the table counts remainders instead of totals, still seeded with the remainder 0 once (LeetCode 974: Subarray Sums Divisible by K).
Negative totals need care, because % differs between languages. For a running total of −7 and k = 3:
| Language | -7 % 3 |
A remainder from 0 to k − 1 |
|---|---|---|
| Python | 2 | total % k is one already |
| Java | −1 | Math.floorMod(total, k), or ((total % k) + k) % k |
| C++ | −1 | ((total % k) + k) % k |
| JavaScript | −1 | ((total % k) + k) % k |
Java, C++ and JavaScript keep the sign of the total, so −7 gives −1 while the total 2, which leaves the same remainder, gives 2. Unfixed, the two never meet in the table. With [-1, 5] and k = 5, the totals −1 and 4 should match for the streak [5], and the unfixed code returns 0 instead of 1.
A video app wants the longest stretch with as many thumbs up as thumbs down. Count a thumbs up as +1 and a thumbs down as −1, and look for the longest stretch with total 0 (LeetCode 525: Contiguous Array).
A banking app explains a change in a balance with the fewest consecutive days whose changes add up to exactly that amount. Store the latest position of each running total, so the streak that ends at the current position is as short as possible. For "at least the amount", one lookup is not enough. With negative changes, the shortest such streak needs the running totals in a monotonic deque (LeetCode 862), a different tool.
Why this matters in real systems#
6. Say: lock it in#
Explain it back#
Explain it back: write the idea in your own words and get feedback.
In two or three sentences, explain to a teammate how you count the streaks that add up to a target in one pass. Then explain why the table must start with the total 0 once. The AI tutor checks your answer against the invariant and the key points of this lesson.
Here is how you could explain it in an interview, now that you have built it.
I keep a running total. A streak that ends here adds up to the target when an earlier running total equals the current total minus the target.
I keep a map from each running total to how often it occurred, and I add the count of the total I look for.
I start the map with the total 0 once, and I look up before I store. One pass, O(n) time, O(n) space.
The 60-second interview answer#
The straightforward answer adds up every streak, which is O(n^2). I can count the streaks in one pass with a hash map.
I keep a running total. The sum of any streak is the difference of two running totals. So a streak that ends at the current entry adds up to the target when an earlier running total equals the current total minus the target.
I keep a map from each running total to how often it occurred. For each entry, I add the count of the total I look for, and then I record the current total. The map starts with the total 0 once, for streaks that begin at the first entry.
Each lookup is O(1) on average, so the pass is O(n) time and O(n) space. It works with negative entries, where a sliding window does not. I use 64-bit integers for the totals and the count.
Checkpoint#
Checkpoint · Running totals
Q1/3 The entries are
[2, 5, -1, 4]. What are the running totals, counting the empty start?Answer & explanation
Answer: C
The empty start has total 0. Then 0 + 2 = 2, 2 + 5 = 7, 7 − 1 = 6 and 6 + 4 = 10. Forgetting the minus sign gives 8 and 12.
Q2/3 The running total before a run is 3, and after the run it is 8. What is the total of the run?
Answer & explanation
Answer: B
The total of a run is the difference of two running totals: 8 − 3 = 5.
Q3/3 The target is 5, and the current running total is 12. Which earlier running total would end a run that adds up to 5 at this entry?
Answer & explanation
Answer: C
The earlier total must be the current total minus the target: 12 − 5 = 7. Adding instead of subtracting gives 17, a common slip.
Checkpoint · The table
Q1/4 Why does the table start with the running total 0 seen once?
Answer & explanation
Answer: B
A run that begins at the first entry has a start position before any entry, whose running total is 0. Without it in the table, that run is never counted.
Q2/4 The entries are
[5]and the target is 5. What does a table that starts empty return?Answer & explanation
Answer: B
After the entry, the total is 5 and the lookup is for 0. An empty table has nothing, so the code returns 0. The right answer is 1.
Q3/4 Why does the code look up before it stores the current running total?
Answer & explanation
Answer: C
With
[3]and target 0, storing first puts 3 in the table, and the lookup of 3 − 0 finds it. The code returns 1, but no run adds up to 0.Q4/4 The entries are
[3, -3, 3, -3]and the target is 0. How many runs add up to 0?Answer & explanation
Answer: C
The running totals are 0, 3, 0, 3, 0. The total 0 occurs 3 times, which makes 3 pairs, and the total 3 occurs twice, which makes 1 pair. That is 4 runs. Counting each total once gives 3.
Checkpoint · Where it works
Q1/3 Why does a sliding window fail on
[1, -3, 2, 5, 3, -3]with target 5?Answer & explanation
Answer: B
A window shrinks when the total is above the target. With negative entries, removing an entry can raise the total, so the window drops entries that later runs need. It finds 1 run, and the right answer is 4.
Q2/3 Which question needs the first position of each running total in the table?
Answer & explanation
Answer: B
The earliest start gives the longest run, so the table keeps the first position. The shortest run needs the latest position, and a count needs how often.
Q3/3 A ledger has 100,000 entries, and each entry is at most 10^6 in size. Why do the running totals need a 64-bit integer?
Answer & explanation
Answer: C
The largest running total is 100,000 × 10^6 = 10^11. A 32-bit integer stops at 2,147,483,647, so the total would overflow.
Ten questions on this lesson. Pass with 80% or more, and solve the checkpoint's two mixed problems, to open the gate to the next stretch on the Academy map. The two problems are "Bucket the events by hour" and "Runs with a sum divisible by k".
Practice ladder#
| Step | Problem | Product line | Level | What it practises |
|---|---|---|---|---|
| 1 | Streaks that sum to the target | Pay | Medium | The running-total table with counts, and negative entries |
| 2 | Subarrays divisible by the shard count | Platform | Medium | The remainder of a running total, counted in one pass |
| 3 | Shortest run that adds up to the target | Bank | Medium | The latest position of a running total |
Review cards#
Review cards from this lesson.
Five cards from this lesson join your spaced-review deck. The first one comes back tomorrow.