</> MAANG.io

Advanced

Advanced problems where modelling is the hard part: implicit graphs, tricky DP states, intervals and design challenges.

0 of 95 solved 0%

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.

Chalkboard flowchart: make it one lookup - divisible by k stores running sum mod k, same line stores a reduced-fraction slope, palindrome stores every word reversed

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 for k != 0 the map never holds more than k entries, 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 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. 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:

Chalkboard worked example table: value, running sum, and running-sum-mod-6 rows; remainder 5 repeats at index 0 and index 2, so subarray [2,4] sums to 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 % 6 is not 5 in every language; normalise before keying.
  • k = 0. % 0 crashes. 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 to n keys).
  • 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 breaks gcd and 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

  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, equal-length reverses.
  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.

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.