Prefix, Pairs and Slope
What is this?
A hash map answers "have I seen this?" instantly. The difficulty at this level is that the thing worth asking about is never the thing you were given. You are handed numbers and asked about divisibility, handed points and asked about collinearity, handed words and asked about palindromes. In each case there is a derived quantity that makes the question a single lookup, and finding it is most of the problem.
Fun fact: the remainder trick rests on a small piece of modular arithmetic. If two prefix sums leave the same remainder when divided by
k, their difference is a multiple ofk, and that difference is the subarray between them. So a question about every possible subarray collapses into "have I seen this remainder before?", and fork != 0the map never holds more thankentries, however long the array is.
🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Core idea: derive a key that makes the question trivial (remainder, reduced fraction, reversed word) and store that. The hash map is never the insight; the transformation into it is.
1. Remainder, not sum
seen = {0: -1} # key -> earliest index it appeared at
running = 0
for i, x in enumerate(nums):
running += x
if k != 0:
running %= k # k == 0: keep the raw prefix (see below)
if running in seen:
if i - seen[running] >= 2: # the subarray must be at least two long
return True
else:
seen[running] = i # FIRST occurrence only
Three details carry it. The first is that the map stores the earliest index for each remainder, because a later one can only produce a shorter subarray, and this problem demands length at least two. The second is that seen = {0: -1} seeds the empty prefix, so a subarray starting at index 0 is counted. The third is k = 0: you cannot take % 0, and the only multiple of 0 is 0, so you key on the raw prefix sum and a repeat means a span that sums to exactly zero.
In Java, C++ and JavaScript % can return a negative, so in those languages normalise with ((x % k) + k) % k before using it as a key. Python's % already returns a non-negative result for positive k.
2. Fractions, not floats
For each pivot point, key every other point by the slope between them, but as a reduced fraction, never a division:
dy, dx = y2 - y1, x2 - x1
g = gcd(dy, dx) or 1
dy, dx = dy // g, dx // g
if dx < 0 or (dx == 0 and dy < 0): # normalise the sign
dy, dx = -dy, -dx
key = (dy, dx)
The sign normalisation matters as much as the reduction: (1, 2) and (-1, -2) are the same direction and must hash to the same key. Vertical lines give dx == 0 and horizontal dy == 0, both handled by the same code once the sign rule covers them.
3. Reversed words, and the split
For palindrome pairs, index every word by its reverse. Then for each word, split it at every position into left and right:
- if
leftis a palindrome and the reverse ofrightexists, that word can go after the found one; - if
rightis a palindrome and the reverse ofleftexists, it can go before.
That is L + 1 splits per word and one lookup each. Each split also costs O(L) for the palindrome check and the reversed slice, so the total is O(n · L²) time and O(n · L) space for the map, against O(n² · L) time for comparing every pair. The empty string is the case to state explicitly: "" pairs with every word that is itself a palindrome, in both orders. The double-count to guard against is different: two equal-length words that are exact reverses (abc and cba) are reachable from both the empty-prefix split and the empty-suffix split, so run the suffix branch only when the suffix is non-empty.
4. A 30-second worked example
nums = [23, 2, 4, 6, 7], k = 6:
The remainder 5 also appears at index 3, but the map kept index 0, the earliest, which is what makes the length check meaningful.
5. Where you'll actually meet this
- Rolling totals. "Is there a stretch of consecutive days whose net count is an exact multiple of the pallet size?" Any "does some window land on a multiple of
k" question has this shape. - Exact geometry keys. With integer coordinates, a reduced
(dy, dx)pair compares directions exactly. Methods such as RANSAC and the Hough transform fit lines to noisy real-valued data, and this exact version is the toy form of the same question: which direction has the biggest group? - Canonical keys. Grouping anagrams by their sorted letters is the same move: compute a canonical form, then hash it.
- Transformed-key lookup. When the partner of an item is a transform of it (its reverse, its complement), hash every item once and look up the transform instead of scanning all pairs.
6. Problems in this chapter
Continuous Subarray Sum
Is there a subarray of length at least two summing to a multiple of k? Store each running remainder's earliest index; a repeat with a gap of two or more is the answer. k = 0 keys on the raw prefix instead.
Pattern: remainder-keyed prefix map. Target: O(n) time, O(min(n, k)) space for k != 0, O(n) for k = 0.
Max Points on a Line
The most points sharing a straight line. Fix each point as a pivot and key the others by a gcd-reduced, sign-normalised slope, and count duplicates of the pivot separately. The brute force over pairs is O(n³) and needs the same duplicate care.
Pattern: exact-fraction slope map. Target: O(n²) time, O(n) space.
Palindrome Pairs
Every pair of words whose concatenation is a palindrome. Index the words reversed, then split each word at every position and look up the complement.
Pattern: reversed-word index + split. Target: O(n · L²) time, O(n · L) space, against O(n² · L) time and O(L) extra space for the brute force. A trie of reversed words has the same O(n · L²) worst case.
7. Common pitfalls
- Storing the latest index rather than the earliest. It silently breaks any minimum-length requirement.
- Forgetting the
{0: -1}seed, which drops every subarray starting at index 0. - Negative remainders.
-7 % 6is not5in every language; normalise before keying. k = 0.% 0crashes. The question becomes "is there a length 2 or longer subarray summing to zero", so key on the raw prefix sum (and the map can then hold up tonkeys).- Floating-point slopes. Collinear points disagree at the fifteenth decimal and the count comes back short.
- Skipping sign normalisation.
(1,2)and(-1,-2)are the same line and must produce the same key. - Duplicate points in the slope problem: they lie on every line through the pivot and must be counted separately, not keyed. Without that, the
(0, 0)slope breaksgcdand the brute-force cross-product test reports every point as collinear. - Emitting a palindrome pair twice. Exact reverses of equal length (
abc,cba) match at both the empty-prefix and empty-suffix splits. Skip the empty-suffix split in the suffix branch. The empty string itself pairs in both orders, which is correct, not a duplicate.
8. Key takeaways
- Derive the key. Remainder, reduced fraction, reversed word. The input never hands it to you.
- Two equal prefix remainders bracket a divisible subarray. That identity is the whole first problem.
- Earliest index, always, when length is part of the question.
- Exact beats approximate. Reduce with
gcdand normalise the sign rather than dividing. - Reversing the data reverses the question: a suffix problem becomes a prefix lookup.
- Handle the degenerate cases explicitly: zero modulus, duplicate points, empty strings, equal-length reverses.
- Why interviewers like it: the map is assumed. What they are watching is whether you can name the derived quantity and then defend it against modulus, sign and precision.
Order: Continuous Subarray Sum → Max Points on a Line → Palindrome Pairs.
Max Points on a Line
Core idea: A straight line is fixed by a point and a direction. So fix one point as the anchor and compute the slope from the anchor to every other point. Points with the same slope lie on one line through the anchor, so the biggest slope bucket plus the anchor itself is the best line through that anchor. Repeat with every point as the anchor and take the global max. The trap that sinks naive solutions is representing the slope as a float:
1/3computed two ways can compare unequal. Use the reduced integer pair(dy/g, dx/g)withg = gcd(dy, dx)and a fixed sign convention as an exact, hashable key. Vertical lines (dx = 0) fall out of this for free, and duplicate points (dx = dy = 0) get their own counter. Total cost is O(n²).
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson