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 the entire 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 of k — and that difference is the subarray between them. So a question about every possible subarray collapses into "have I seen this remainder before?", and the map never grows beyond k entries no matter how long the array is.

🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line 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}                 # remainder -> earliest index it appeared at
running = 0
for i, x in enumerate(nums):
    running = (running + x) % k
    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

Two details carry it. 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. And seen = {0: -1} seeds the empty prefix, so a subarray starting at index 0 is counted.

In languages where % can return a negative, normalise with ((x % k) + k) % k before using it as a key.

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 left is a palindrome and the reverse of right exists, that word can go after the found one;
• if right is a palindrome and the reverse of left exists, it can go before.

That is L + 1 splits per word and one lookup each — O(n · L²) in total, against O(n² · L) for comparing every pair. The empty-string case is the one to state explicitly: a word paired with "" works in both directions when the word is itself a palindrome, and it is easy to emit that pair twice.

4. A 30-second worked example

nums = [23, 2, 4, 6, 7], k = 6:

index        0    1    2    3    4
value       23    2    4    6    7
running     23   25   29   35   42
mod 6        5    1    5    5    0

seen: {0:-1, 5:0, 1:1}
at index 2 the remainder 5 repeats (first seen at index 0)
   → 2 - 0 = 2, which is >= 2  ✓  subarray [2, 4] sums to 6

Note 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

• Financial reconciliation. Finding a run of entries that nets to a multiple of some unit, used to match balancing transactions.
• Computer vision and GIS. Collinearity and vanishing-point detection over point sets, where exact rational slopes avoid the float problem entirely.
• Search infrastructure. Reverse indexes for suffix and palindrome lookup; the same structure powers "words ending in".
• Data deduplication. Canonical keys — reduced, normalised, sorted — decide when two differently-shaped records are the same.
• Hash-based cycle detection. Remainder keys appear wherever a value space needs to be folded into a bounded map.

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.
Pattern: remainder-keyed prefix map. Target: O(n) time, O(min(n, k)) space.

▶ 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.
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.

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 % 6 is not 5 in every language; normalise before keying.
• k = 0. The modulus problem needs an explicit guard — the question becomes "is there a subarray summing to zero".
• 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.
• Emitting the empty-string palindrome pair twice — once from each direction.

8. Key takeaways

1. Derive the key. Remainder, reduced fraction, reversed word — the input never hands it to you.
2. Two equal prefix remainders bracket a divisible subarray. That identity is the whole first problem.
3. Earliest index, always, when length is part of the question.
4. Exact beats approximate. Reduce with gcd and normalise the sign rather than dividing.
5. Reversing the data reverses the question — a suffix problem becomes a prefix lookup.
6. Handle the degenerate cases explicitly: zero modulus, duplicate points, empty strings.
7. 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.