What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

0. Math & Geometry Foundation • Invariant Proof & Speed-Run

Theory Context•Math & Geometry

Conceptual Foundation & Intuitive Analogy

🧭 Conceptual Foundation & Pattern Intuition

Traversing an $M \times N$ 2D matrix in spiral order is not about calculating complex geometric curves or calculating trigonometric trajectories. It is an exercise in Rectangular Boundary Contraction. Four boundary walls—top, bottom, left, right—define the unvisited rectangular domain. Traversal proceeds along the active perimeter, and as each side is completed, its boundary wall is shifted inward monotonically.

🏟️ The Analogy: Peeling an Onion, Layer by Layer

Imagine peeling an onion with flat, rectangular layers. You slice off the top outer skin (traverse left to right), slice off the right skin (traverse top to bottom), shave off the bottom skin (traverse right to left), and finally peel up the left skin (traverse bottom to top). What remains inside is another smaller, pristine rectangular onion. You repeat this peeling cycle until nothing remains.

🔑 Why It Works

Notice the crucial safety checks if top <= bottom and if left <= right before the backward passes! For non-square matrices (e.g., $1 \times 4$ or $3 \times 1$ ), the first two sweeps contract the boundary past the opposing wall. Without these guards, the backward loops would re-traverse already visited cells, creating duplicate elements.

Visual Blueprint & State Transition Model

Math & Geometry Mental Model Diagram — Figure 1 • Math & Geometry Core Invariant & State Lifecycle

Core Invariant Specification

Boundary pointers (top, bottom, left, right) contract inward monotonically after each directional sweep.

Boundary Model: 4-Pointer Boundary Box Contraction [top, bottom, left, right]

Boundary pointers contract inward after each directional sweep; modular arithmetic bounds state cyclically.

Loop Invariant Termination

while top <= bottom and left <= right: sweep right, down, left, up, contracting respective pointer.

The 11 Mental Models of Math and Geometry

Categorize math problems by their spatial or arithmetic invariant before writing code.

1Digit Manipulation

integer x ➔ digit modulo extraction ➔ overflow clamp

Integer Overflow Handling & Digit Manipulation

Spot it when: You must return 0 or clamp when the result leaves the 32-bit range, or you build, reverse or parse a number one digit at a time.

Mode 1 · Digit Manipulation

Python

1	def reverse_integer(x: int) -> int:
2	"""Reverses digits of a 32-bit signed integer with overflow detection.
3	Time: O(log10 \|x\|) \| Space: O(1)
4	"""
5	INT_MAX = 2**31 - 1 # 2147483647
6	INT_MIN = -2**31 # -2147483648
7
8	# 1. Normalize the Sign:
9	# Python's % and // round toward minus infinity, so working on a
10	# negative x directly would misbehave; the sign is split off and reapplied at the end.
11	sign = -1 if x < 0 else 1
12	x = abs(x)
13	res = 0 # digits of x, read from the right, rebuilt in reverse order
14
15	# 2. Peel Off and Append One Digit at a Time:
16	# x % 10 reads the last digit and x //= 10 drops it; appending that
17	# digit to res with res * 10 + digit builds the reversed number one digit per step.
18	while x > 0:
19	digit = x % 10
20	x //= 10
21
22	# 3. Detect Overflow Before It Happens:
23	# res * 10 + digit must stay within INT_MAX; checking res against
24	# INT_MAX // 10 first catches the overflow before the multiply can occur.
25	if res > INT_MAX // 10 or (res == INT_MAX // 10 and digit > 7):
26	return 0
27
28	res = res * 10 + digit
29
30	# 4. Reapply the Sign and the Final Range Check:
31	# The sign set aside in step 1 is multiplied back in, then the result
32	# is re-checked against the full signed range in case that flipped it out of bounds.
33	res *= sign
34	return res if INT_MIN <= res <= INT_MAX else 0

Treat a number as a row of digits: x % 10 reads the last digit, x //= 10 drops it, and res = res * 10 + digit appends a digit on the right, so any number can be taken apart and rebuilt one digit at a time without turning it into a string. Each step moves exactly one digit, so reading from the right while appending builds the digits in reverse order, as reverse_integer does; the same two moves, in other orders, compare a number with its mirror, add numbers stored as digit arrays or parse text into a number. Work on abs(x) and put the sign back at the end, because in Python % and // round toward minus infinity for negatives (-7 % 10 == 3). The trap is overflow: test res > INT_MAX // 10 (or res == INT_MAX // 10 and digit > 7) before res * 10 + digit, because with fixed-width integers the multiply itself overflows: Java silently wraps the value around, and in C++ signed overflow is undefined behavior.

Gotchas1 of 3

The trap
Gotcha 1: Checking the 32-bit limit after res * 10 + digit
Mistake
```
res = res * 10 + digit
if res > INT_MAX:
    return 0
```
Fix
```
if res > INT_MAX // 10 or (res == INT_MAX // 10 and digit > 7):
    return 0
res = res * 10 + digit
```
What happens: In Java or C++, res is a 32-bit integer. res * 10 + digit can go past INT_MAX, which is 2^31 - 1. Java then wraps the value around, and in C++ signed overflow is undefined behavior. A check after the multiply only sees the wrapped value. For x = 1534236469, the true reverse is 9646324351, and Java's wrapped value is 1056389759. That value is below INT_MAX, so the late check lets it through. Python ints never overflow, so in Python both orders return 0. The check before the multiply is the one that works in every language.
Gotcha 2: Using % and // on a negative x
Mistake
```
while x != 0:  # x is still negative
    digit = x % 10
    x //= 10
```
Fix
```
sign = -1 if x < 0 else 1
x = abs(x)
```
What happens: In Python, % and // round toward minus infinity. So -7 % 10 is 3, and -7 // 10 is -1. On a negative x, x //= 10 stops at -1 and never reaches 0. The blueprint works on abs(x) and puts the sign back at the end.
Example: x = -123
Mistake: the loop never endsFix: returns -321
Gotcha 3: Reversing the digits through a string
Mistake
```
return int(str(x)[::-1])
```
Fix
```
digit = x % 10
x //= 10
res = res * 10 + digit
```
What happens: str(-123)[::-1] is '321-', with the minus sign at the end. So int(str(x)[::-1]) raises ValueError on a negative x. The string version also still needs the 32-bit check. The digit loop handles the sign and the check in one pass.
Example: x = -123
Mistake: raises ValueErrorFix: returns -321

Canonical LeetCode:Reverse Integer (LC 7)Palindrome Number (LC 9)Multiply Strings (LC 43)Plus One (LC 66)String to Integer (atoi) (LC 8)Prime Palindrome (LC 866)Subtract the Product and Sum of Digits of an Integer (LC 1281)Check if Number is a Sum of Powers of Three (LC 1780)Add Binary (LC 67)

Open the Digit Manipulation card

2Spiral Matrix

grid (R x C) ➔ top/bottom/left/right ➔ inward spiral

Spiral Matrix Traversal (Layer-by-Layer Boundary Shrinking)

Spot it when: You must walk a matrix ring by ring: spiral order, filling a spiral, rotating layers.

Mode 2 · Spiral Matrix

Python

1	def spiral_order(matrix: list[list[int]]) -> list[int]:
2	"""Spiral Matrix: read the matrix ring by ring with four boundaries.
3	Time: O(R * C) \| Space: O(1) auxiliary
4	"""
5	if not matrix or not matrix[0]:
6	return []
7
8	top, bottom = 0, len(matrix) - 1
9	left, right = 0, len(matrix[0]) - 1
10	result: list[int] = []
11
12	while top <= bottom and left <= right:
13	# 1. Sweep Top (Left -> Right)
14	for c in range(left, right + 1):
15	result.append(matrix[top][c])
16	top += 1
17
18	# 2. Sweep Right (Top -> Bottom)
19	for r in range(top, bottom + 1):
20	result.append(matrix[r][right])
21	right -= 1
22
23	# 3. Sweep Bottom (Right -> Left) with Guard!
24	if top <= bottom:
25	for c in range(right, left - 1, -1):
26	result.append(matrix[bottom][c])
27	bottom -= 1
28
29	# 4. Sweep Left (Bottom -> Top) with Guard!
30	if left <= right:
31	for r in range(bottom, top - 1, -1):
32	result.append(matrix[r][left])
33	left += 1
34
35	return result

Walk the matrix one ring at a time with four boundaries, top, bottom, left and right, that close in from all four sides like converging pointers, and move each boundary inward right after its side is read. Each boundary marks the first row or column not yet read on its side, so after the four sweeps the unread cells form a smaller rectangle and the same sweeps repeat on it. The trap is the last, thin ring: after the top and right sweeps there may be no row or no column left, so guard the bottom sweep with if top <= bottom and the left sweep with if left <= right, or a single row such as [[1,2,3]] returns [1,2,3,2,1].

Gotchas1 of 4

The trap
Gotcha 1: Leaving out the if top <= bottom guard
Mistake
```
for c in range(right, left - 1, -1):
    result.append(matrix[bottom][c])
bottom -= 1
```
Fix
```
if top <= bottom:
    for c in range(right, left - 1, -1):
        result.append(matrix[bottom][c])
    bottom -= 1
```
What happens: After the top sweep and the right sweep, the rows may be used up. For [[1,2,3]], the top sweep reads row 0 and sets top to 1, while bottom is 0. Without the guard, the bottom sweep reads row 0 again, backwards. The left sweep needs if left <= right for the same reason.
Example: matrix = [[1, 2, 3]]
Mistake: returns [1, 2, 3, 2, 1]Fix: returns [1, 2, 3]
Gotcha 2: Forgetting top += 1 after the top sweep
Mistake
```
for c in range(left, right + 1):
    result.append(matrix[top][c])
```
Fix
```
for c in range(left, right + 1):
    result.append(matrix[top][c])
top += 1
```
What happens: top marks the first row that is not read yet. The right sweep starts at row top. Without top += 1, the right sweep reads the top-right corner a second time. Later sweeps then read other cells twice as well.
Example: matrix = [[1, 2], [3, 4]]
Mistake: returns [1, 2, 2, 4, 3, 1]Fix: returns [1, 2, 4, 3]
Gotcha 3: Writing range(right, left, -1) in the bottom sweep
Mistake
```
for c in range(right, left, -1):
```
Fix
```
for c in range(right, left - 1, -1):
```
What happens: range stops before its end value. range(right, left, -1) stops before column left, so the bottom sweep skips it. For [[1,2],[3,4]], the value 3 is never read. The left sweep has the same kind of bound, range(bottom, top - 1, -1).
Example: matrix = [[1, 2], [3, 4]]
Mistake: returns [1, 2, 4]Fix: returns [1, 2, 4, 3]
Gotcha 4: Looping range(right - left + 1) when rotating a ring
Mistake
```
for i in range(right - left + 1):
```
Fix
```
for i in range(right - left):
```
What happens: In Rotate Image (LC 48), each ring can be turned in place. For each i in range(right - left), four cells move one side along, through one saved value. A side has right - left + 1 cells, but its last cell is the first cell of the next side. With range(right - left + 1), each corner moves twice.
Example: matrix = [[1, 2], [3, 4]]
Mistake: returns [[4, 3], [2, 1]]Fix: returns [[3, 1], [4, 2]]

Canonical LeetCode:Spiral Matrix (LC 54)Spiral Matrix II (LC 59)Rotate Image (LC 48)Spiral Matrix IV (LC 2326)Cyclically Rotating a Grid (LC 1914)

Open the Spiral Matrix card

3Fast Power

base x, exponent n ➔ halve exponent repeatedly ➔ O(log N) power

Fast Power (Exponentiation by Squaring)

Spot it when: The exponent can be huge (up to

10^9

or more), or the answer is a repeated product 'modulo

10^9 + 7

Mode 3 · Fast Power

Python

1	def my_pow(x: float, n: int) -> float:
2	"""Binary Exponentiation: computes x^n by squaring.
3	Time: O(log N) \| Space: O(1)
4	"""
5	if n < 0:
6	x = 1.0 / x # x^-n == (1/x)^n
7	n = -n
8
9	result = 1.0
10	curr_product = x # Holds x^(2^i) for the current bit i
11
12	while n > 0:
13	if n % 2 == 1:
14	result *= curr_product # Bit is set: multiply this power in
15	curr_product *= curr_product # Square for the next bit
16	n //= 2 # Move to the next bit
17
18	return result

Write n in binary: x^13 = x^8 · x^4 · x^1, so only the powers x^1, x^2, x^4, ... are ever needed. curr_product squares once per bit, and result takes it in only when the current bit of n is 1 (n % 2 == 1). It is correct because result * curr_product ** n stays equal to the original x ** n every round, and the loop ends with n = 0. The trap is a negative n: flip first with x = 1 / x and n = -n (in Java or C++ copy n into 64 bits first, since -n overflows for -2³¹).

Gotchas1 of 4

The trap
Gotcha 1: Negating n without replacing x by 1 / x
Mistake
```
if n < 0:
    n = -n
```
Fix
```
if n < 0:
    x = 1.0 / x
    n = -n
```
What happens: For a negative n, x ** n equals (1 / x) ** -n. The loop only handles n >= 0. With n = -n alone, it computes x ** -n. So my_pow(2.0, -2) returns 4.0 instead of 0.25.
Example: x = 2.0, n = -2
Mistake: returns 4.0Fix: returns 0.25
Gotcha 2: Negating n in a 32-bit int in Java or C++
What happens: In Java or C++, n can be -2^31, the smallest 32-bit int. Its negative, 2^31, does not fit in 32 bits. In Java, -n gives -2^31 again, and in C++ it is undefined behavior. Copy n into a 64-bit variable, such as a Java long, before n = -n.
Gotcha 3: Reducing modulo MOD only at the end
Mistake
```
result *= curr_product
curr_product *= curr_product
```
Fix
```
result = result * curr_product % MOD
curr_product = curr_product * curr_product % MOD
```
What happens: This problem has no modulus, but many counting problems ask for the answer modulo MOD, such as 10^9 + 7. Without % MOD after each multiplication, the numbers grow to many digits. In Python the answer is still correct, but every multiplication gets slower. In Java or C++, a 64-bit value overflows. Python's built-in pow(base, exp, MOD) runs the same loop and reduces after each step.
Gotcha 4: Subtracting after pow(2, n, MOD) without adding MOD back
Mistake
```
return pow(2, n, MOD) - 2
```
Fix
```
return (pow(2, n, MOD) - 2 + MOD) % MOD
```
What happens: pow(2, n, MOD) is already reduced, so it can be smaller than 2. For n = 500000003 and MOD = 10**9 + 7, it is exactly 1. Subtracting 2 then gives -1. Count Collisions of Monkeys on a Polygon (LC 2550) returns this difference, so it needs the fix. Add MOD before the final % MOD, because in Java and C++ % of a negative number stays negative.
Example: n = 500000003, MOD = 10**9 + 7
Mistake: returns -1Fix: returns 1000000006

Canonical LeetCode:Pow(x, n) (LC 50)Count Good Numbers (LC 1922)Count Collisions of Monkeys on a Polygon (LC 2550)Maximize Number of Nice Divisors (LC 1808)Super Pow (LC 372)

Open the Fast Power card

4In-Place Marking

matrix ➔ markers in the first row / column or spare bits ➔ apply in a second pass

In-Place Markers (First Row/Column Flags, Two States per Cell)

Spot it when: The input must be changed in place with O(1) extra memory, but each change depends on the input as it was: rows or columns to wipe, or a new state that every neighbour must still read in its old form.

Mode 4 · In-Place Marking

Python

1	def set_zeroes(matrix: list[list[int]]) -> None:
2	"""Set Matrix Zeroes: row 0 and column 0 hold the flags for the other rows and columns.
3	Time: O(M * N) \| Space: O(1)
4	"""
5	m, n = len(matrix), len(matrix[0])
6
7	# 1. Save Row 0's and Column 0's Own Zeros First:
8	# Pass 1 below overwrites row 0 and column 0 with flags, so whether
9	# they originally held a zero must be recorded before any flag is written.
10	first_row_zero = any(matrix[0][c] == 0 for c in range(n))
11	first_col_zero = any(matrix[r][0] == 0 for r in range(m))
12
13	# 2. Mark Flags in Row 0 and Column 0:
14	# A zero found inside the matrix (outside row 0 and column 0) means its
15	# whole row and column end up zero, so that is recorded by zeroing the
16	# row's cell in column 0 and the column's cell in row 0.
17	for r in range(1, m):
18	for c in range(1, n):
19	if matrix[r][c] == 0:
20	matrix[r][0] = 0
21	matrix[0][c] = 0
22
23	# 3. Apply the Flags to Every Inner Cell:
24	# Any inner cell whose row flag or column flag is set is zeroed; row 0
25	# and column 0 themselves are skipped here because they still need to be read.
26	for r in range(1, m):
27	for c in range(1, n):
28	if matrix[r][0] == 0 or matrix[0][c] == 0:
29	matrix[r][c] = 0
30
31	# 4. Clear Row 0 and Column 0 Last:
32	# Row 0 and column 0 are cleared only after every other cell has read
33	# their flags; clearing them earlier would turn every flag true and wipe the whole matrix.
34	if first_row_zero:
35	for c in range(n):
36	matrix[0][c] = 0
37	if first_col_zero:
38	for r in range(m):
39	matrix[r][0] = 0

When no extra memory is allowed, store the marks in cells whose final value you already know: a zero at (r, c) means row r and column c end up all zero, so pass 1 writes the flags matrix[r][0] = 0 and matrix[0][c] = 0, and pass 2 zeroes every cell whose row flag or column flag is 0. Writing a flag loses nothing, because both flag cells become zero in the answer anyway; the same idea packs two states into one cell when every neighbour must still read it in its old form, because the old value stays readable until every reader is done, whether that means a whole cell repurposed as a flag or one bit of it holding the next state. The trap is that row 0 and column 0 are data as well as flags: compute first_row_zero and first_col_zero before pass 1 writes any flag, keep both passes to r >= 1 and c >= 1, and clear row 0 and column 0 last, because clearing them first turns every flag to 0 and wipes the whole matrix.

Gotchas1 of 5

The trap

Gotcha 1: Clearing row 0 before pass 2 reads the flags

Mistake

if first_row_zero:
    for c in range(n):
        matrix[0][c] = 0
for r in range(1, m):
    for c in range(1, n):
        if matrix[r][0] == 0 or matrix[0][c] == 0:
            matrix[r][c] = 0

Fix

for r in range(1, m):
    for c in range(1, n):
        if matrix[r][0] == 0 or matrix[0][c] == 0:
            matrix[r][c] = 0
if first_row_zero:
    for c in range(n):
        matrix[0][c] = 0

What happens: After pass 1, row 0 holds the column flags. A 0 at matrix[0][c] means "clear column c". If row 0 is cleared before pass 2, every matrix[0][c] becomes 0. Pass 2 then finds a flag in every column and clears the whole matrix.

Example: matrix = [[0, 1, 2], [3, 4, 5], [6, 7, 8]]

Mistake: returns [[0, 0, 0], [0, 0, 0], [0, 0, 0]]Fix: returns [[0, 0, 0], [0, 4, 5], [0, 7, 8]]

Gotcha 2: Using one flag for both row 0 and column 0
Mistake
```
first_zero = any(matrix[0][c] == 0 for c in range(n)) or any(matrix[r][0] == 0 for r in range(m))
first_row_zero = first_col_zero = first_zero
```
Fix
```
first_row_zero = any(matrix[0][c] == 0 for c in range(n))
first_col_zero = any(matrix[r][0] == 0 for r in range(m))
```
What happens: One shared flag can only say that row 0 or column 0 had a 0. It can't say which one. So a 0 only in column 0 also clears all of row 0. Using matrix[0][0] as that one flag has the same problem, because the cell is in both. The blueprint keeps two booleans, first_row_zero and first_col_zero.
Example: matrix = [[1, 1], [0, 1]]
Mistake: returns [[0, 0], [0, 0]]Fix: returns [[0, 1], [0, 0]]

Gotcha 3: Computing first_row_zero after pass 1 writes the flags

Mistake

for r in range(1, m):
    for c in range(1, n):
        if matrix[r][c] == 0:
            matrix[r][0] = 0
            matrix[0][c] = 0
first_row_zero = any(matrix[0][c] == 0 for c in range(n))

Fix

first_row_zero = any(matrix[0][c] == 0 for c in range(n))
for r in range(1, m):
    for c in range(1, n):
        if matrix[r][c] == 0:
            matrix[r][0] = 0
            matrix[0][c] = 0

What happens: Pass 1 writes 0s into row 0 as column flags. After that, any(matrix[0][c] == 0 ...) can't tell a flag from a 0 that was in the input. It finds a flag and sets first_row_zero to True. The last step then clears all of row 0.

Example: matrix = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]

Mistake: returns [[0, 0, 0], [0, 0, 0], [1, 0, 1]]Fix: returns [[1, 0, 1], [0, 0, 0], [1, 0, 1]]

Gotcha 4: Zeroing row r and column c during the scan
Mistake
```
if matrix[r][c] == 0:
    for k in range(n):
        matrix[r][k] = 0
    for k in range(m):
        matrix[k][c] = 0
```
Fix
```
if matrix[r][c] == 0:
    matrix[r][0] = 0
    matrix[0][c] = 0
```
What happens: Pass 1 scans the cells in order. If it writes 0s into the row and the column at once, the scan meets those new 0s later. It takes them for 0s that were in the input. Each one clears another row and column. The 0s spread to rows and columns that had none.
Example: matrix = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
Mistake: returns [[1, 0, 0], [0, 0, 0], [0, 0, 0]]Fix: returns [[1, 0, 1], [0, 0, 0], [1, 0, 1]]
Gotcha 5: Starting pass 2 at row 0 instead of row 1
Mistake
```
for r in range(m):
    for c in range(1, n):
        if matrix[r][0] == 0 or matrix[0][c] == 0:
```
Fix
```
for r in range(1, m):
    for c in range(1, n):
        if matrix[r][0] == 0 or matrix[0][c] == 0:
```
What happens: Row 0 holds the column flags until pass 2 ends. If pass 2 starts at row 0 and matrix[0][0] == 0, it sets every matrix[0][c] to 0. Every later row then finds a flag in every column and is cleared.
Example: matrix = [[0, 1], [1, 1]]
Mistake: returns [[0, 0], [0, 0]]Fix: returns [[0, 0], [0, 1]]

Canonical LeetCode:Set Matrix Zeroes (LC 73)Game of Life (LC 289)Build Array from Permutation (LC 1920)Candy Crush (LC 723)

Open the In-Place Marking card

5Cross Product

three points ➔ sign of the cross product ➔ left turn, right turn or straight line

Cross Product Orientation Test (Turn Direction, Collinearity, Convexity)

Spot it when: Points with integer coordinates and a question about direction: does a path turn left or right, do three points lie on one line, which side of a line is a point on, is a polygon convex, or how large is a triangle.

Mode 5 · Cross Product

Python

1	def cross(o: list[int], a: list[int], b: list[int]) -> int:
2	"""Orientation test: > 0 when o -> a -> b turns left, < 0 when it turns right, 0 when the points are collinear."""
3	# cross is twice the signed area of triangle o, a, b: its sign alone gives the turn direction.
4	return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
5
6
7	def is_convex(points: list[list[int]]) -> bool:
8	"""Convex Polygon: every turn along the boundary has the same cross-product sign.
9	Time: O(N) \| Space: O(1)
10	"""
11	n = len(points)
12	prev = 0 # prev: the last non-zero turn seen so far; 0 means no turn has been seen yet
13	for i in range(n):
14	# 1. Compute the Turn at the Next Corner:
15	# cross() gives the sign of the turn o -> a -> b in one integer; % n wraps the index, so the
16	# two turns that close the polygon are checked in the same pass as every other corner.
17	turn = cross(points[i], points[(i + 1) % n], points[(i + 2) % n])
18
19	# 2. Classify the Turn (the trap):
20	# A turn of 0 is a straight corner: it is allowed and tells nothing about direction, so it
21	# is skipped before prev is touched. A later non-zero turn with the opposite sign means the
22	# boundary bent back on itself, a dent, so the polygon is not convex.
23	if turn == 0:
24	continue
25	if prev != 0 and (turn > 0) != (prev > 0):
26	return False
27
28	# 3. Remember the Direction:
29	# Save this non-zero turn so the next corner's turn can be compared against it.
30	prev = turn
31	return True

The cross product cross(o, a, b) = (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]) answers "which way does the path o -> a -> b turn?" with one integer: positive for a left (counter-clockwise) turn, negative for a right turn, 0 when the three points lie on one line. A polygon is convex exactly when its boundary always turns the same way, so is_convex computes turn at every corner, wrapping around with % n so the two turns that close the loop are checked too, and returns False the first time a turn's sign differs from prev. This is correct because the value is twice the signed area of the triangle o, a, b: its sign flips exactly when b crosses from one side of the line through o and a to the other, and it uses only integer multiplication and subtraction, so there is no division by zero on a vertical edge and no rounding error. The trap is a turn of 0: three points in a row on one line make a straight corner, which is allowed and says nothing about the direction, so continue past it. Treating it as a change of direction rejects convex polygons that have extra points along an edge, and storing it in prev overwrites the record of which way the boundary was turning, so a dent right after a straight corner slips through.

Gotchas1 of 4

The trap
Gotcha 1: Leaving out if turn == 0: continue
Mistake
```
if prev != 0 and (turn > 0) != (prev > 0):
```
Fix
```
if turn == 0:
    continue
if prev != 0 and (turn > 0) != (prev > 0):
```
What happens: A turn of 0 is a straight corner. It is allowed, and it says nothing about the direction. Without continue, the 0 reaches the sign test. After a right turn, the test passes, and prev = turn sets prev to 0. The last known direction is lost. A dent right after the straight corner is then not caught. After a left turn, the same 0 fails the test, so a convex polygon is rejected.
Example: points = [[6,6],[8,12],[12,12],[12,0],[0,0],[0,12],[4,12],[5,9]]
Mistake: returns TrueFix: returns False
Gotcha 2: Looping range(n - 2) and skipping the two closing turns
Mistake
```
for i in range(n - 2):
```
Fix
```
for i in range(n):
```
What happens: range(n - 2) checks the corners at points[1] to points[n - 2]. The corners at points[n - 1] and points[0] close the loop, and they are never checked. In [[0,0],[0,10],[10,10],[10,0],[5,5]], the dent at [5,5] is one of them. range(n) with % n in the turn line checks all n corners.
Example: points = [[0,0],[0,10],[10,10],[10,0],[5,5]]
Mistake: returns TrueFix: returns False
Gotcha 3: Testing the sign with prev * turn < 0
Mistake
```
if prev * turn < 0:
```
Fix
```
if prev != 0 and (turn > 0) != (prev > 0):
```
What happens: In Python both tests give the same answer. With coordinates up to 10^4, one cross product can reach 8 * 10^8. The product of two cross products can reach 6.4 * 10^17, which overflows a 32-bit integer in Java or C++. Comparing the two signs needs no multiplication.
Gotcha 4: Comparing slopes dy / dx instead of using cross
Mistake
```
(a[1] - o[1]) / (a[0] - o[0]) == (b[1] - a[1]) / (b[0] - a[0])
```
Fix
```
cross(o, a, b) == 0
```
What happens: A vertical edge has dx = 0, so the division raises ZeroDivisionError. With large coordinates, two different slopes can also round to the same float. cross uses only integer multiplication and subtraction. Valid Boomerang (LC 1037) only asks whether one cross is non-zero. Largest Triangle Area (LC 812) is the largest abs(cross(o, a, b)) / 2.
Example: o = [0, 0], a = [0, 5], b = [0, 10]
Mistake: raises ZeroDivisionErrorFix: returns True

Canonical LeetCode:Convex Polygon (LC 469)Check If It Is a Straight Line (LC 1232)Valid Boomerang (LC 1037)Largest Triangle Area (LC 812)

Open the Cross Product card

6Euclid's GCD

two numbers ➔ replace (a, b) by (b, a % b) ➔ greatest common divisor

Euclidean Algorithm (Greatest Common Divisor)

Spot it when: Several whole numbers or lengths must share a divisor: the largest number that divides them all, a block or period two things are both made of, groups of equal size, or a fraction in lowest terms.

Mode 6 · Euclid's GCD

Python

1	def gcd(a: int, b: int) -> int:
2	"""Euclid's algorithm: gcd(a, b) == gcd(b, a % b), and gcd(a, 0) == a."""
3	# 1. Replace the Pair Until It Shrinks to Zero (the trap):
4	# a % b is a minus a multiple of b, so a number dividing both a and b also divides a % b, and a
5	# number dividing b and a % b also divides a: both values must update from the old pair at once.
6	while b:
7	a, b = b, a % b
8	# 2. Return the Answer:
9	# The loop stops once b is 0; since gcd(a, 0) == a, a now holds the greatest common divisor.
10	return a
11
12
13	def find_gcd(nums: list[int]) -> int:
14	"""Find Greatest Common Divisor of Array: Euclid's algorithm on the smallest and largest value.
15	Time: O(N + log M) \| Space: O(1)
16	"""
17	lo, hi = min(nums), max(nums) # lo, hi: the two ends; only they matter, the other values play no part
18	return gcd(hi, lo)

Euclid's algorithm finds the greatest common divisor of two numbers by replacing the pair (a, b) with (b, a % b) until b is 0; then a is the answer. Here find_gcd only needs the smallest and largest value, lo and hi, so it returns gcd(hi, lo). It is correct because a % b is a minus a multiple of b: any number that divides both a and b also divides a % b, and any number that divides b and a % b also divides a, so the pair changes but its common divisors never do. The trap is the update: write a, b = b, a % b as one statement. Updating a = b first makes the next line compute b % b, which is always 0, so the loop stops after one step and returns the smaller number.

Gotchas1 of 4

The trap
Gotcha 1: Writing a = b and then b = a % b
Mistake
```
a = b
b = a % b
```
Fix
```
a, b = b, a % b
```
What happens: After a = b, the old a is gone. The next line computes b % b, which is always 0. The loop stops after one step and returns the old b. So gcd(8, 3) returns 3 instead of 1.
Example: a = 8, b = 3
Mistake: returns 3Fix: returns 1
Gotcha 2: Returning b instead of a after the loop
Mistake
```
return b
```
Fix
```
return a
```
What happens: The loop stops when b is 0, so the pair ends as (g, 0). return b then always returns 0. The rule gcd(x, 0) == x also lets a running gcd start from 0, as in Number of Subarrays With GCD Equal to K (LC 2447).
Example: a = 8, b = 3
Mistake: returns 0Fix: returns 1
Gotcha 3: Using repeated subtraction instead of %
Mistake
```
while b:
    if a >= b:
        a -= b
    else:
        a, b = b, a
```
Fix
```
while b:
    a, b = b, a % b
```
What happens: Subtraction gives the same answer, but it can take a / b steps. For gcd(10**9, 1), that is about 10^9 steps. With %, the number of steps is at most about 2 * log2 of the smaller value.
Gotcha 4: Taking the gcd of all values in nums
Mistake
```
return functools.reduce(gcd, nums)
```
Fix
```
lo, hi = min(nums), max(nums)
return gcd(hi, lo)
```
What happens: Find Greatest Common Divisor of Array (LC 1979) asks for the gcd of only the smallest and the largest value. For [2, 5, 6, 9, 10], that is the gcd of 10 and 2, which is 2. The gcd of all five values is 1. Other problems do take the gcd of every value, such as X of a Kind in a Deck of Cards (LC 914) with its counts.
Example: nums = [2, 5, 6, 9, 10]
Mistake: returns 1Fix: returns 2

Canonical LeetCode:Find Greatest Common Divisor of Array (LC 1979)Greatest Common Divisor of Strings (LC 1071)X of a Kind in a Deck of Cards (LC 914)Number of Subarrays With GCD Equal to K (LC 2447)Check If It Is a Good Array (LC 1250)

Open the Euclid's GCD card

7Canonical Key

integers (a, b) ➔ Euclidean reduction ➔ normalized coprime factors

Canonical-Form Hashing (Normalize Before You Count)

Spot it when: Items must be grouped or counted as equal once they are written in one standard form: points on the same line (the same reduced slope), strings that match after a shift, shapes that match after a move.

Mode 7 · Canonical Key

Python

1	import math
2	from collections import defaultdict
3
4	def max_points_on_line(points: list[list[int]]) -> int:
5	"""Maximum points collinear on a plane using GCD slope hashing.
6	Time: O(N^2) \| Space: O(N)
7	"""
8	# 1. Handle Trivial Inputs:
9	# Any 0, 1, or 2 points are always collinear, so the general counting
10	# below is skipped for those sizes.
11	if len(points) <= 2:
12	return len(points)
13
14	max_pts = 0 # largest count of collinear points found across all anchors
15
16	# 2. Anchor on Each Point in Turn:
17	# slopes counts, for the current anchor points[i], how many later points
18	# share each direction from it; a fresh dict per anchor keeps directions
19	# from different anchors from being mixed into the same count.
20	for i in range(len(points)):
21	slopes: dict[tuple[int, int], int] = defaultdict(int)
22	x1, y1 = points[i]
23
24	for j in range(i + 1, len(points)):
25	x2, y2 = points[j]
26	dx, dy = x2 - x1, y2 - y1
27	g = math.gcd(dx, dy)
28
29	# 3. Reduce the Direction to a Canonical Key:
30	# Dividing dx and dy by their gcd keeps the same direction in
31	# lowest terms, then flipping the sign so dy is positive (or dy
32	# == 0 with dx positive) makes opposite vectors of one line hash alike.
33	slope = (dy // g, dx // g)
34	if slope[0] < 0 or (slope[0] == 0 and slope[1] < 0):
35	slope = (-slope[0], -slope[1])
36
37	# 4. Count and Track the Best Line Through This Anchor:
38	# Every point sharing a key lies on the same line through
39	# points[i]; the + 1 below counts the anchor point itself.
40	slopes[slope] += 1
41	max_pts = max(max_pts, slopes[slope] + 1)
42
43	return max_pts

Before counting, turn each item into a key that is equal exactly when the items should count as equal; here the item is the direction from points[i] to points[j], and its key is (dy // g, dx // g) with g = gcd(dx, dy), sign fixed. Two directions lie on the same line through points[i] exactly when their reduced integer pairs match, and integers compare exactly, so two different directions never share one bucket, as rounded float slopes can when the coordinates are large. The trap is the sign: (1, -2) and (-1, 2) are the same direction, so force dy positive (or dy == 0 with dx positive) before counting slope, or one line is counted as two.

Gotchas1 of 4

The trap
Gotcha 1: Leaving the sign of (dy // g, dx // g) unfixed
Mistake
```
slope = (dy // g, dx // g)
```
Fix
```
slope = (dy // g, dx // g)
if slope[0] < 0 or (slope[0] == 0 and slope[1] < 0):
    slope = (-slope[0], -slope[1])
```
What happens: math.gcd never returns a negative number. So dy // g and dx // g keep the signs of dy and dx. For points = [[0, 0], [1, 1], [-1, -1]], the anchor [0, 0] gives [1, 1] the key (1, 1). It gives [-1, -1] the key (-1, -1), although both points lie on the same line. That one line is then counted in two buckets. The fix flips the pair so that dy is positive, or dy == 0 and dx is positive.
Example: points = [[0, 0], [1, 1], [-1, -1]]
Mistake: returns 2Fix: returns 3
Gotcha 2: Creating slopes once, outside the loop over i
Mistake
```
slopes: dict[tuple[int, int], int] = defaultdict(int)
for i in range(len(points)):
```
Fix
```
for i in range(len(points)):
    slopes: dict[tuple[int, int], int] = defaultdict(int)
```
What happens: A key in slopes is only a direction. It names one line only while every point is measured from the same points[i]. If slopes is shared by all anchors, two parallel lines add to the same count. The fix creates a new, empty slopes for every anchor i.
Example: points = [[0, 0], [1, 0], [5, 5], [6, 5]]
Mistake: returns 3Fix: returns 2
Gotcha 3: Running the blueprint on points that can repeat
Mistake
```
g = math.gcd(dx, dy)
slope = (dy // g, dx // g)
```
Fix
```
if dx == 0 and dy == 0:
    same += 1
    continue
g = math.gcd(dx, dy)
```
What happens: Max Points on a Line (LC 149) promises that all points are different. In a variant with repeated points, a copy of points[i] gives dx = dy = 0. Then math.gcd(0, 0) is 0, and dy // g raises ZeroDivisionError. Count the copies of points[i] in same instead. Add same to the best line through points[i], because a copy lies on every line through it.
Example: points = [[1, 1], [1, 1], [2, 2]]
Mistake: raises ZeroDivisionErrorFix: returns 3
Gotcha 4: Hashing the slope as a float dy / dx
Mistake
```
slope = dy / dx
```
Fix
```
slope = (dy // g, dx // g)
if slope[0] < 0 or (slope[0] == 0 and slope[1] < 0):
    slope = (-slope[0], -slope[1])
```
What happens: A vertical line has dx = 0, so dy / dx raises ZeroDivisionError. Floats also round. With coordinates near 10^8, two different slopes can round to the same float and share one key. For example, 94911150 / 94911151 == 94911151 / 94911152 is True in Python. The reduced integer pair (dy // g, dx // g) has neither problem.
Example: points = [[1, 1], [1, 2], [1, 3]]
Mistake: raises ZeroDivisionErrorFix: returns 3

Canonical LeetCode:Max Points on a Line (LC 149)Number of Distinct Islands (LC 694)Number of Distinct Islands II (LC 711)Group Shifted Strings (LC 249)Number of Equivalent Domino Pairs (LC 1128)Number of Pairs of Interchangeable Rectangles (LC 2001)Toeplitz Matrix (LC 766)Sort the Matrix Diagonally (LC 1329)

Open the Canonical Key card

8Count and Skip

rank k in a huge list in dictionary order ➔ at each slot, skip k // block blocks of equal size (k counted from 0) and keep k % block ➔ the k-th item, built one slot at a time

K-th in Dictionary Order by Block Counting (Unranking, Factorial Number System)

Spot it when: You must return the k-th item of a huge list sorted in dictionary order (the k-th permutation, route, string or number), or the rank of a given item in that list, and the list is far too long to build: k can reach n!, C(30, 15) or 10¹⁵.

Mode 8 · Count and Skip

Python

1	def get_permutation(n: int, k: int) -> str:
2	"""Permutation Sequence: skip whole blocks of arrangements that share the digits chosen so far.
3	Time: O(N^2) \| Space: O(N)
4	"""
5	fact = [1] * n # fact[m] = m!
6
7	# 1. Precompute Factorials:
8	# fact[m] holds m!, the number of arrangements of m items, needed below
9	# to size each slot's blocks without computing a factorial inside the main loop.
10	for m in range(1, n):
11	fact[m] = fact[m - 1] * m
12
13	pool = [str(d) for d in range(1, n + 1)] # unused digits, smallest first
14
15	# 2. Convert the Rank to 0-Based:
16	# k counts from 1, but k // block below needs the count of arrangements
17	# that come strictly before the answer, which is k - 1.
18	k -= 1
19	result = [] # digits of the answer, chosen one slot at a time
20
21	# 3. Choose Each Slot by Skipping Whole Blocks:
22	# Every unused digit starts a block of fact[n - 1 - slot] arrangements
23	# that share the digits chosen so far; dividing k by that block size
24	# finds how many whole blocks come before the answer, and the remainder
25	# becomes the answer's rank inside the chosen block for the next slot.
26	for slot in range(n):
27	block = fact[n - 1 - slot]
28	index = k // block
29	k %= block
30	result.append(pool.pop(index))
31	return "".join(result)

Items in dictionary order come in blocks: every arrangement that starts with the same digit sits together, and here every block at a slot holds the same number of arrangements, block = fact[n - 1 - slot]. So the answer's digit for a slot is found without listing anything: skip index = k // block whole blocks, take pool.pop(index), and continue inside the chosen block with k %= block, one slot to the right and one factorial smaller. This is correct because the blocks come in the same order as their first digits and all have the same size, so exactly index of them lie before the answer, and k % block is the answer's rank inside its own block; removing the used digit from pool keeps the next slot's choices in order. The trap is the rank's base: k counts from 1, so subtract 1 first. Without k -= 1, every k that is a multiple of block picks one block too far: n = 3, k = 3 gives "231" instead of "213".

Gotchas1 of 4

The trap
Gotcha 1: Leaving out k -= 1
Mistake
```
result = []
```
Fix
```
k -= 1
result = []
```
What happens: k counts from 1, but k // block needs the number of arrangements before the answer. That number is k - 1. Without k -= 1, every k that is a multiple of block picks one block too far.
Example: n = 3, k = 3
Mistake: returns '231'Fix: returns '213'
Gotcha 2: Writing fact[n - slot] instead of fact[n - 1 - slot]
Mistake
```
block = fact[n - slot]
```
Fix
```
block = fact[n - 1 - slot]
```
What happens: A block holds the arrangements of the slots after this one. At slot 0 there are n - 1 such slots. So a block there holds (n - 1)! arrangements, which is fact[n - 1]. fact has only n entries, so fact[n - 0] raises IndexError.
Example: n = 3, k = 3
Mistake: raises IndexErrorFix: returns '213'
Gotcha 3: Reading pool[index] instead of pool.pop(index)
Mistake
```
result.append(pool[index])
```
Fix
```
result.append(pool.pop(index))
```
What happens: pool[index] reads the digit but leaves it in pool. The next slot can choose the same digit again, so the answer repeats a digit. pool.pop(index) removes the digit, so the next slot chooses from the unused digits only.
Example: n = 3, k = 3
Mistake: returns '211'Fix: returns '213'
Gotcha 4: Using k // block when blocks have different sizes
What happens: k // block is correct only when every block at a slot holds the same number of arrangements. In K-th Smallest in Lexicographical Order (LC 440), the blocks at one slot differ in size. There, k // block skips the wrong number of arrangements, so it picks the wrong block.

Canonical LeetCode:Permutation Sequence (LC 60)The k-th Lexicographical String of All Happy Strings of Length n (LC 1415)Kth Smallest Instructions (LC 1643)K-th Smallest in Lexicographical Order (LC 440)Minimum Number of Operations to Make String Sorted (LC 1830)Permutations IV (LC 3470)Smallest Palindromic Rearrangement II (LC 3518)

Open the Count and Skip card

9Josephus Problem

circle of n friends ➔ smaller circle's winner ➔ shift by k

Josephus Problem (Circular Elimination Recurrence)

Spot it when: People (or items) stand in a circle and every k-th one is removed until one is left; find who remains without simulating every removal.

Mode 9 · Josephus Problem

Python

1	def find_the_winner(n: int, k: int) -> int:
2	"""Find the Winner of the Circular Game (Josephus): f(size) = (f(size - 1) + k) % size.
3	Time: O(N) \| Space: O(1)
4	"""
5	winner = 0 # 0-indexed winner of the game with 1 friend
6	for size in range(2, n + 1):
7	winner = (winner + k) % size # Shift the smaller game's winner k seats
8	return winner + 1 # Friends are numbered from 1

Once the first friend leaves, the rest is the same game with one friend fewer, only started k seats later, so if winner is the answer for size - 1 friends, (winner + k) % size is the answer for size friends, and a loop from size = 2 up to n builds it without simulating anyone leaving. It is correct because removing the k-th friend and restarting from the next seat is exactly a shift of the smaller circle by k seats, and % size wraps that shift around the larger circle. The trap is the index base: the rule counts seats from 0, so start from winner = 0 for one friend and add 1 only in the final return, because the friends are numbered from 1.

Gotchas1 of 4

The trap
Gotcha 1: Returning winner without adding 1
Mistake
```
return winner
```
Fix
```
return winner + 1
```
What happens: The recurrence counts seats from 0. So winner = 0 is the only seat when one friend is left. Find the Winner of the Circular Game (LC 1823) numbers the friends from 1. Only the final return adds 1.
Example: n = 5, k = 2
Mistake: returns 2Fix: returns 3
Gotcha 2: Wrapping with % n instead of % size
Mistake
```
winner = (winner + k) % n
```
Fix
```
winner = (winner + k) % size
```
What happens: At each step, the circle has size friends, not n. The shift of k seats happens in that smaller circle, so the wrap must use % size. With % n, winner can point past the last seat of the current circle.
Example: n = 5, k = 2
Mistake: returns 4Fix: returns 3
Gotcha 3: Simulating the circle with list.pop
Mistake
```
people = list(range(1, n + 1))
i = 0
while len(people) > 1:
    i = (i + k - 1) % len(people)
    people.pop(i)
return people[0]
```
Fix
```
winner = 0
for size in range(2, n + 1):
    winner = (winner + k) % size
return winner + 1
```
What happens: The simulation gives the same answer, and it passes the limits of Find the Winner of the Circular Game (LC 1823). Each pop(i) shifts the later friends, so the simulation takes O(N^2) time and O(N) space. The recurrence takes O(N) time and O(1) space.
Gotcha 4: Looping range(2, n) instead of range(2, n + 1)
Mistake
```
for size in range(2, n):
```
Fix
```
for size in range(2, n + 1):
```
What happens: range stops before its end value. So range(2, n) stops at a circle of n - 1 friends. It returns the winner of that smaller game.
Example: n = 5, k = 2
Mistake: returns 1Fix: returns 3

Canonical LeetCode:Find the Winner of the Circular Game (LC 1823)Elimination Game (LC 390)

Open the Josephus Problem card

10Sieve of Eratosthenes

upper bound n ➔ boolean sieve array ➔ prime count

Sieve of Eratosthenes

Spot it when: You need to know which of many numbers up to a known limit are prime (counting primes, pairing primes, checking many values), not just one number.

Mode 10 · Sieve of Eratosthenes

Python

1	def count_primes(n: int) -> int:
2	"""Sieve of Eratosthenes: counts primes strictly below n.
3	Time: O(N log log N) \| Space: O(N)
4	"""
5	if n <= 2:
6	return 0 # No primes below 2
7
8	is_prime = [True] * n
9	is_prime[0] = is_prime[1] = False # 0 and 1 are not prime
10
11	for p in range(2, int(n ** 0.5) + 1): # Factors above sqrt(n) were already crossed out
12	if is_prime[p]:
13	for multiple in range(p * p, n, p): # Start at p*p: smaller multiples have a smaller factor
14	is_prime[multiple] = False
15
16	return sum(is_prime)

A number is composite exactly when it has a prime factor no larger than its square root, so cross off multiples only for primes p up to sqrt(n). Start each crossing at p * p: every smaller multiple p * k with k < p was already crossed off by a smaller prime factor of k. Whatever is still True in is_prime is prime. The trap is 0 and 1: they start True like every slot, but no crossing ever reaches them, so set both to False first or the count comes out 2 too high.

Gotchas1 of 5

The trap
Gotcha 1: Leaving is_prime[0] and is_prime[1] as True
Mistake
```
is_prime = [True] * n
```
Fix
```
is_prime = [True] * n
is_prime[0] = is_prime[1] = False
```
What happens: Every slot starts True. Crossing out starts at p * p, which is at least 4. So no step ever reaches 0 or 1. Without the line, sum(is_prime) counts 0 and 1 as primes, and the count is 2 too high.
Example: n = 10
Mistake: returns 6Fix: returns 4
Gotcha 2: Making the table [True] * (n + 1)
Mistake
```
is_prime = [True] * (n + 1)
```
Fix
```
is_prime = [True] * n
```
What happens: Count Primes (LC 204) counts the primes strictly less than n. With n + 1 slots, the table also has a slot for n itself. The loop range(p * p, n, p) stops before n, so that slot is never crossed out. sum(is_prime) then counts n as a prime, even when it is not. The same definition explains if n <= 2: return 0, because no prime is less than 2.
Example: n = 10
Mistake: returns 5Fix: returns 4
Gotcha 3: Stopping p at int(n ** 0.5) without the + 1
Mistake
```
for p in range(2, int(n ** 0.5)):
```
Fix
```
for p in range(2, int(n ** 0.5) + 1):
```
What happens: range stops before its end value. Without + 1, p never takes the value int(n ** 0.5) itself. For n = 10, that value is 3, so 9 is never crossed out. Any end above the square root is correct. Looping p up to n also works, but it is slower.
Example: n = 10
Mistake: returns 5Fix: returns 4
Gotcha 4: Starting the crossing at 2 * p instead of p * p
Mistake
```
for multiple in range(2 * p, n, p):
```
Fix
```
for multiple in range(p * p, n, p):
```
What happens: Every multiple p * k with k < p has a prime factor smaller than p. That smaller prime already crossed it out. Starting at 2 * p crosses those numbers out again. The count is the same, and only the time grows.
Gotcha 5: Building a sieve to test only one or two numbers
What happens: The sieve fills a table of n slots, so it costs O(n log log n) time and O(n) space. To test one number x, trial division by every value up to the square root of x is simpler. The sieve pays off when you test many numbers below n.

Canonical LeetCode:Count Primes (LC 204)Prime Arrangements (LC 1175)Prime Subtraction Operation (LC 2601)Prime Pairs With Target Sum (LC 2761)

Open the Sieve of Eratosthenes card

11Reservoir Sampling

stream of items ➔ keep each with chance 1/i ➔ one uniform random item

Reservoir Sampling & Randomized Pick

Spot it when: A uniform random pick from a list or stream you can read only once, often of unknown length and with no room to copy it: every element must come back with the same chance.

Mode 11 · Reservoir Sampling

Python

1	import random
2	from typing import Optional
3
4
5	class ListNode:
6	def __init__(self, val: int = 0, next: Optional["ListNode"] = None):
7	self.val = val
8	self.next = next
9
10
11	class Solution:
12	"""Linked List Random Node: reservoir sampling, one pass per pick and O(1) extra space.
13	Time: O(N) per getRandom \| Space: O(1)
14	"""
15
16	def __init__(self, head: Optional[ListNode]):
17	self.head = head # Keep only the head: every pick walks the list again
18
19	def getRandom(self) -> int:
20	result, i = 0, 0 # result: the current pick; i: nodes seen so far
21	node = self.head
22	while node:
23	# 1. Count This Node:
24	# i must count node before the draw, so the first node is always taken (randrange(1) is 0).
25	i += 1
26
27	# 2. Draw With Chance 1/i:
28	# randrange(i) is one of 0..i - 1, so it lands on 0 with chance exactly 1/i; every earlier
29	# node then keeps its own share, since it survives this draw with chance (i - 1)/i.
30	if random.randrange(i) == 0:
31	result = node.val
32
33	# 3. Move to the Next Node:
34	# The same draw repeats at every node until the whole list has been walked once.
35	node = node.next
36	# 4. Return the Last Survivor:
37	# After the last node every node has had chance exactly 1/n, with no copy of the list ever made.
38	return result

Reservoir sampling picks a uniform random node in one pass without knowing the length: walk the list, count the nodes with i, and let the i-th node replace result with chance exactly 1/i, drawn as random.randrange(i) == 0. It is fair because the shares stay equal at every step: the new node gets in with 1/i, and each earlier node, which was result with chance 1/(i - 1), survives the draw with (i - 1)/i, which leaves it at 1/i too; after the last node every node has chance 1/n, with no copy of the list. The trap is the chance: i must count the current node before the draw, so the first node is always taken (randrange(1) is 0). randrange(i + 1), a chance of 1/(i + 1), keeps the head only half the time and can leave result at its starting 0, and returning at the first successful draw always returns the head.

Gotchas1 of 3

The trap
Gotcha 1: Drawing randrange(i + 1) instead of randrange(i)
Mistake
```
if random.randrange(i + 1) == 0:
```
Fix
```
if random.randrange(i) == 0:
```
What happens: i += 1 already counts the current node, so node i must win with chance 1/i. The head then wins with chance 1/1, so it is always kept first. With randrange(i + 1), the head wins only half the time. For the list [1, 2], each of 0, 1 and 2 is returned in one third of the calls. The 0 is result's starting value, which is not in the list.
Example: head = [1, 2], the set of values from 100 calls
Mistake: returns [0, 1, 2]Fix: returns [1, 2]
Gotcha 2: Returning at the first successful draw
Mistake
```
if random.randrange(i) == 0:
    return node.val
```
Fix
```
if random.randrange(i) == 0:
    result = node.val
```
What happens: The first node's draw is randrange(1), which is always 0. So the first draw always succeeds. Returning there gives the head on every call. The loop must keep walking, so later nodes can replace result.
Example: head = [1, 2], the set of values from 100 calls
Mistake: returns [1]Fix: returns [1, 2]
Gotcha 3: Choosing the random node once, in __init__
Mistake
```
def getRandom(self) -> int:
    return self.pick  # drawn once in __init__
```
Fix
```
def getRandom(self) -> int:
    result, i = 0, 0
    node = self.head
```
What happens: Each call to getRandom must be a new draw. A value chosen once in __init__ is returned on every call. So every call gives the same value.
Example: head = [1, 2], the set of values from 100 calls
Mistake: returns [1]Fix: returns [1, 2]

Canonical LeetCode:Linked List Random Node (LC 382)Random Pick Index (LC 398)

Open the Reservoir Sampling card

The Math & Geometry Decision Rule

When facing an unseen mathematical or geometric problem, ask in this order:

Step 1.Does the problem parse strings to integers, reverse digits, or risk 32-bit wrap?

➔ Digit Manipulation

Reverse Integer (LC 7)Palindrome Number (LC 9)

Validate bounds before res = res * 10 + digit.

Step 2.Must items count as equal once written in one standard form (reduced slopes, sorted letters, shapes shifted to the origin)?

➔ Canonical Key

Max Points on a Line (LC 149)Number of Distinct Islands (LC 694)

Build the key first, e.g. (dy // g, dx // g) with g = gcd(dx, dy) and one fixed sign, then count keys in a dict.

Step 3.Must the input change in place with O(1) extra memory, while each change depends on the values as they were?

➔ In-Place Marking

Set Matrix Zeroes (LC 73)Game of Life (LC 289)

Record the changes in the first row and column (or in spare bits of each cell), then apply them in a second pass.

Step 4.Does the problem walk a matrix ring by ring (spiral order, filling a spiral, rotating layers)?

➔ Spiral Matrix

Spiral Matrix (LC 54)Spiral Matrix II (LC 59)

Establish top, bottom, left, right bounds and contract clockwise.

Step 5.Do people stand in a circle with every k-th one removed until one is left?

➔ Josephus Problem

Find the Winner of the Circular Game (LC 1823)Elimination Game (LC 390)

f(1) = 0 and f(n) = (f(n - 1) + k) % n; the winner is f(n) + 1 in 1-based numbering.

Step 6.Does the problem need which of many numbers up to a limit are prime?

➔ Sieve of Eratosthenes

Count Primes (LC 204)Prime Arrangements (LC 1175)

Precompute a boolean prime table in O(N log log N), crossing out multiples from p * p.

Step 7.Does the problem involve huge powers or a repeated product modulo 10^9 + 7?

➔ Fast Power

Pow(x, n) (LC 50)Count Good Numbers (LC 1922)

Halve the exponent each iteration: x^n = (x^2)^(n/2), times x when n is odd, in O(log N).

Step 8.Must several whole numbers or lengths share their largest common divisor (a common block, equal groups, a reduced fraction)?

➔ Euclid's GCD

Find Greatest Common Divisor of Array (LC 1979)Greatest Common Divisor of Strings (LC 1071)

gcd(a, b) = gcd(b, a % b) until b == 0; fold it over the whole list.

Step 9.Is the question about direction between points: a left or right turn, collinearity, convexity or a triangle's area?

➔ Cross Product

Convex Polygon (LC 469)Check If It Is a Straight Line (LC 1232)

cross = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x): positive is a left turn, zero is collinear.

Step 10.Must you pick uniformly at random from a list or stream you can read only once?

➔ Reservoir Sampling

Linked List Random Node (LC 382)Random Pick Index (LC 398)

Keep the i-th item (1-based) with probability 1 / i: replace the pick when randrange(i) == 0.

Step 11.Must you return the k-th item of a huge list sorted in dictionary order (the k-th permutation, string or route), or the rank of an item in it, without building the list?

➔ Count and Skip

Permutation Sequence (LC 60)The k-th Lexicographical String of All Happy Strings of Length n (LC 1415)

Set k -= 1 so k counts from 0. At each slot, every choice starts a block of the same size, block (fact[n - 1 - slot] for permutations): take choice number k // block, then k %= block is the rank inside that block. For the rank of a given item, add (unused choices before its digit) * block at each slot, then add 1.

Pattern Architecture & Invariant Design Masterclass

Mathematical and geometric problems model continuous spaces using discrete structures. Invariants such as 4-pointer inward contraction for spiral matrices, greatest common divisor (GCD) reduction for normalized slope vectors, and 32-bit overflow guard checks ensure exact simulation without floating-point drift.

The invariants to say out loud:

4-Boundary Box: "After traversing the top row and right column, I must verify top <= bottom and left <= right before reversing direction back across bottom and left."
Coprime Slopes: "Never compare floating-point slopes. Reduce displacement vectors by gcd(dx, dy) and store coprime integer pairs."

🔬 Variable Anatomy: The 7 Variables Every Math & Geometry Solution Uses

To connect abstract geometric invariants with concrete Python syntax, here is the universal code anatomy showing what every variable does:

Code / Blueprint

import math
from collections import defaultdict
 
def mathGeometryMasterTemplate(
    matrix: list[list[int]],
    points: list[list[int]],
    n: int
) -> tuple[list[int], int, int]:
    # =========================================================================
    # 1. THE 4-BOUNDARY COORDINATE POINTERS
    # =========================================================================
    top, bottom = 0, len(matrix) - 1      # ↕️ Vertical Boundary Bounds
    left, right = 0, len(matrix[0]) - 1   # ↔️ Horizontal Boundary Bounds
    spiral_res = []
 
    # =========================================================================
    # 2. 4-POINTER PERIMETER CONTRACTION (SPIRAL MATRIX)
    # =========================================================================
    while top <= bottom and left <= right:
        # Top row: left -> right
        for c in range(left, right + 1):
            spiral_res.append(matrix[top][c])
        top += 1
 
        # Right col: top -> bottom
        for r in range(top, bottom + 1):
            spiral_res.append(matrix[r][right])
        right -= 1
 
        # Bottom row: right -> left (Guarded against single row)
        if top <= bottom:
            for c in range(right, left - 1, -1):
                spiral_res.append(matrix[bottom][c])
            bottom -= 1
 
        # Left col: bottom -> top (Guarded against single col)
        if left <= right:
            for r in range(bottom, top - 1, -1):
                spiral_res.append(matrix[r][left])
            left += 1
 
    # =========================================================================
    # 3. GCD REDUCED FRACTION SLOPE HASHING
    # =========================================================================
    slope_counts = defaultdict(int)
    if points:
        x1, y1 = points[0]
        for x2, y2 in points[1:]:
            dx = x2 - x1
            dy = y2 - y1
            if dx == 0 and dy == 0:
                continue
            g = math.gcd(dx, dy)
            reduced_slope = (dy // g, dx // g)  # ⚡ Coprime integer slope key
            if reduced_slope[0] < 0 or (reduced_slope[0] == 0 and reduced_slope[1] < 0):
                reduced_slope = (-reduced_slope[0], -reduced_slope[1])
            slope_counts[reduced_slope] += 1
 
    # =========================================================================
    # 4. 32-BIT OVERFLOW GUARD & DIGIT EXTRACTION
    # =========================================================================
    INT_MAX = 2**31 - 1
    INT_MIN = -2**31
    rev = 0
    temp_n = n
    sign = -1 if temp_n < 0 else 1
    temp_n = abs(temp_n)
 
    while temp_n > 0:
        digit = temp_n % 10
        temp_n //= 10
        # ⚠️ CRITICAL: Check overflow BEFORE multiplying
        if rev > (INT_MAX - digit) // 10:
            rev = 0
            break
        rev = rev * 10 + digit
 
    reversed_int = sign * rev
 
    return spiral_res, max(slope_counts.values(), default=0), reversed_int

Variable Role Reference:

Variable	Role in Code	Question It Answers	❌ What Happens If Omitted or Mismanaged?
`top` / `bottom`	Row boundary pointers	"What is the active vertical range of unvisited cells?"	❌ Without contracting `top += 1` / `bottom -= 1`, rows are traversed multiple times.
`left` / `right`	Col boundary pointers	"What is the active horizontal range of unvisited cells?"	❌ Omitting `if top <= bottom` before bottom sweep repeats middle rows on non-square matrices.
`dx` / `dy`	Coordinate delta	"What is the displacement between two geometric points?"	❌ Subtracting in inconsistent order `(x1 - x2)` vs `(x2 - x1)` inverts vector direction.
`g` (`gcd`)	Greatest common divisor	"What factor reduces `(dy, dx)` to its unique coprime ratio?"	❌ Using floating-point division `dy / dx` introduces precision errors where distinct slopes collide in hash keys.
`INT_MAX`	32-bit clamp threshold	"Will `rev 10 + digit` exceed 32-bit signed integer capacity?"*	❌ Checking overflow after multiplying triggers runtime integer wrap/overflow in fixed-width languages.
`digit`	`x % 10`	"What is the current least significant base-10 digit?"	❌ In Python, negative `% 10` returns positive; in C++/Java it returns negative, breaking parity.
`exp`	Binary power exponent	"Can we halve the exponent to reduce power calculation to $O(\log N)$ ?"	❌ Iterating $N$ times for $x^N$ times out on large exponents ( $N = 2^{31} - 1$ ).

🧠 The Universal Contract of Discrete Geometry:

Coprime Slope Contract: Never hash float(dy) / float(dx) due to IEEE 754 precision drift. Always reduce by g = gcd(dx, dy) and hash the integer tuple (dy // g, dx // g). Handle vertical lines (1, 0) and horizontal lines (0, 1) consistently.

Boundary Guard Invariant: When contracting a 2D matrix box, the horizontal and vertical sweeps shrink the space. Always verify top <= bottom and left <= right before initiating the return bottom and left sweeps.

🌟 The 3 Dimensions of Math & Geometry & The Precision-Boundary Invariant

Every Math & Geometry problem is governed by 3 Fundamental Dimensions:

Code / Blueprint

┌─────────────────────────────────────────────────────────────────────────────┐
│                       THE 3 DIMENSIONS OF MATH & GEOMETRY                   │
├───────────────────┬───────────────────────────────────┬─────────────────────┤
│ Dimension         │ Mechanism in Code                 │ Question It Answers │
├───────────────────┼───────────────────────────────────┼─────────────────────┤
│ 1. BOUNDARY       │ Monotonic inward contraction:     │ "How does perimeter │
│    CONTRACTION    │ `top, bottom, left, right`        │ geometry shrink?"   │
├───────────────────┼───────────────────────────────────┼─────────────────────┤
│ 2. ARITHMETIC     │ Coprime reduction `(dy//g, dx//g)`│ "How do we preserve │
│    PRECISION      │ Pre-multiplication overflow guard │ exact equality?"    │
├───────────────────┼───────────────────────────────────┼─────────────────────┤
│ 3. NUMBER THEORY  │ Binary Exponentiation: O(log N)   │ "How do we avoid    │
│    REDUCTION      │ Sieve: O(N log log N)             │ O(N^2) brute force  │
│                   │ instead of trial division         │ operations?"        │
└───────────────────┴───────────────────────────────────┴─────────────────────┘

How this plays out in actual problems:

🟢 Scenario A: Perimeter Box Contraction (Spiral Matrix LC 54)

Traversing a matrix in spiral order naively requires an $O(R \cdot C)$ visited grid.
The Rule: Maintain 4 boundary limits (top = 0, bottom = R-1, left = 0, right = C-1). Traverse top edge (L➔R) and increment top += 1. Traverse right edge (T➔B) and decrement right -= 1. Guard inner reverse sweeps with if top <= bottom and if left <= right.
The Result: Complete traversal in $O(R \cdot C)$ time with $O(1)$ extra space.

🔵 Scenario B: Coprime Slope Hashing (Max Points on a Line LC 149)

Checking if 3 points are collinear by comparing (y2 - y1) / (x2 - x1) == (y3 - y1) / (x3 - x1) fails on vertical lines (divide-by-zero) and floats.
The Rule: Compute g = math.gcd(dx, dy). Normalize signs so dy > 0 (or dy == 0 and dx > 0). Store coprime pairs (dy // g, dx // g) in a hash map.
The Result: Guaranteed zero precision drift across all lines.

🟣 Scenario C: Binary Exponentiation (Pow(x, n) LC 50)

Computing $x^n$ with a loop takes $O(n)$ multiplications, which times out for $n = 2 \times 10^9$ .
The Rule: Halve the exponent each step: if $n$ is even, $x^n = (x^2)^{n/2}$ ; if $n$ is odd, $x^n = x \cdot (x^2)^{(n-1)/2}$ .
The Result: Collapses $2 \times 10^9$ operations to about 31 squarings plus one multiplication per 1-bit of $n$ (at most about 62 multiplications, $O(\log n)$ ).

💡 The Ultimate Takeaway Decision Rule:
When analyzing a math or coordinate problem, ask: "Is this perimeter navigation, slope collinearity, or large arithmetic reduction?"

If Matrix spiral / rotation ➔ 4-Pointer Perimeter Contraction ( $O(R \cdot C)$ ).

If Line collinearity / slopes ➔ Coprime GCD tuple hashing (dy//g, dx//g).

If Large powers or primes ➔ Binary Exponentiation ( $O(\log N)$ ) or Sieve ( $O(N \log \log N)$ ).

If 32-bit digit operations ➔ Pre-multiplication overflow guard rev > (INT_MAX - d) // 10.

🎯 The 4 Essential Math & Geometry Paradigms & Archetypes

Code / Blueprint

┌──────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│                                   THE 4 CORE MATH & GEOMETRY ARCHETYPES                                          │
├────────────────────────┬──────────────────────┬───────────────────────────────┬──────────────────────────────────┤
│ Archetype              │ Coordinate Mechanism │ Exact Arithmetic Invariant    │ Target Problems & Complexity     │
├────────────────────────┼──────────────────────┼───────────────────────────────┼──────────────────────────────────┤
│ 1. Perimeter Contract. │ 4 shrinking bounds   │ Guard reverse sweeps with     │ Spiral Matrix (LC 54), Spiral    │
│    (4-Boundary Box)    │ `top, bottom, L, R`  │ `top <= bottom & left <= right│ Matrix II (LC 59) — O(R * C)     │
├────────────────────────┼──────────────────────┼───────────────────────────────┼──────────────────────────────────┤
│ 2. Coprime GCD Slopes  │ Coordinate deltas    │ `g = gcd(dx, dy)` yields      │ Max Points on a Line (LC 149)    │
│    (Collinear Points)  │ `(x2 - x1, y2 - y1)` │ normalized `(dy//g, dx//g)`   │ — O(N^2)                         │
├────────────────────────┼──────────────────────┼───────────────────────────────┼──────────────────────────────────┤
│ 3. Overflow Surgery    │ Base-10 extraction   │ Check `rev > (MAX - d) // 10` │ Reverse Integer (LC 7), String   │
│    (Digit Reversal)    │ `d = x % 10; x //= 10` before multiplying by 10      │ to Integer atoi (LC 8) — O(log N)│
├────────────────────────┼──────────────────────┼───────────────────────────────┼──────────────────────────────────┤
│ 4. Logarithmic Powers  │ Binary Exponentiation│ $x^n = (x^2)^{n/2}$;          │ Pow(x, n) (LC 50) — O(log N);    │
│    (Sieve & Pow)       │ Sieve crossing $p^2$ │ cross multiples in sieve      │ Count Primes (LC 204) —          │
│                        │                      │                               │ O(N log log N)                   │
└────────────────────────┴──────────────────────┴───────────────────────────────┴──────────────────────────────────┘

🌀 1. 4-Pointer Perimeter Contraction (LC 54 — Spiral Matrix)

Mental Model: Peels rectangular perimeters layer-by-layer like an onion.
Code: see the Spiral Matrix card.

📐 2. Number Theory & GCD Slope Hashing (LC 149)

Mental Model: Points $P_1, P_2, P_3$ share a line if their normalized slope vectors from an anchor point are identical.
Code: see the Canonical Key card.

🔢 3. 32-Bit Integer Overflow Surgery (LC 7)

Mental Model: Reverse digits one by one while verifying that multiplying by 10 will not overflow 32-bit signed integer limits.
Code: see the Digit Manipulation card.

⚡ 4. Binary Exponentiation (LC 50 — Pow(x, n))

Mental Model: Repeated squaring halves the computation size at each step.
Code: see the Fast Power card.

🌳 Evaluating Mathematical Invariants, Modular Arithmetic & Precision Guarantees

Maintaining exactness in mathematical calculations requires understanding computer arithmetic:

1. In-Place Matrix Rotation (Transpose + Reflect)

To rotate an $N \times N$ $N \times N$ matrix 90 degrees clockwise in-place with $O(1)$ $O (1)$ extra space:
1. Transpose: Swap matrix[i][j] with matrix[j][i] for all $j > i$ .
2. Reflect: Reverse each row row.reverse().

2. Guarding Modulo of Negative Numbers

In languages like C++ and Java, -7 % 3 yields -1 rather than 2. To guarantee a non-negative residue, use (x % m + m) % m.

💡 Staff SWE Architectural Invariant:
Avoid floating-point types for discrete geometry comparisons. Always reduce coordinate ratios to coprime integer pairs with GCD to eliminate precision drift across platforms.

Understanding Invariants: Perimeter Contraction & Coprime Slope Precision

Discrete geometry problems eliminate floating-point precision loss by reducing coordinate deltas to coprime integer ratios using GCD, and compress matrix state via 4-pointer perimeter box contraction.

Contracting 4-boundary boxes (top, bottom, left, right) guarantees every cell in a 2D matrix is visited exactly once in O(1) auxiliary space without a visited hash set.

2D Boundary Guard Invariant

Condition: Before traversing bottom row (right to left) or left column (bottom to top)

Action: verify top <= bottom and left <= right

Contracts boundary pointers after top and right sweeps; without guards, non-square matrices re-traverse cells.

Coprime Slope Precision Invariant

Condition: For any slope delta (dy, dx)

Action: hash integer tuple (dy // gcd(dx, dy), dx // gcd(dx, dy)) instead of float(dy / dx)

Prevents IEEE 754 floating-point drift and avoids divide-by-zero crashes on vertical lines.

Common Questions

"In Spiral Matrix, why do the bottom-row and left-column sweeps need an extra if top <= bottom / if left <= right guard, when the top-row and right-column sweeps don't need one?"

Because by the time execution reaches the third and fourth sides of a lap, the first two sides may have already shrunk the remaining region down to a single row or column — and without the guard, that same row or column gets walked a second time, in the opposite direction.

Each full lap peels one layer off the "onion": top row left-to-right (top += 1), right column top-to-bottom (right -= 1), bottom row right-to-left (bottom -= 1), left column bottom-to-top (left += 1). The first two sides are always safe because the loop condition while top <= bottom and left <= right already guaranteed a valid region existed before the lap began. But the first two sides' own pointer updates (top += 1, right -= 1) happen during the lap — so by the time you reach the third side, top may have already passed bottom (this was a single remaining row), or by the fourth side left may have already passed right (a single remaining column).

Without the guard, the bottom-row sweep would re-walk the exact same row the top-row sweep just finished, in reverse — double-counting cells that were already collected. The two guard checks exist purely to detect "this layer has already been fully collapsed to a line by the earlier sides of this same lap" and skip the redundant sweep. It's specific to the third and fourth sides because only they can observe a collapse the first two sides just caused.

Coach discussion points

1.
How do we cleanly represent vertical line slopes where dx == 0 when using the GCD approach?
2.
Explain how coordinate matrix rotation matrix[i][j] maps to matrix[j][n - 1 - i] for a 90-degree clock-wise turn.
3.
Why must dividend == INT_MIN and divisor == -1 be checked before any other arithmetic in Divide Two Integers, rather than after computing abs(dividend)?
4.
Walk through why doubling temp and multiple together in lock-step guarantees the bit-shift doubling algorithm removes at least half of the remaining dividend on every outer loop iteration, bounding total iterations to O(log N).
5.
In Integer to Roman, why does putting the subtractive forms (900=CM, 400=CD, 90=XC, 40=XL, 9=IX, 4=IV) directly into the ordered value/symbol table eliminate the need for any per-digit conditional branching?
6.
What would break if the Integer to Roman value/symbol table were not kept in strictly decreasing order?
7.
For reverse integer, why does Python let you cheat the 32-bit limit naturally, and how do you enforce it algorithmically in Python?
8.
In Set Matrix Zeroes, why may row 0 and column 0 hold the flags at all, and why must first_row_zero and first_col_zero be recorded before the first flag is written and used only after the second pass?
9.
In Convex Polygon, why must a turn of 0 be skipped before it is compared with prev or stored in it, and which two turns does the % n wrap-around add?
10.
In Find Greatest Common Divisor of Array, why do (a, b) and (b, a % b) share every common divisor, and why must a, b = b, a % b update both values in one statement?
11.
In Linked List Random Node, why does keeping the i-th node with chance exactly 1/i leave every node with chance 1/n at the end, and why must i count the current node before the draw?
12.
In Permutation Sequence, why do the arrangements that share a first digit form one block of (n - 1)!, and why must k -= 1 come before k // block?

Complexity analysis

Spiral Matrix: $O(M \times N)$ Time, $O(1)$ Space.
Max Points: $O(N^2)$ Time, $O(N)$ Space.
Reverse Integer: $O(\log_{10} x)$ Time, $O(1)$ Space.
Josephus: $O(N)$ Time, $O(1)$ Space.
Pow(x, n): $O(\log N)$ Time, $O(1)$ Space.
Count Primes: $O(N \log \log N)$ Time, $O(N)$ Space.
Integer to Roman: $O(1)$ Time, $O(1)$ Space (fixed 13-entry table).
Divide Two Integers: $O(\log^2 N)$ Time, $O(1)$ Space.
Set Matrix Zeroes: $O(M \times N)$ Time, $O(1)$ Space (flags in row 0 and column 0).
Convex Polygon: $O(N)$ Time, $O(1)$ Space (one cross product per corner).
Find Greatest Common Divisor of Array: $O(N + \log M)$ Time, $O(1)$ Space (Euclid's remainder steps on the two ends).
Linked List Random Node: $O(N)$ Time per getRandom, $O(1)$ Space (reservoir sampling, one walk per pick).
Permutation Sequence: $O(N^2)$ Time, $O(N)$ Space (Count and Skip: N slots, each with an O(N) pop).

Production Systems Deployment & Motivation

Graphics engines frequently rotate textures or traverse grids spirally to encode image blocks. Collinear points detection is used in computer vision for Hough transforms to detect lines. Overflow checks are critical for low-level banking applications where integer maximums can wrap around to negative numbers, causing catastrophic faults.

Mastery Roadmap & Prerequisite Graph

💡 Don't worry if modular arithmetic or geometric slope hashing feels mathematical right now! Mathematical algorithms exploit algebraic identities and coordinate transformations to avoid exhaustive simulation. As you progress through the Archetype Variants (from Count Primes Sieve and Binary Exponentiation to Spiral Matrix and Max Points on a Line), each hands-on challenge will cement this intuition until guarding integer overflow and applying invariant formulas becomes second nature.

Traversing bottom row or left column when boundaries have crossed: After traversing right and down, top and bottom or left and right may have crossed (e.g. in single-row or single-column matrices). You must verify top <= bottom before traversing left, and left <= right before traversing up.
Allocating visited matrix when 4 boundaries suffice: Maintaining an $M \times N$ visited boolean matrix wastes $O(M \cdot N)$ auxiliary space. Four bounding pointers (top, bottom, left, right) achieve $O(1)$ auxiliary space.
Off-by-one on boundary increments: Forgetting to advance boundaries (top += 1, right -= 1, bottom -= 1, left += 1) causes the traversal to repeat the outer perimeter infinitely.

Staff+ Engineering Perspective

Staff+ Systems Architecture & Hardware Considerations

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

Triggers: "greatest common divisor (GCD)", "prime factorization / sieve", "matrix rotation / spiral traversal", "combinatorics and modular arithmetic". Algebraic equations, modular arithmetic, and discrete coordinate transformations.

CONSTRAINTS & BOUNDS

Values up to $10^{18}$ or matrix dimensions up to $1000 \times 1000$ . Brute-force simulation times out; mathematical closed forms or Euclidean algorithm drop complexity from $O(N)$ to $O(\log(\min(a, b)))$ .

FAANG PRODUCTION TRAPS & EDGE CASES

Integer overflow during multiplication prior to modulo; division in modular arithmetic requiring Fermat's Little Theorem / modular inverse; matrix boundary off-by-one errors during spiral traversals.

Theory Context•Math & Geometry

Conceptual Foundation & Intuitive Analogy

🧭 Conceptual Foundation & Pattern Intuition

🏟️ The Analogy: Peeling an Onion, Layer by Layer

🔑 Why It Works

Visual Blueprint & State Transition Model

Core Invariant Specification

Boundary pointers (top, bottom, left, right) contract inward monotonically after each directional sweep.

Boundary Model: 4-Pointer Boundary Box Contraction [top, bottom, left, right]

Boundary pointers contract inward after each directional sweep; modular arithmetic bounds state cyclically.

Loop Invariant Termination

while top <= bottom and left <= right: sweep right, down, left, up, contracting respective pointer.

The 11 Mental Models of Math and Geometry

Categorize math problems by their spatial or arithmetic invariant before writing code.

1Digit Manipulation

integer x ➔ digit modulo extraction ➔ overflow clamp

Integer Overflow Handling & Digit Manipulation

Spot it when: You must return 0 or clamp when the result leaves the 32-bit range, or you build, reverse or parse a number one digit at a time.

Mode 1 · Digit Manipulation

Python

1	def reverse_integer(x: int) -> int:
2	"""Reverses digits of a 32-bit signed integer with overflow detection.
3	Time: O(log10 \|x\|) \| Space: O(1)
4	"""
5	INT_MAX = 2**31 - 1 # 2147483647
6	INT_MIN = -2**31 # -2147483648
7
8	# 1. Normalize the Sign:
9	# Python's % and // round toward minus infinity, so working on a
10	# negative x directly would misbehave; the sign is split off and reapplied at the end.
11	sign = -1 if x < 0 else 1
12	x = abs(x)
13	res = 0 # digits of x, read from the right, rebuilt in reverse order
14
15	# 2. Peel Off and Append One Digit at a Time:
16	# x % 10 reads the last digit and x //= 10 drops it; appending that
17	# digit to res with res * 10 + digit builds the reversed number one digit per step.
18	while x > 0:
19	digit = x % 10
20	x //= 10
21
22	# 3. Detect Overflow Before It Happens:
23	# res * 10 + digit must stay within INT_MAX; checking res against
24	# INT_MAX // 10 first catches the overflow before the multiply can occur.
25	if res > INT_MAX // 10 or (res == INT_MAX // 10 and digit > 7):
26	return 0
27
28	res = res * 10 + digit
29
30	# 4. Reapply the Sign and the Final Range Check:
31	# The sign set aside in step 1 is multiplied back in, then the result
32	# is re-checked against the full signed range in case that flipped it out of bounds.
33	res *= sign
34	return res if INT_MIN <= res <= INT_MAX else 0

Gotchas1 of 3

The trap
Gotcha 1: Checking the 32-bit limit after res * 10 + digit
Mistake
```
res = res * 10 + digit
if res > INT_MAX:
    return 0
```
Fix
```
if res > INT_MAX // 10 or (res == INT_MAX // 10 and digit > 7):
    return 0
res = res * 10 + digit
```
What happens: In Java or C++, res is a 32-bit integer. res * 10 + digit can go past INT_MAX, which is 2^31 - 1. Java then wraps the value around, and in C++ signed overflow is undefined behavior. A check after the multiply only sees the wrapped value. For x = 1534236469, the true reverse is 9646324351, and Java's wrapped value is 1056389759. That value is below INT_MAX, so the late check lets it through. Python ints never overflow, so in Python both orders return 0. The check before the multiply is the one that works in every language.
Gotcha 2: Using % and // on a negative x
Mistake
```
while x != 0:  # x is still negative
    digit = x % 10
    x //= 10
```
Fix
```
sign = -1 if x < 0 else 1
x = abs(x)
```
What happens: In Python, % and // round toward minus infinity. So -7 % 10 is 3, and -7 // 10 is -1. On a negative x, x //= 10 stops at -1 and never reaches 0. The blueprint works on abs(x) and puts the sign back at the end.
Example: x = -123
Mistake: the loop never endsFix: returns -321
Gotcha 3: Reversing the digits through a string
Mistake
```
return int(str(x)[::-1])
```
Fix
```
digit = x % 10
x //= 10
res = res * 10 + digit
```
What happens: str(-123)[::-1] is '321-', with the minus sign at the end. So int(str(x)[::-1]) raises ValueError on a negative x. The string version also still needs the 32-bit check. The digit loop handles the sign and the check in one pass.
Example: x = -123
Mistake: raises ValueErrorFix: returns -321

Open the Digit Manipulation card

2Spiral Matrix

grid (R x C) ➔ top/bottom/left/right ➔ inward spiral

Spiral Matrix Traversal (Layer-by-Layer Boundary Shrinking)

Spot it when: You must walk a matrix ring by ring: spiral order, filling a spiral, rotating layers.

Mode 2 · Spiral Matrix

Python

1	def spiral_order(matrix: list[list[int]]) -> list[int]:
2	"""Spiral Matrix: read the matrix ring by ring with four boundaries.
3	Time: O(R * C) \| Space: O(1) auxiliary
4	"""
5	if not matrix or not matrix[0]:
6	return []
7
8	top, bottom = 0, len(matrix) - 1
9	left, right = 0, len(matrix[0]) - 1
10	result: list[int] = []
11
12	while top <= bottom and left <= right:
13	# 1. Sweep Top (Left -> Right)
14	for c in range(left, right + 1):
15	result.append(matrix[top][c])
16	top += 1
17
18	# 2. Sweep Right (Top -> Bottom)
19	for r in range(top, bottom + 1):
20	result.append(matrix[r][right])
21	right -= 1
22
23	# 3. Sweep Bottom (Right -> Left) with Guard!
24	if top <= bottom:
25	for c in range(right, left - 1, -1):
26	result.append(matrix[bottom][c])
27	bottom -= 1
28
29	# 4. Sweep Left (Bottom -> Top) with Guard!
30	if left <= right:
31	for r in range(bottom, top - 1, -1):
32	result.append(matrix[r][left])
33	left += 1
34
35	return result

Gotchas1 of 4

The trap
Gotcha 1: Leaving out the if top <= bottom guard
Mistake
```
for c in range(right, left - 1, -1):
    result.append(matrix[bottom][c])
bottom -= 1
```
Fix
```
if top <= bottom:
    for c in range(right, left - 1, -1):
        result.append(matrix[bottom][c])
    bottom -= 1
```
What happens: After the top sweep and the right sweep, the rows may be used up. For [[1,2,3]], the top sweep reads row 0 and sets top to 1, while bottom is 0. Without the guard, the bottom sweep reads row 0 again, backwards. The left sweep needs if left <= right for the same reason.
Example: matrix = [[1, 2, 3]]
Mistake: returns [1, 2, 3, 2, 1]Fix: returns [1, 2, 3]
Gotcha 2: Forgetting top += 1 after the top sweep
Mistake
```
for c in range(left, right + 1):
    result.append(matrix[top][c])
```
Fix
```
for c in range(left, right + 1):
    result.append(matrix[top][c])
top += 1
```
What happens: top marks the first row that is not read yet. The right sweep starts at row top. Without top += 1, the right sweep reads the top-right corner a second time. Later sweeps then read other cells twice as well.
Example: matrix = [[1, 2], [3, 4]]
Mistake: returns [1, 2, 2, 4, 3, 1]Fix: returns [1, 2, 4, 3]
Gotcha 3: Writing range(right, left, -1) in the bottom sweep
Mistake
```
for c in range(right, left, -1):
```
Fix
```
for c in range(right, left - 1, -1):
```
What happens: range stops before its end value. range(right, left, -1) stops before column left, so the bottom sweep skips it. For [[1,2],[3,4]], the value 3 is never read. The left sweep has the same kind of bound, range(bottom, top - 1, -1).
Example: matrix = [[1, 2], [3, 4]]
Mistake: returns [1, 2, 4]Fix: returns [1, 2, 4, 3]
Gotcha 4: Looping range(right - left + 1) when rotating a ring
Mistake
```
for i in range(right - left + 1):
```
Fix
```
for i in range(right - left):
```
What happens: In Rotate Image (LC 48), each ring can be turned in place. For each i in range(right - left), four cells move one side along, through one saved value. A side has right - left + 1 cells, but its last cell is the first cell of the next side. With range(right - left + 1), each corner moves twice.
Example: matrix = [[1, 2], [3, 4]]
Mistake: returns [[4, 3], [2, 1]]Fix: returns [[3, 1], [4, 2]]

Canonical LeetCode:Spiral Matrix (LC 54)Spiral Matrix II (LC 59)Rotate Image (LC 48)Spiral Matrix IV (LC 2326)Cyclically Rotating a Grid (LC 1914)

Open the Spiral Matrix card

3Fast Power

base x, exponent n ➔ halve exponent repeatedly ➔ O(log N) power

Fast Power (Exponentiation by Squaring)

Spot it when: The exponent can be huge (up to

10^9

or more), or the answer is a repeated product 'modulo

10^9 + 7

Mode 3 · Fast Power

Python

1	def my_pow(x: float, n: int) -> float:
2	"""Binary Exponentiation: computes x^n by squaring.
3	Time: O(log N) \| Space: O(1)
4	"""
5	if n < 0:
6	x = 1.0 / x # x^-n == (1/x)^n
7	n = -n
8
9	result = 1.0
10	curr_product = x # Holds x^(2^i) for the current bit i
11
12	while n > 0:
13	if n % 2 == 1:
14	result *= curr_product # Bit is set: multiply this power in
15	curr_product *= curr_product # Square for the next bit
16	n //= 2 # Move to the next bit
17
18	return result

Gotchas1 of 4

The trap
Gotcha 1: Negating n without replacing x by 1 / x
Mistake
```
if n < 0:
    n = -n
```
Fix
```
if n < 0:
    x = 1.0 / x
    n = -n
```
What happens: For a negative n, x ** n equals (1 / x) ** -n. The loop only handles n >= 0. With n = -n alone, it computes x ** -n. So my_pow(2.0, -2) returns 4.0 instead of 0.25.
Example: x = 2.0, n = -2
Mistake: returns 4.0Fix: returns 0.25
Gotcha 2: Negating n in a 32-bit int in Java or C++
What happens: In Java or C++, n can be -2^31, the smallest 32-bit int. Its negative, 2^31, does not fit in 32 bits. In Java, -n gives -2^31 again, and in C++ it is undefined behavior. Copy n into a 64-bit variable, such as a Java long, before n = -n.
Gotcha 3: Reducing modulo MOD only at the end
Mistake
```
result *= curr_product
curr_product *= curr_product
```
Fix
```
result = result * curr_product % MOD
curr_product = curr_product * curr_product % MOD
```
What happens: This problem has no modulus, but many counting problems ask for the answer modulo MOD, such as 10^9 + 7. Without % MOD after each multiplication, the numbers grow to many digits. In Python the answer is still correct, but every multiplication gets slower. In Java or C++, a 64-bit value overflows. Python's built-in pow(base, exp, MOD) runs the same loop and reduces after each step.
Gotcha 4: Subtracting after pow(2, n, MOD) without adding MOD back
Mistake
```
return pow(2, n, MOD) - 2
```
Fix
```
return (pow(2, n, MOD) - 2 + MOD) % MOD
```
What happens: pow(2, n, MOD) is already reduced, so it can be smaller than 2. For n = 500000003 and MOD = 10**9 + 7, it is exactly 1. Subtracting 2 then gives -1. Count Collisions of Monkeys on a Polygon (LC 2550) returns this difference, so it needs the fix. Add MOD before the final % MOD, because in Java and C++ % of a negative number stays negative.
Example: n = 500000003, MOD = 10**9 + 7
Mistake: returns -1Fix: returns 1000000006

Canonical LeetCode:Pow(x, n) (LC 50)Count Good Numbers (LC 1922)Count Collisions of Monkeys on a Polygon (LC 2550)Maximize Number of Nice Divisors (LC 1808)Super Pow (LC 372)

Open the Fast Power card

4In-Place Marking

matrix ➔ markers in the first row / column or spare bits ➔ apply in a second pass

In-Place Markers (First Row/Column Flags, Two States per Cell)

Mode 4 · In-Place Marking

Python

1	def set_zeroes(matrix: list[list[int]]) -> None:
2	"""Set Matrix Zeroes: row 0 and column 0 hold the flags for the other rows and columns.
3	Time: O(M * N) \| Space: O(1)
4	"""
5	m, n = len(matrix), len(matrix[0])
6
7	# 1. Save Row 0's and Column 0's Own Zeros First:
8	# Pass 1 below overwrites row 0 and column 0 with flags, so whether
9	# they originally held a zero must be recorded before any flag is written.
10	first_row_zero = any(matrix[0][c] == 0 for c in range(n))
11	first_col_zero = any(matrix[r][0] == 0 for r in range(m))
12
13	# 2. Mark Flags in Row 0 and Column 0:
14	# A zero found inside the matrix (outside row 0 and column 0) means its
15	# whole row and column end up zero, so that is recorded by zeroing the
16	# row's cell in column 0 and the column's cell in row 0.
17	for r in range(1, m):
18	for c in range(1, n):
19	if matrix[r][c] == 0:
20	matrix[r][0] = 0
21	matrix[0][c] = 0
22
23	# 3. Apply the Flags to Every Inner Cell:
24	# Any inner cell whose row flag or column flag is set is zeroed; row 0
25	# and column 0 themselves are skipped here because they still need to be read.
26	for r in range(1, m):
27	for c in range(1, n):
28	if matrix[r][0] == 0 or matrix[0][c] == 0:
29	matrix[r][c] = 0
30
31	# 4. Clear Row 0 and Column 0 Last:
32	# Row 0 and column 0 are cleared only after every other cell has read
33	# their flags; clearing them earlier would turn every flag true and wipe the whole matrix.
34	if first_row_zero:
35	for c in range(n):
36	matrix[0][c] = 0
37	if first_col_zero:
38	for r in range(m):
39	matrix[r][0] = 0

Gotchas1 of 5

The trap

Gotcha 1: Clearing row 0 before pass 2 reads the flags

Mistake

if first_row_zero:
    for c in range(n):
        matrix[0][c] = 0
for r in range(1, m):
    for c in range(1, n):
        if matrix[r][0] == 0 or matrix[0][c] == 0:
            matrix[r][c] = 0

Fix

for r in range(1, m):
    for c in range(1, n):
        if matrix[r][0] == 0 or matrix[0][c] == 0:
            matrix[r][c] = 0
if first_row_zero:
    for c in range(n):
        matrix[0][c] = 0

Example: matrix = [[0, 1, 2], [3, 4, 5], [6, 7, 8]]

Mistake: returns [[0, 0, 0], [0, 0, 0], [0, 0, 0]]Fix: returns [[0, 0, 0], [0, 4, 5], [0, 7, 8]]

Gotcha 2: Using one flag for both row 0 and column 0
Mistake
```
first_zero = any(matrix[0][c] == 0 for c in range(n)) or any(matrix[r][0] == 0 for r in range(m))
first_row_zero = first_col_zero = first_zero
```
Fix
```
first_row_zero = any(matrix[0][c] == 0 for c in range(n))
first_col_zero = any(matrix[r][0] == 0 for r in range(m))
```
What happens: One shared flag can only say that row 0 or column 0 had a 0. It can't say which one. So a 0 only in column 0 also clears all of row 0. Using matrix[0][0] as that one flag has the same problem, because the cell is in both. The blueprint keeps two booleans, first_row_zero and first_col_zero.
Example: matrix = [[1, 1], [0, 1]]
Mistake: returns [[0, 0], [0, 0]]Fix: returns [[0, 1], [0, 0]]

Gotcha 3: Computing first_row_zero after pass 1 writes the flags

Mistake

for r in range(1, m):
    for c in range(1, n):
        if matrix[r][c] == 0:
            matrix[r][0] = 0
            matrix[0][c] = 0
first_row_zero = any(matrix[0][c] == 0 for c in range(n))

Fix

first_row_zero = any(matrix[0][c] == 0 for c in range(n))
for r in range(1, m):
    for c in range(1, n):
        if matrix[r][c] == 0:
            matrix[r][0] = 0
            matrix[0][c] = 0

Example: matrix = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]

Mistake: returns [[0, 0, 0], [0, 0, 0], [1, 0, 1]]Fix: returns [[1, 0, 1], [0, 0, 0], [1, 0, 1]]

Gotcha 4: Zeroing row r and column c during the scan
Mistake
```
if matrix[r][c] == 0:
    for k in range(n):
        matrix[r][k] = 0
    for k in range(m):
        matrix[k][c] = 0
```
Fix
```
if matrix[r][c] == 0:
    matrix[r][0] = 0
    matrix[0][c] = 0
```
What happens: Pass 1 scans the cells in order. If it writes 0s into the row and the column at once, the scan meets those new 0s later. It takes them for 0s that were in the input. Each one clears another row and column. The 0s spread to rows and columns that had none.
Example: matrix = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
Mistake: returns [[1, 0, 0], [0, 0, 0], [0, 0, 0]]Fix: returns [[1, 0, 1], [0, 0, 0], [1, 0, 1]]
Gotcha 5: Starting pass 2 at row 0 instead of row 1
Mistake
```
for r in range(m):
    for c in range(1, n):
        if matrix[r][0] == 0 or matrix[0][c] == 0:
```
Fix
```
for r in range(1, m):
    for c in range(1, n):
        if matrix[r][0] == 0 or matrix[0][c] == 0:
```
What happens: Row 0 holds the column flags until pass 2 ends. If pass 2 starts at row 0 and matrix[0][0] == 0, it sets every matrix[0][c] to 0. Every later row then finds a flag in every column and is cleared.
Example: matrix = [[0, 1], [1, 1]]
Mistake: returns [[0, 0], [0, 0]]Fix: returns [[0, 0], [0, 1]]

Canonical LeetCode:Set Matrix Zeroes (LC 73)Game of Life (LC 289)Build Array from Permutation (LC 1920)Candy Crush (LC 723)

Open the In-Place Marking card

5Cross Product

three points ➔ sign of the cross product ➔ left turn, right turn or straight line

Cross Product Orientation Test (Turn Direction, Collinearity, Convexity)

Mode 5 · Cross Product

Python

1	def cross(o: list[int], a: list[int], b: list[int]) -> int:
2	"""Orientation test: > 0 when o -> a -> b turns left, < 0 when it turns right, 0 when the points are collinear."""
3	# cross is twice the signed area of triangle o, a, b: its sign alone gives the turn direction.
4	return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
5
6
7	def is_convex(points: list[list[int]]) -> bool:
8	"""Convex Polygon: every turn along the boundary has the same cross-product sign.
9	Time: O(N) \| Space: O(1)
10	"""
11	n = len(points)
12	prev = 0 # prev: the last non-zero turn seen so far; 0 means no turn has been seen yet
13	for i in range(n):
14	# 1. Compute the Turn at the Next Corner:
15	# cross() gives the sign of the turn o -> a -> b in one integer; % n wraps the index, so the
16	# two turns that close the polygon are checked in the same pass as every other corner.
17	turn = cross(points[i], points[(i + 1) % n], points[(i + 2) % n])
18
19	# 2. Classify the Turn (the trap):
20	# A turn of 0 is a straight corner: it is allowed and tells nothing about direction, so it
21	# is skipped before prev is touched. A later non-zero turn with the opposite sign means the
22	# boundary bent back on itself, a dent, so the polygon is not convex.
23	if turn == 0:
24	continue
25	if prev != 0 and (turn > 0) != (prev > 0):
26	return False
27
28	# 3. Remember the Direction:
29	# Save this non-zero turn so the next corner's turn can be compared against it.
30	prev = turn
31	return True

Gotchas1 of 4

The trap
Gotcha 1: Leaving out if turn == 0: continue
Mistake
```
if prev != 0 and (turn > 0) != (prev > 0):
```
Fix
```
if turn == 0:
    continue
if prev != 0 and (turn > 0) != (prev > 0):
```
What happens: A turn of 0 is a straight corner. It is allowed, and it says nothing about the direction. Without continue, the 0 reaches the sign test. After a right turn, the test passes, and prev = turn sets prev to 0. The last known direction is lost. A dent right after the straight corner is then not caught. After a left turn, the same 0 fails the test, so a convex polygon is rejected.
Example: points = [[6,6],[8,12],[12,12],[12,0],[0,0],[0,12],[4,12],[5,9]]
Mistake: returns TrueFix: returns False
Gotcha 2: Looping range(n - 2) and skipping the two closing turns
Mistake
```
for i in range(n - 2):
```
Fix
```
for i in range(n):
```
What happens: range(n - 2) checks the corners at points[1] to points[n - 2]. The corners at points[n - 1] and points[0] close the loop, and they are never checked. In [[0,0],[0,10],[10,10],[10,0],[5,5]], the dent at [5,5] is one of them. range(n) with % n in the turn line checks all n corners.
Example: points = [[0,0],[0,10],[10,10],[10,0],[5,5]]
Mistake: returns TrueFix: returns False
Gotcha 3: Testing the sign with prev * turn < 0
Mistake
```
if prev * turn < 0:
```
Fix
```
if prev != 0 and (turn > 0) != (prev > 0):
```
What happens: In Python both tests give the same answer. With coordinates up to 10^4, one cross product can reach 8 * 10^8. The product of two cross products can reach 6.4 * 10^17, which overflows a 32-bit integer in Java or C++. Comparing the two signs needs no multiplication.
Gotcha 4: Comparing slopes dy / dx instead of using cross
Mistake
```
(a[1] - o[1]) / (a[0] - o[0]) == (b[1] - a[1]) / (b[0] - a[0])
```
Fix
```
cross(o, a, b) == 0
```
What happens: A vertical edge has dx = 0, so the division raises ZeroDivisionError. With large coordinates, two different slopes can also round to the same float. cross uses only integer multiplication and subtraction. Valid Boomerang (LC 1037) only asks whether one cross is non-zero. Largest Triangle Area (LC 812) is the largest abs(cross(o, a, b)) / 2.
Example: o = [0, 0], a = [0, 5], b = [0, 10]
Mistake: raises ZeroDivisionErrorFix: returns True

Canonical LeetCode:Convex Polygon (LC 469)Check If It Is a Straight Line (LC 1232)Valid Boomerang (LC 1037)Largest Triangle Area (LC 812)

Open the Cross Product card

6Euclid's GCD

two numbers ➔ replace (a, b) by (b, a % b) ➔ greatest common divisor

Euclidean Algorithm (Greatest Common Divisor)

Mode 6 · Euclid's GCD

Python

1	def gcd(a: int, b: int) -> int:
2	"""Euclid's algorithm: gcd(a, b) == gcd(b, a % b), and gcd(a, 0) == a."""
3	# 1. Replace the Pair Until It Shrinks to Zero (the trap):
4	# a % b is a minus a multiple of b, so a number dividing both a and b also divides a % b, and a
5	# number dividing b and a % b also divides a: both values must update from the old pair at once.
6	while b:
7	a, b = b, a % b
8	# 2. Return the Answer:
9	# The loop stops once b is 0; since gcd(a, 0) == a, a now holds the greatest common divisor.
10	return a
11
12
13	def find_gcd(nums: list[int]) -> int:
14	"""Find Greatest Common Divisor of Array: Euclid's algorithm on the smallest and largest value.
15	Time: O(N + log M) \| Space: O(1)
16	"""
17	lo, hi = min(nums), max(nums) # lo, hi: the two ends; only they matter, the other values play no part
18	return gcd(hi, lo)

Gotchas1 of 4

The trap
Gotcha 1: Writing a = b and then b = a % b
Mistake
```
a = b
b = a % b
```
Fix
```
a, b = b, a % b
```
What happens: After a = b, the old a is gone. The next line computes b % b, which is always 0. The loop stops after one step and returns the old b. So gcd(8, 3) returns 3 instead of 1.
Example: a = 8, b = 3
Mistake: returns 3Fix: returns 1
Gotcha 2: Returning b instead of a after the loop
Mistake
```
return b
```
Fix
```
return a
```
What happens: The loop stops when b is 0, so the pair ends as (g, 0). return b then always returns 0. The rule gcd(x, 0) == x also lets a running gcd start from 0, as in Number of Subarrays With GCD Equal to K (LC 2447).
Example: a = 8, b = 3
Mistake: returns 0Fix: returns 1
Gotcha 3: Using repeated subtraction instead of %
Mistake
```
while b:
    if a >= b:
        a -= b
    else:
        a, b = b, a
```
Fix
```
while b:
    a, b = b, a % b
```
What happens: Subtraction gives the same answer, but it can take a / b steps. For gcd(10**9, 1), that is about 10^9 steps. With %, the number of steps is at most about 2 * log2 of the smaller value.
Gotcha 4: Taking the gcd of all values in nums
Mistake
```
return functools.reduce(gcd, nums)
```
Fix
```
lo, hi = min(nums), max(nums)
return gcd(hi, lo)
```
What happens: Find Greatest Common Divisor of Array (LC 1979) asks for the gcd of only the smallest and the largest value. For [2, 5, 6, 9, 10], that is the gcd of 10 and 2, which is 2. The gcd of all five values is 1. Other problems do take the gcd of every value, such as X of a Kind in a Deck of Cards (LC 914) with its counts.
Example: nums = [2, 5, 6, 9, 10]
Mistake: returns 1Fix: returns 2

Open the Euclid's GCD card

7Canonical Key

integers (a, b) ➔ Euclidean reduction ➔ normalized coprime factors

Canonical-Form Hashing (Normalize Before You Count)

Mode 7 · Canonical Key

Python

1	import math
2	from collections import defaultdict
3
4	def max_points_on_line(points: list[list[int]]) -> int:
5	"""Maximum points collinear on a plane using GCD slope hashing.
6	Time: O(N^2) \| Space: O(N)
7	"""
8	# 1. Handle Trivial Inputs:
9	# Any 0, 1, or 2 points are always collinear, so the general counting
10	# below is skipped for those sizes.
11	if len(points) <= 2:
12	return len(points)
13
14	max_pts = 0 # largest count of collinear points found across all anchors
15
16	# 2. Anchor on Each Point in Turn:
17	# slopes counts, for the current anchor points[i], how many later points
18	# share each direction from it; a fresh dict per anchor keeps directions
19	# from different anchors from being mixed into the same count.
20	for i in range(len(points)):
21	slopes: dict[tuple[int, int], int] = defaultdict(int)
22	x1, y1 = points[i]
23
24	for j in range(i + 1, len(points)):
25	x2, y2 = points[j]
26	dx, dy = x2 - x1, y2 - y1
27	g = math.gcd(dx, dy)
28
29	# 3. Reduce the Direction to a Canonical Key:
30	# Dividing dx and dy by their gcd keeps the same direction in
31	# lowest terms, then flipping the sign so dy is positive (or dy
32	# == 0 with dx positive) makes opposite vectors of one line hash alike.
33	slope = (dy // g, dx // g)
34	if slope[0] < 0 or (slope[0] == 0 and slope[1] < 0):
35	slope = (-slope[0], -slope[1])
36
37	# 4. Count and Track the Best Line Through This Anchor:
38	# Every point sharing a key lies on the same line through
39	# points[i]; the + 1 below counts the anchor point itself.
40	slopes[slope] += 1
41	max_pts = max(max_pts, slopes[slope] + 1)
42
43	return max_pts

Gotchas1 of 4

The trap
Gotcha 1: Leaving the sign of (dy // g, dx // g) unfixed
Mistake
```
slope = (dy // g, dx // g)
```
Fix
```
slope = (dy // g, dx // g)
if slope[0] < 0 or (slope[0] == 0 and slope[1] < 0):
    slope = (-slope[0], -slope[1])
```
What happens: math.gcd never returns a negative number. So dy // g and dx // g keep the signs of dy and dx. For points = [[0, 0], [1, 1], [-1, -1]], the anchor [0, 0] gives [1, 1] the key (1, 1). It gives [-1, -1] the key (-1, -1), although both points lie on the same line. That one line is then counted in two buckets. The fix flips the pair so that dy is positive, or dy == 0 and dx is positive.
Example: points = [[0, 0], [1, 1], [-1, -1]]
Mistake: returns 2Fix: returns 3
Gotcha 2: Creating slopes once, outside the loop over i
Mistake
```
slopes: dict[tuple[int, int], int] = defaultdict(int)
for i in range(len(points)):
```
Fix
```
for i in range(len(points)):
    slopes: dict[tuple[int, int], int] = defaultdict(int)
```
What happens: A key in slopes is only a direction. It names one line only while every point is measured from the same points[i]. If slopes is shared by all anchors, two parallel lines add to the same count. The fix creates a new, empty slopes for every anchor i.
Example: points = [[0, 0], [1, 0], [5, 5], [6, 5]]
Mistake: returns 3Fix: returns 2
Gotcha 3: Running the blueprint on points that can repeat
Mistake
```
g = math.gcd(dx, dy)
slope = (dy // g, dx // g)
```
Fix
```
if dx == 0 and dy == 0:
    same += 1
    continue
g = math.gcd(dx, dy)
```
What happens: Max Points on a Line (LC 149) promises that all points are different. In a variant with repeated points, a copy of points[i] gives dx = dy = 0. Then math.gcd(0, 0) is 0, and dy // g raises ZeroDivisionError. Count the copies of points[i] in same instead. Add same to the best line through points[i], because a copy lies on every line through it.
Example: points = [[1, 1], [1, 1], [2, 2]]
Mistake: raises ZeroDivisionErrorFix: returns 3
Gotcha 4: Hashing the slope as a float dy / dx
Mistake
```
slope = dy / dx
```
Fix
```
slope = (dy // g, dx // g)
if slope[0] < 0 or (slope[0] == 0 and slope[1] < 0):
    slope = (-slope[0], -slope[1])
```
What happens: A vertical line has dx = 0, so dy / dx raises ZeroDivisionError. Floats also round. With coordinates near 10^8, two different slopes can round to the same float and share one key. For example, 94911150 / 94911151 == 94911151 / 94911152 is True in Python. The reduced integer pair (dy // g, dx // g) has neither problem.
Example: points = [[1, 1], [1, 2], [1, 3]]
Mistake: raises ZeroDivisionErrorFix: returns 3

Open the Canonical Key card

8Count and Skip

rank k in a huge list in dictionary order ➔ at each slot, skip k // block blocks of equal size (k counted from 0) and keep k % block ➔ the k-th item, built one slot at a time

K-th in Dictionary Order by Block Counting (Unranking, Factorial Number System)

Mode 8 · Count and Skip

Python

1	def get_permutation(n: int, k: int) -> str:
2	"""Permutation Sequence: skip whole blocks of arrangements that share the digits chosen so far.
3	Time: O(N^2) \| Space: O(N)
4	"""
5	fact = [1] * n # fact[m] = m!
6
7	# 1. Precompute Factorials:
8	# fact[m] holds m!, the number of arrangements of m items, needed below
9	# to size each slot's blocks without computing a factorial inside the main loop.
10	for m in range(1, n):
11	fact[m] = fact[m - 1] * m
12
13	pool = [str(d) for d in range(1, n + 1)] # unused digits, smallest first
14
15	# 2. Convert the Rank to 0-Based:
16	# k counts from 1, but k // block below needs the count of arrangements
17	# that come strictly before the answer, which is k - 1.
18	k -= 1
19	result = [] # digits of the answer, chosen one slot at a time
20
21	# 3. Choose Each Slot by Skipping Whole Blocks:
22	# Every unused digit starts a block of fact[n - 1 - slot] arrangements
23	# that share the digits chosen so far; dividing k by that block size
24	# finds how many whole blocks come before the answer, and the remainder
25	# becomes the answer's rank inside the chosen block for the next slot.
26	for slot in range(n):
27	block = fact[n - 1 - slot]
28	index = k // block
29	k %= block
30	result.append(pool.pop(index))
31	return "".join(result)

Gotchas1 of 4

The trap
Gotcha 1: Leaving out k -= 1
Mistake
```
result = []
```
Fix
```
k -= 1
result = []
```
What happens: k counts from 1, but k // block needs the number of arrangements before the answer. That number is k - 1. Without k -= 1, every k that is a multiple of block picks one block too far.
Example: n = 3, k = 3
Mistake: returns '231'Fix: returns '213'
Gotcha 2: Writing fact[n - slot] instead of fact[n - 1 - slot]
Mistake
```
block = fact[n - slot]
```
Fix
```
block = fact[n - 1 - slot]
```
What happens: A block holds the arrangements of the slots after this one. At slot 0 there are n - 1 such slots. So a block there holds (n - 1)! arrangements, which is fact[n - 1]. fact has only n entries, so fact[n - 0] raises IndexError.
Example: n = 3, k = 3
Mistake: raises IndexErrorFix: returns '213'
Gotcha 3: Reading pool[index] instead of pool.pop(index)
Mistake
```
result.append(pool[index])
```
Fix
```
result.append(pool.pop(index))
```
What happens: pool[index] reads the digit but leaves it in pool. The next slot can choose the same digit again, so the answer repeats a digit. pool.pop(index) removes the digit, so the next slot chooses from the unused digits only.
Example: n = 3, k = 3
Mistake: returns '211'Fix: returns '213'
Gotcha 4: Using k // block when blocks have different sizes
What happens: k // block is correct only when every block at a slot holds the same number of arrangements. In K-th Smallest in Lexicographical Order (LC 440), the blocks at one slot differ in size. There, k // block skips the wrong number of arrangements, so it picks the wrong block.

Open the Count and Skip card

9Josephus Problem

circle of n friends ➔ smaller circle's winner ➔ shift by k

Josephus Problem (Circular Elimination Recurrence)

Spot it when: People (or items) stand in a circle and every k-th one is removed until one is left; find who remains without simulating every removal.

Mode 9 · Josephus Problem

Python

1	def find_the_winner(n: int, k: int) -> int:
2	"""Find the Winner of the Circular Game (Josephus): f(size) = (f(size - 1) + k) % size.
3	Time: O(N) \| Space: O(1)
4	"""
5	winner = 0 # 0-indexed winner of the game with 1 friend
6	for size in range(2, n + 1):
7	winner = (winner + k) % size # Shift the smaller game's winner k seats
8	return winner + 1 # Friends are numbered from 1

Gotchas1 of 4

The trap
Gotcha 1: Returning winner without adding 1
Mistake
```
return winner
```
Fix
```
return winner + 1
```
What happens: The recurrence counts seats from 0. So winner = 0 is the only seat when one friend is left. Find the Winner of the Circular Game (LC 1823) numbers the friends from 1. Only the final return adds 1.
Example: n = 5, k = 2
Mistake: returns 2Fix: returns 3
Gotcha 2: Wrapping with % n instead of % size
Mistake
```
winner = (winner + k) % n
```
Fix
```
winner = (winner + k) % size
```
What happens: At each step, the circle has size friends, not n. The shift of k seats happens in that smaller circle, so the wrap must use % size. With % n, winner can point past the last seat of the current circle.
Example: n = 5, k = 2
Mistake: returns 4Fix: returns 3
Gotcha 3: Simulating the circle with list.pop
Mistake
```
people = list(range(1, n + 1))
i = 0
while len(people) > 1:
    i = (i + k - 1) % len(people)
    people.pop(i)
return people[0]
```
Fix
```
winner = 0
for size in range(2, n + 1):
    winner = (winner + k) % size
return winner + 1
```
What happens: The simulation gives the same answer, and it passes the limits of Find the Winner of the Circular Game (LC 1823). Each pop(i) shifts the later friends, so the simulation takes O(N^2) time and O(N) space. The recurrence takes O(N) time and O(1) space.
Gotcha 4: Looping range(2, n) instead of range(2, n + 1)
Mistake
```
for size in range(2, n):
```
Fix
```
for size in range(2, n + 1):
```
What happens: range stops before its end value. So range(2, n) stops at a circle of n - 1 friends. It returns the winner of that smaller game.
Example: n = 5, k = 2
Mistake: returns 1Fix: returns 3

Canonical LeetCode:Find the Winner of the Circular Game (LC 1823)Elimination Game (LC 390)

Open the Josephus Problem card

10Sieve of Eratosthenes

upper bound n ➔ boolean sieve array ➔ prime count

Sieve of Eratosthenes

Spot it when: You need to know which of many numbers up to a known limit are prime (counting primes, pairing primes, checking many values), not just one number.

Mode 10 · Sieve of Eratosthenes

Python

1	def count_primes(n: int) -> int:
2	"""Sieve of Eratosthenes: counts primes strictly below n.
3	Time: O(N log log N) \| Space: O(N)
4	"""
5	if n <= 2:
6	return 0 # No primes below 2
7
8	is_prime = [True] * n
9	is_prime[0] = is_prime[1] = False # 0 and 1 are not prime
10
11	for p in range(2, int(n ** 0.5) + 1): # Factors above sqrt(n) were already crossed out
12	if is_prime[p]:
13	for multiple in range(p * p, n, p): # Start at p*p: smaller multiples have a smaller factor
14	is_prime[multiple] = False
15
16	return sum(is_prime)

Gotchas1 of 5

The trap
Gotcha 1: Leaving is_prime[0] and is_prime[1] as True
Mistake
```
is_prime = [True] * n
```
Fix
```
is_prime = [True] * n
is_prime[0] = is_prime[1] = False
```
What happens: Every slot starts True. Crossing out starts at p * p, which is at least 4. So no step ever reaches 0 or 1. Without the line, sum(is_prime) counts 0 and 1 as primes, and the count is 2 too high.
Example: n = 10
Mistake: returns 6Fix: returns 4
Gotcha 2: Making the table [True] * (n + 1)
Mistake
```
is_prime = [True] * (n + 1)
```
Fix
```
is_prime = [True] * n
```
What happens: Count Primes (LC 204) counts the primes strictly less than n. With n + 1 slots, the table also has a slot for n itself. The loop range(p * p, n, p) stops before n, so that slot is never crossed out. sum(is_prime) then counts n as a prime, even when it is not. The same definition explains if n <= 2: return 0, because no prime is less than 2.
Example: n = 10
Mistake: returns 5Fix: returns 4
Gotcha 3: Stopping p at int(n ** 0.5) without the + 1
Mistake
```
for p in range(2, int(n ** 0.5)):
```
Fix
```
for p in range(2, int(n ** 0.5) + 1):
```
What happens: range stops before its end value. Without + 1, p never takes the value int(n ** 0.5) itself. For n = 10, that value is 3, so 9 is never crossed out. Any end above the square root is correct. Looping p up to n also works, but it is slower.
Example: n = 10
Mistake: returns 5Fix: returns 4
Gotcha 4: Starting the crossing at 2 * p instead of p * p
Mistake
```
for multiple in range(2 * p, n, p):
```
Fix
```
for multiple in range(p * p, n, p):
```
What happens: Every multiple p * k with k < p has a prime factor smaller than p. That smaller prime already crossed it out. Starting at 2 * p crosses those numbers out again. The count is the same, and only the time grows.
Gotcha 5: Building a sieve to test only one or two numbers
What happens: The sieve fills a table of n slots, so it costs O(n log log n) time and O(n) space. To test one number x, trial division by every value up to the square root of x is simpler. The sieve pays off when you test many numbers below n.

Canonical LeetCode:Count Primes (LC 204)Prime Arrangements (LC 1175)Prime Subtraction Operation (LC 2601)Prime Pairs With Target Sum (LC 2761)

Open the Sieve of Eratosthenes card

11Reservoir Sampling

stream of items ➔ keep each with chance 1/i ➔ one uniform random item

Reservoir Sampling & Randomized Pick

Spot it when: A uniform random pick from a list or stream you can read only once, often of unknown length and with no room to copy it: every element must come back with the same chance.

Mode 11 · Reservoir Sampling

Python

1	import random
2	from typing import Optional
3
4
5	class ListNode:
6	def __init__(self, val: int = 0, next: Optional["ListNode"] = None):
7	self.val = val
8	self.next = next
9
10
11	class Solution:
12	"""Linked List Random Node: reservoir sampling, one pass per pick and O(1) extra space.
13	Time: O(N) per getRandom \| Space: O(1)
14	"""
15
16	def __init__(self, head: Optional[ListNode]):
17	self.head = head # Keep only the head: every pick walks the list again
18
19	def getRandom(self) -> int:
20	result, i = 0, 0 # result: the current pick; i: nodes seen so far
21	node = self.head
22	while node:
23	# 1. Count This Node:
24	# i must count node before the draw, so the first node is always taken (randrange(1) is 0).
25	i += 1
26
27	# 2. Draw With Chance 1/i:
28	# randrange(i) is one of 0..i - 1, so it lands on 0 with chance exactly 1/i; every earlier
29	# node then keeps its own share, since it survives this draw with chance (i - 1)/i.
30	if random.randrange(i) == 0:
31	result = node.val
32
33	# 3. Move to the Next Node:
34	# The same draw repeats at every node until the whole list has been walked once.
35	node = node.next
36	# 4. Return the Last Survivor:
37	# After the last node every node has had chance exactly 1/n, with no copy of the list ever made.
38	return result

Gotchas1 of 3

The trap
Gotcha 1: Drawing randrange(i + 1) instead of randrange(i)
Mistake
```
if random.randrange(i + 1) == 0:
```
Fix
```
if random.randrange(i) == 0:
```
What happens: i += 1 already counts the current node, so node i must win with chance 1/i. The head then wins with chance 1/1, so it is always kept first. With randrange(i + 1), the head wins only half the time. For the list [1, 2], each of 0, 1 and 2 is returned in one third of the calls. The 0 is result's starting value, which is not in the list.
Example: head = [1, 2], the set of values from 100 calls
Mistake: returns [0, 1, 2]Fix: returns [1, 2]
Gotcha 2: Returning at the first successful draw
Mistake
```
if random.randrange(i) == 0:
    return node.val
```
Fix
```
if random.randrange(i) == 0:
    result = node.val
```
What happens: The first node's draw is randrange(1), which is always 0. So the first draw always succeeds. Returning there gives the head on every call. The loop must keep walking, so later nodes can replace result.
Example: head = [1, 2], the set of values from 100 calls
Mistake: returns [1]Fix: returns [1, 2]
Gotcha 3: Choosing the random node once, in __init__
Mistake
```
def getRandom(self) -> int:
    return self.pick  # drawn once in __init__
```
Fix
```
def getRandom(self) -> int:
    result, i = 0, 0
    node = self.head
```
What happens: Each call to getRandom must be a new draw. A value chosen once in __init__ is returned on every call. So every call gives the same value.
Example: head = [1, 2], the set of values from 100 calls
Mistake: returns [1]Fix: returns [1, 2]

Canonical LeetCode:Linked List Random Node (LC 382)Random Pick Index (LC 398)

Open the Reservoir Sampling card

The Math & Geometry Decision Rule

When facing an unseen mathematical or geometric problem, ask in this order:

Step 1.Does the problem parse strings to integers, reverse digits, or risk 32-bit wrap?

➔ Digit Manipulation

Reverse Integer (LC 7)Palindrome Number (LC 9)

Validate bounds before res = res * 10 + digit.

Step 2.Must items count as equal once written in one standard form (reduced slopes, sorted letters, shapes shifted to the origin)?

➔ Canonical Key

Max Points on a Line (LC 149)Number of Distinct Islands (LC 694)

Build the key first, e.g. (dy // g, dx // g) with g = gcd(dx, dy) and one fixed sign, then count keys in a dict.

Step 3.Must the input change in place with O(1) extra memory, while each change depends on the values as they were?

➔ In-Place Marking

Set Matrix Zeroes (LC 73)Game of Life (LC 289)

Record the changes in the first row and column (or in spare bits of each cell), then apply them in a second pass.

Step 4.Does the problem walk a matrix ring by ring (spiral order, filling a spiral, rotating layers)?

➔ Spiral Matrix

Spiral Matrix (LC 54)Spiral Matrix II (LC 59)

Establish top, bottom, left, right bounds and contract clockwise.

Step 5.Do people stand in a circle with every k-th one removed until one is left?

➔ Josephus Problem

Find the Winner of the Circular Game (LC 1823)Elimination Game (LC 390)

f(1) = 0 and f(n) = (f(n - 1) + k) % n; the winner is f(n) + 1 in 1-based numbering.

Step 6.Does the problem need which of many numbers up to a limit are prime?

➔ Sieve of Eratosthenes

Count Primes (LC 204)Prime Arrangements (LC 1175)

Precompute a boolean prime table in O(N log log N), crossing out multiples from p * p.

Step 7.Does the problem involve huge powers or a repeated product modulo 10^9 + 7?

➔ Fast Power

Pow(x, n) (LC 50)Count Good Numbers (LC 1922)

Halve the exponent each iteration: x^n = (x^2)^(n/2), times x when n is odd, in O(log N).

Step 8.Must several whole numbers or lengths share their largest common divisor (a common block, equal groups, a reduced fraction)?

➔ Euclid's GCD

Find Greatest Common Divisor of Array (LC 1979)Greatest Common Divisor of Strings (LC 1071)

gcd(a, b) = gcd(b, a % b) until b == 0; fold it over the whole list.

Step 9.Is the question about direction between points: a left or right turn, collinearity, convexity or a triangle's area?

➔ Cross Product

Convex Polygon (LC 469)Check If It Is a Straight Line (LC 1232)

cross = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x): positive is a left turn, zero is collinear.

Step 10.Must you pick uniformly at random from a list or stream you can read only once?

➔ Reservoir Sampling

Linked List Random Node (LC 382)Random Pick Index (LC 398)

Keep the i-th item (1-based) with probability 1 / i: replace the pick when randrange(i) == 0.

Step 11.Must you return the k-th item of a huge list sorted in dictionary order (the k-th permutation, string or route), or the rank of an item in it, without building the list?

➔ Count and Skip

Permutation Sequence (LC 60)The k-th Lexicographical String of All Happy Strings of Length n (LC 1415)

Pattern Architecture & Invariant Design Masterclass

The invariants to say out loud:

4-Boundary Box: "After traversing the top row and right column, I must verify top <= bottom and left <= right before reversing direction back across bottom and left."
Coprime Slopes: "Never compare floating-point slopes. Reduce displacement vectors by gcd(dx, dy) and store coprime integer pairs."

🔬 Variable Anatomy: The 7 Variables Every Math & Geometry Solution Uses

To connect abstract geometric invariants with concrete Python syntax, here is the universal code anatomy showing what every variable does:

Code / Blueprint

import math
from collections import defaultdict
 
def mathGeometryMasterTemplate(
    matrix: list[list[int]],
    points: list[list[int]],
    n: int
) -> tuple[list[int], int, int]:
    # =========================================================================
    # 1. THE 4-BOUNDARY COORDINATE POINTERS
    # =========================================================================
    top, bottom = 0, len(matrix) - 1      # ↕️ Vertical Boundary Bounds
    left, right = 0, len(matrix[0]) - 1   # ↔️ Horizontal Boundary Bounds
    spiral_res = []
 
    # =========================================================================
    # 2. 4-POINTER PERIMETER CONTRACTION (SPIRAL MATRIX)
    # =========================================================================
    while top <= bottom and left <= right:
        # Top row: left -> right
        for c in range(left, right + 1):
            spiral_res.append(matrix[top][c])
        top += 1
 
        # Right col: top -> bottom
        for r in range(top, bottom + 1):
            spiral_res.append(matrix[r][right])
        right -= 1
 
        # Bottom row: right -> left (Guarded against single row)
        if top <= bottom:
            for c in range(right, left - 1, -1):
                spiral_res.append(matrix[bottom][c])
            bottom -= 1
 
        # Left col: bottom -> top (Guarded against single col)
        if left <= right:
            for r in range(bottom, top - 1, -1):
                spiral_res.append(matrix[r][left])
            left += 1
 
    # =========================================================================
    # 3. GCD REDUCED FRACTION SLOPE HASHING
    # =========================================================================
    slope_counts = defaultdict(int)
    if points:
        x1, y1 = points[0]
        for x2, y2 in points[1:]:
            dx = x2 - x1
            dy = y2 - y1
            if dx == 0 and dy == 0:
                continue
            g = math.gcd(dx, dy)
            reduced_slope = (dy // g, dx // g)  # ⚡ Coprime integer slope key
            if reduced_slope[0] < 0 or (reduced_slope[0] == 0 and reduced_slope[1] < 0):
                reduced_slope = (-reduced_slope[0], -reduced_slope[1])
            slope_counts[reduced_slope] += 1
 
    # =========================================================================
    # 4. 32-BIT OVERFLOW GUARD & DIGIT EXTRACTION
    # =========================================================================
    INT_MAX = 2**31 - 1
    INT_MIN = -2**31
    rev = 0
    temp_n = n
    sign = -1 if temp_n < 0 else 1
    temp_n = abs(temp_n)
 
    while temp_n > 0:
        digit = temp_n % 10
        temp_n //= 10
        # ⚠️ CRITICAL: Check overflow BEFORE multiplying
        if rev > (INT_MAX - digit) // 10:
            rev = 0
            break
        rev = rev * 10 + digit
 
    reversed_int = sign * rev
 
    return spiral_res, max(slope_counts.values(), default=0), reversed_int

Variable Role Reference:

Variable	Role in Code	Question It Answers	❌ What Happens If Omitted or Mismanaged?
`top` / `bottom`	Row boundary pointers	"What is the active vertical range of unvisited cells?"	❌ Without contracting `top += 1` / `bottom -= 1`, rows are traversed multiple times.
`left` / `right`	Col boundary pointers	"What is the active horizontal range of unvisited cells?"	❌ Omitting `if top <= bottom` before bottom sweep repeats middle rows on non-square matrices.
`dx` / `dy`	Coordinate delta	"What is the displacement between two geometric points?"	❌ Subtracting in inconsistent order `(x1 - x2)` vs `(x2 - x1)` inverts vector direction.
`g` (`gcd`)	Greatest common divisor	"What factor reduces `(dy, dx)` to its unique coprime ratio?"	❌ Using floating-point division `dy / dx` introduces precision errors where distinct slopes collide in hash keys.
`INT_MAX`	32-bit clamp threshold	"Will `rev 10 + digit` exceed 32-bit signed integer capacity?"*	❌ Checking overflow after multiplying triggers runtime integer wrap/overflow in fixed-width languages.
`digit`	`x % 10`	"What is the current least significant base-10 digit?"	❌ In Python, negative `% 10` returns positive; in C++/Java it returns negative, breaking parity.
`exp`	Binary power exponent	"Can we halve the exponent to reduce power calculation to $O(\log N)$ ?"	❌ Iterating $N$ times for $x^N$ times out on large exponents ( $N = 2^{31} - 1$ ).

🧠 The Universal Contract of Discrete Geometry:

Coprime Slope Contract: Never hash float(dy) / float(dx) due to IEEE 754 precision drift. Always reduce by g = gcd(dx, dy) and hash the integer tuple (dy // g, dx // g). Handle vertical lines (1, 0) and horizontal lines (0, 1) consistently.

Boundary Guard Invariant: When contracting a 2D matrix box, the horizontal and vertical sweeps shrink the space. Always verify top <= bottom and left <= right before initiating the return bottom and left sweeps.

🌟 The 3 Dimensions of Math & Geometry & The Precision-Boundary Invariant

Every Math & Geometry problem is governed by 3 Fundamental Dimensions:

Code / Blueprint

┌─────────────────────────────────────────────────────────────────────────────┐
│                       THE 3 DIMENSIONS OF MATH & GEOMETRY                   │
├───────────────────┬───────────────────────────────────┬─────────────────────┤
│ Dimension         │ Mechanism in Code                 │ Question It Answers │
├───────────────────┼───────────────────────────────────┼─────────────────────┤
│ 1. BOUNDARY       │ Monotonic inward contraction:     │ "How does perimeter │
│    CONTRACTION    │ `top, bottom, left, right`        │ geometry shrink?"   │
├───────────────────┼───────────────────────────────────┼─────────────────────┤
│ 2. ARITHMETIC     │ Coprime reduction `(dy//g, dx//g)`│ "How do we preserve │
│    PRECISION      │ Pre-multiplication overflow guard │ exact equality?"    │
├───────────────────┼───────────────────────────────────┼─────────────────────┤
│ 3. NUMBER THEORY  │ Binary Exponentiation: O(log N)   │ "How do we avoid    │
│    REDUCTION      │ Sieve: O(N log log N)             │ O(N^2) brute force  │
│                   │ instead of trial division         │ operations?"        │
└───────────────────┴───────────────────────────────────┴─────────────────────┘

How this plays out in actual problems:

🟢 Scenario A: Perimeter Box Contraction (Spiral Matrix LC 54)

Traversing a matrix in spiral order naively requires an $O(R \cdot C)$ visited grid.
The Rule: Maintain 4 boundary limits (top = 0, bottom = R-1, left = 0, right = C-1). Traverse top edge (L➔R) and increment top += 1. Traverse right edge (T➔B) and decrement right -= 1. Guard inner reverse sweeps with if top <= bottom and if left <= right.
The Result: Complete traversal in $O(R \cdot C)$ time with $O(1)$ extra space.

🔵 Scenario B: Coprime Slope Hashing (Max Points on a Line LC 149)

Checking if 3 points are collinear by comparing (y2 - y1) / (x2 - x1) == (y3 - y1) / (x3 - x1) fails on vertical lines (divide-by-zero) and floats.
The Rule: Compute g = math.gcd(dx, dy). Normalize signs so dy > 0 (or dy == 0 and dx > 0). Store coprime pairs (dy // g, dx // g) in a hash map.
The Result: Guaranteed zero precision drift across all lines.

🟣 Scenario C: Binary Exponentiation (Pow(x, n) LC 50)

Computing $x^n$ with a loop takes $O(n)$ multiplications, which times out for $n = 2 \times 10^9$ .
The Rule: Halve the exponent each step: if $n$ is even, $x^n = (x^2)^{n/2}$ ; if $n$ is odd, $x^n = x \cdot (x^2)^{(n-1)/2}$ .
The Result: Collapses $2 \times 10^9$ operations to about 31 squarings plus one multiplication per 1-bit of $n$ (at most about 62 multiplications, $O(\log n)$ ).

💡 The Ultimate Takeaway Decision Rule:
When analyzing a math or coordinate problem, ask: "Is this perimeter navigation, slope collinearity, or large arithmetic reduction?"

If Matrix spiral / rotation ➔ 4-Pointer Perimeter Contraction ( $O(R \cdot C)$ ).

If Line collinearity / slopes ➔ Coprime GCD tuple hashing (dy//g, dx//g).

If Large powers or primes ➔ Binary Exponentiation ( $O(\log N)$ ) or Sieve ( $O(N \log \log N)$ ).

If 32-bit digit operations ➔ Pre-multiplication overflow guard rev > (INT_MAX - d) // 10.

🎯 The 4 Essential Math & Geometry Paradigms & Archetypes

Code / Blueprint

┌──────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│                                   THE 4 CORE MATH & GEOMETRY ARCHETYPES                                          │
├────────────────────────┬──────────────────────┬───────────────────────────────┬──────────────────────────────────┤
│ Archetype              │ Coordinate Mechanism │ Exact Arithmetic Invariant    │ Target Problems & Complexity     │
├────────────────────────┼──────────────────────┼───────────────────────────────┼──────────────────────────────────┤
│ 1. Perimeter Contract. │ 4 shrinking bounds   │ Guard reverse sweeps with     │ Spiral Matrix (LC 54), Spiral    │
│    (4-Boundary Box)    │ `top, bottom, L, R`  │ `top <= bottom & left <= right│ Matrix II (LC 59) — O(R * C)     │
├────────────────────────┼──────────────────────┼───────────────────────────────┼──────────────────────────────────┤
│ 2. Coprime GCD Slopes  │ Coordinate deltas    │ `g = gcd(dx, dy)` yields      │ Max Points on a Line (LC 149)    │
│    (Collinear Points)  │ `(x2 - x1, y2 - y1)` │ normalized `(dy//g, dx//g)`   │ — O(N^2)                         │
├────────────────────────┼──────────────────────┼───────────────────────────────┼──────────────────────────────────┤
│ 3. Overflow Surgery    │ Base-10 extraction   │ Check `rev > (MAX - d) // 10` │ Reverse Integer (LC 7), String   │
│    (Digit Reversal)    │ `d = x % 10; x //= 10` before multiplying by 10      │ to Integer atoi (LC 8) — O(log N)│
├────────────────────────┼──────────────────────┼───────────────────────────────┼──────────────────────────────────┤
│ 4. Logarithmic Powers  │ Binary Exponentiation│ $x^n = (x^2)^{n/2}$;          │ Pow(x, n) (LC 50) — O(log N);    │
│    (Sieve & Pow)       │ Sieve crossing $p^2$ │ cross multiples in sieve      │ Count Primes (LC 204) —          │
│                        │                      │                               │ O(N log log N)                   │
└────────────────────────┴──────────────────────┴───────────────────────────────┴──────────────────────────────────┘

🌀 1. 4-Pointer Perimeter Contraction (LC 54 — Spiral Matrix)

Mental Model: Peels rectangular perimeters layer-by-layer like an onion.
Code: see the Spiral Matrix card.

📐 2. Number Theory & GCD Slope Hashing (LC 149)

Mental Model: Points $P_1, P_2, P_3$ share a line if their normalized slope vectors from an anchor point are identical.
Code: see the Canonical Key card.

🔢 3. 32-Bit Integer Overflow Surgery (LC 7)

Mental Model: Reverse digits one by one while verifying that multiplying by 10 will not overflow 32-bit signed integer limits.
Code: see the Digit Manipulation card.

⚡ 4. Binary Exponentiation (LC 50 — Pow(x, n))

Mental Model: Repeated squaring halves the computation size at each step.
Code: see the Fast Power card.

🌳 Evaluating Mathematical Invariants, Modular Arithmetic & Precision Guarantees

Maintaining exactness in mathematical calculations requires understanding computer arithmetic:

1. In-Place Matrix Rotation (Transpose + Reflect)

To rotate an $N \times N$ $N \times N$ matrix 90 degrees clockwise in-place with $O(1)$ $O (1)$ extra space:
1. Transpose: Swap matrix[i][j] with matrix[j][i] for all $j > i$ .
2. Reflect: Reverse each row row.reverse().

2. Guarding Modulo of Negative Numbers

In languages like C++ and Java, -7 % 3 yields -1 rather than 2. To guarantee a non-negative residue, use (x % m + m) % m.

💡 Staff SWE Architectural Invariant:
Avoid floating-point types for discrete geometry comparisons. Always reduce coordinate ratios to coprime integer pairs with GCD to eliminate precision drift across platforms.

Understanding Invariants: Perimeter Contraction & Coprime Slope Precision

Contracting 4-boundary boxes (top, bottom, left, right) guarantees every cell in a 2D matrix is visited exactly once in O(1) auxiliary space without a visited hash set.

2D Boundary Guard Invariant

Condition: Before traversing bottom row (right to left) or left column (bottom to top)

Action: verify top <= bottom and left <= right

Contracts boundary pointers after top and right sweeps; without guards, non-square matrices re-traverse cells.

Coprime Slope Precision Invariant

Condition: For any slope delta (dy, dx)

Action: hash integer tuple (dy // gcd(dx, dy), dx // gcd(dx, dy)) instead of float(dy / dx)

Prevents IEEE 754 floating-point drift and avoids divide-by-zero crashes on vertical lines.

Common Questions

"In Spiral Matrix, why do the bottom-row and left-column sweeps need an extra if top <= bottom / if left <= right guard, when the top-row and right-column sweeps don't need one?"

Because by the time execution reaches the third and fourth sides of a lap, the first two sides may have already shrunk the remaining region down to a single row or column — and without the guard, that same row or column gets walked a second time, in the opposite direction.

Each full lap peels one layer off the "onion": top row left-to-right (top += 1), right column top-to-bottom (right -= 1), bottom row right-to-left (bottom -= 1), left column bottom-to-top (left += 1). The first two sides are always safe because the loop condition while top <= bottom and left <= right already guaranteed a valid region existed before the lap began. But the first two sides' own pointer updates (top += 1, right -= 1) happen during the lap — so by the time you reach the third side, top may have already passed bottom (this was a single remaining row), or by the fourth side left may have already passed right (a single remaining column).

Without the guard, the bottom-row sweep would re-walk the exact same row the top-row sweep just finished, in reverse — double-counting cells that were already collected. The two guard checks exist purely to detect "this layer has already been fully collapsed to a line by the earlier sides of this same lap" and skip the redundant sweep. It's specific to the third and fourth sides because only they can observe a collapse the first two sides just caused.

Coach discussion points

1.
How do we cleanly represent vertical line slopes where dx == 0 when using the GCD approach?
2.
Explain how coordinate matrix rotation matrix[i][j] maps to matrix[j][n - 1 - i] for a 90-degree clock-wise turn.
3.
Why must dividend == INT_MIN and divisor == -1 be checked before any other arithmetic in Divide Two Integers, rather than after computing abs(dividend)?
4.
Walk through why doubling temp and multiple together in lock-step guarantees the bit-shift doubling algorithm removes at least half of the remaining dividend on every outer loop iteration, bounding total iterations to O(log N).
5.
In Integer to Roman, why does putting the subtractive forms (900=CM, 400=CD, 90=XC, 40=XL, 9=IX, 4=IV) directly into the ordered value/symbol table eliminate the need for any per-digit conditional branching?
6.
What would break if the Integer to Roman value/symbol table were not kept in strictly decreasing order?
7.
For reverse integer, why does Python let you cheat the 32-bit limit naturally, and how do you enforce it algorithmically in Python?
8.
In Set Matrix Zeroes, why may row 0 and column 0 hold the flags at all, and why must first_row_zero and first_col_zero be recorded before the first flag is written and used only after the second pass?
9.
In Convex Polygon, why must a turn of 0 be skipped before it is compared with prev or stored in it, and which two turns does the % n wrap-around add?
10.
In Find Greatest Common Divisor of Array, why do (a, b) and (b, a % b) share every common divisor, and why must a, b = b, a % b update both values in one statement?
11.
In Linked List Random Node, why does keeping the i-th node with chance exactly 1/i leave every node with chance 1/n at the end, and why must i count the current node before the draw?
12.
In Permutation Sequence, why do the arrangements that share a first digit form one block of (n - 1)!, and why must k -= 1 come before k // block?

Complexity analysis

Spiral Matrix: $O(M \times N)$ Time, $O(1)$ Space.
Max Points: $O(N^2)$ Time, $O(N)$ Space.
Reverse Integer: $O(\log_{10} x)$ Time, $O(1)$ Space.
Josephus: $O(N)$ Time, $O(1)$ Space.
Pow(x, n): $O(\log N)$ Time, $O(1)$ Space.
Count Primes: $O(N \log \log N)$ Time, $O(N)$ Space.
Integer to Roman: $O(1)$ Time, $O(1)$ Space (fixed 13-entry table).
Divide Two Integers: $O(\log^2 N)$ Time, $O(1)$ Space.
Set Matrix Zeroes: $O(M \times N)$ Time, $O(1)$ Space (flags in row 0 and column 0).
Convex Polygon: $O(N)$ Time, $O(1)$ Space (one cross product per corner).
Find Greatest Common Divisor of Array: $O(N + \log M)$ Time, $O(1)$ Space (Euclid's remainder steps on the two ends).
Linked List Random Node: $O(N)$ Time per getRandom, $O(1)$ Space (reservoir sampling, one walk per pick).
Permutation Sequence: $O(N^2)$ Time, $O(N)$ Space (Count and Skip: N slots, each with an O(N) pop).

Production Systems Deployment & Motivation

Mastery Roadmap & Prerequisite Graph

Traversing bottom row or left column when boundaries have crossed: After traversing right and down, top and bottom or left and right may have crossed (e.g. in single-row or single-column matrices). You must verify top <= bottom before traversing left, and left <= right before traversing up.
Allocating visited matrix when 4 boundaries suffice: Maintaining an $M \times N$ visited boolean matrix wastes $O(M \cdot N)$ auxiliary space. Four bounding pointers (top, bottom, left, right) achieve $O(1)$ auxiliary space.
Off-by-one on boundary increments: Forgetting to advance boundaries (top += 1, right -= 1, bottom -= 1, left += 1) causes the traversal to repeat the outer perimeter infinitely.

Staff+ Engineering Perspective

Staff+ Systems Architecture & Hardware Considerations

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

CONSTRAINTS & BOUNDS

FAANG PRODUCTION TRAPS & EDGE CASES

Integer overflow during multiplication prior to modulo; division in modular arithmetic requiring Fermat's Little Theorem / modular inverse; matrix boundary off-by-one errors during spiral traversals.