4.28.0 — Math & Geometry: The Pattern

Recognition cue. There is no data structure to reach for. The problem is arithmetic, index manipulation on a grid, or a small piece of geometry — and the answer is a formula or a careful loop rather than a map or a heap.

These problems are not hard. They are fiddly. The failures come from off-by-one errors and untested edge cases, not from missing an algorithm. So the method is different: derive the formula on a tiny example before writing any code.

The recurring moves

Digit walking. divmod(n, 10) peels the last digit and shifts the rest down. It appears in Happy Number, Plus One, Reverse Integer and Multiply Strings.

Index formulas on a grid. Deriving them once and checking them on a corner is the whole technique.

you want	formula
flatten (r, c) into one index	r * cols + c
unflatten index i	(i // cols, i % cols)
the 3×3 box of a Sudoku cell	(r // 3) * 3 + (c // 3)
the two diagonals through (r, c)	r − c and r + c
digit i × digit j lands at	i + j and i + j + 1

Matrix transformations, all built from transpose and reverse:

operation	recipe
rotate 90° clockwise	transpose, reverse each row
rotate 90° anticlockwise	transpose, reverse each column
rotate 180°	reverse the row order and each row
mirror horizontally	reverse each row

Halving the exponent. Fast exponentiation reads the exponent in binary and squares repeatedly, giving O(\log n).

Exact comparisons only. Compare squared distances rather than distances, and reduced fractions rather than slopes. Floating point turns a correct algorithm into an unreliable one.

The eight problems

#	Problem	The one insight
4.28.1	Rotate Image	Transpose, then reverse each row
4.28.2	Spiral Matrix	Four boundaries, and two guards for the last row or column
4.28.3	Set Matrix Zeroes	Use row 0 and column 0 as the record; [0][0] collides
4.28.4	Happy Number	A deterministic process is a linked list — use cycle detection
4.28.5	Plus One	The early return replaces the carry variable
4.28.6	Pow(x, n)	Read the exponent in binary; square repeatedly
4.28.7	Multiply Strings	Digits i and j land at i+j and i+j+1
4.28.8	Detect Squares	The diagonal determines the other two corners

The traps on this pattern

Untested boundary cases. A 1×n matrix in Spiral Matrix, all nines in Plus One, the most negative integer in Pow. Test the degenerate input before saying you are done.

Overflow. Negating the most negative 32-bit integer does not fit. Python is immune; most languages are not, and interviewers ask.

Floating point where integers would do. Squared distances, reduced fractions, and integer ceiling division (a + b - 1) // b.

Converting a huge digit string to an integer. It works in Python and overflows everywhere else — which is exactly why Multiply Strings and Plus One forbid it.

Swapping every pair twice. In a transpose, j must start at i + 1.

What the interviewer will push on

"Derive the index formula." Do it on a 2×2 or a corner cell, out loud.

"What is the degenerate input?" Name it before they do.

"Does this overflow?" Know where your language protects you and where it does not.

"Why not use floating point?" Precision. Give the squared-distance example.

One thing to volunteer: check your formula on the smallest example before writing the loop. Every problem in this group is one formula plus careful boundaries, and ten seconds of checking removes the only real risk.

Recall

• These problems are fiddly, not hard — derive the formula on a tiny example first.
• Digit walking: divmod(n, 10) peels the last digit.
• Grid formulas: flatten with r * cols + c; the Sudoku box is (r//3)*3 + (c//3); the diagonals are r − c and r + c.
• Rotate 90° clockwise = transpose then reverse each row. In the transpose, j starts at i + 1 or every pair is swapped twice.
• Fast exponentiation reads the exponent in binary: square each step, multiply in when the bit is set. O(\log n).
• Multiply Strings: digits i and j contribute to positions i+j and i+j+1, and the result has at most m + n digits.
• Compare exact quantities — squared distances, reduced fractions — never floats.
• Watch the degenerate input: a single row, all nines, the most negative integer.

Next: 4.28.1 Rotate Image — two simple operations replacing one formula that is easy to get wrong.