Prefix Sums and Hashing Checkpoint
A review of this module. Skip it if you feel confident; the next module does not need it.
Fix the mistakes
The slips that cost marks in this module. Spot each one, then check the fix.
This checkpoint mixes everything from the module on orders, stock and exam data. Name the pattern first, state the brute force and its cost, then write the better version.
Decide by the question
Offline processing means you know all updates and queries before you start, so you can batch them. A difference array needs it. A prefix sum needs the data to stay fixed while you query.
Every problem in this module is solved by remembering something about earlier items. The wording of the question tells you what to remember.
clues = { "total between two positions, many times": "prefix sums", "add to a range, read at the end": "difference array", "have I seen this value?": "set or dict", "block of items with sum k": "prefix sums + dict",}for question, tool in clues.items(): print(f"{question} -> {tool}")Example 1 · Two quick lookups
ids = [105, 220, 317, 220]print(len(set(ids)) != len(ids))
prices = [8, 3, 11, 5]seen = set()found = Falsefor p in prices: if 14 - p in seen: found = True seen.add(p)print(found)True True
What this code does
- A set answers "any repeat?" and "is the partner here?" in one pass each.
- The partner check comes before the add, so an item never pairs with itself.
Always state the brute force first and its cost, then the trick, then the new cost.
Updates first, then queries
A difference array applies all range updates cheaply. A prefix sum then answers range queries on the result. Together they handle a whole day of shelf changes and reports.
from itertools import accumulate
diff = [0] * 7for low, high, units in [(0, 3, 5), (2, 5, 2)]: diff[low] += units diff[high + 1] -= unitsstock = list(accumulate(diff))[:6]prefix = list(accumulate(stock, initial=0))print(stock)print(prefix[6] - prefix[2])Example 2 · Updates, then several range queries
from itertools import accumulate
diff = [0] * 7for low, high, units in [(0, 3, 5), (2, 5, 2)]: diff[low] += units diff[high + 1] -= unitsstock = list(accumulate(diff))[:6]prefix = list(accumulate(stock, initial=0))print(stock)for low, high in [(0, 5), (2, 3), (4, 5)]: print(low, high, prefix[high + 1] - prefix[low])[5, 5, 7, 7, 2, 2] 0 5 28 2 3 14 4 5 4
What this code does
- The first accumulate turns the edits into stock levels. The second builds the prefix list.
- Each query is one subtraction, however long the range.
Cost: O(u) for updates, O(n) to rebuild twice, then O(1) per query.
A hash map for the rest
When the question is about equal prefixes or earlier partners, keep a dictionary. Count blocks with sum k by looking up prefix - k.
from collections import Counter
def count_k(items, k): seen = Counter({0: 1}) prefix = count = 0 for x in items: prefix += x count += seen[prefix - k] seen[prefix] += 1 return count
print(count_k([2, 4, 3, 2, 5], 9))Example 3 · Pairs and blocks with the same total
from collections import Counter
def count_k(items, k): seen = Counter({0: 1}) prefix = count = 0 for x in items: prefix += x count += seen[prefix - k] seen[prefix] += 1 return count
items = [4, 6, 2, 8, 2]seen = Counter()pairs = 0for x in items: pairs += seen[10 - x] seen[x] += 1print(pairs)print(count_k(items, 10))3 3
What this code does
- Pairs of positions with sum 10 are counted with a Counter of earlier values: (4, 6) and (2, 8) twice.
- Blocks of consecutive items with sum 10 use prefix sums: [4, 6], [2, 8] and [8, 2].
O(n) time and space. It works for negative numbers, unlike a sliding window.
Module quiz
Questions from the whole module. Your first answer is your score.
Problems
Graded easy to hard, using everything from this module.
Try each one yourself first. Use the hint if you get stuck. Mark it as done when it works.
Exercise 1· Easy
For items = [4, 1, 7, 3, 9, 2], print the sum of the items at indexes 2 to 4 using a prefix list.
19
Exercise 2· Easy
Print True if two different numbers in [8, 3, 11, 5] add up to 14, otherwise False.
True
Exercise 3· Medium
A list of five zeros gets the updates (0, 2, 3) and (1, 4, 2) as (low, high, amount). With a difference array, print the final list, then the sum of the items at indexes 1 to 3.
[3, 5, 5, 2, 2] 12
Exercise 4· Medium
Print the number of anagram groups in ["act", "cat", "tac", "dog", "god", "bird"].
3
Exercise 5· Medium
Print how many blocks of consecutive items in [1, 2, 3, 4, 5] have sum 9.
2
Exercise 6· Hard
Exam results are [1, 1, 0, 0, 1, 0, 1, 1], where 1 is pass and 0 is fail. Print the length of the longest run of consecutive exams with equally many passes and fails.
6
Exercise 7· Hard
Sessions are [(8, 10), (9, 12), (11, 13), (12, 14)] as (start, end), and the end hour is free again. Print the largest number of sessions at the same time, and the first hour when it happens, separated by a space.
2 9
Exercise 8· Hard
Count the pairs of positions i < j in [3, 5, 7, 9, 1, 11] whose sum is divisible by 4. Print the count.
9
Interview questions
Questions interviewers ask on this topic.
Finish up
Mark complete & continue
Next: Must-do problems: Prefix Sums and Hashing