Math & Geometry

Most interview questions are about data structures. This small but reliable family is about arithmetic — manipulating a 2-D grid by its indices, or doing digit-by-digit number work — and it is the one NeetCode-150 category the earlier patterns do not cover. The maths is never hard; the bugs come from getting the indices and the mutation order right.

The idea

There are two sub-families here, and both reward a calm, methodical approach:

1. Grid manipulation. Rotate, transpose, spiral-traverse, flood or mark a matrix — usually in place, so the challenge is swapping cells in the right order without clobbering data you still need. The trick is almost always a clean index mapping (e.g. “cell (i, j) goes to (j, n-1-i) after a 90° rotation”) rather than an auxiliary grid.
2. Number tricks. Work on the digits of a number directly: carry propagation (Plus One), building a value digit by digit (Reverse Integer, Roman numerals), or multiplying without converting to a big integer. The watch-out here is overflow — a non-issue in Python’s arbitrary-precision integers, but something interviewers expect you to mention for 32-bit languages.

Say your index mapping out loud, draw a 3×3 example, and verify one corner before you code. That habit turns these from fiddly to routine.

Worked example: rotate an image

Rotate an n × n matrix 90° clockwise in place. The clean decomposition is transpose (swap across the main diagonal) then reverse each row:

def rotate(matrix):
    n = len(matrix)
    for i in range(n):
        for j in range(i + 1, n):          # j starts at i+1 → each pair once
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    for row in matrix:
        row.reverse()
    return matrix
# rotate([[1,2,3],[4,5,6],[7,8,9]]) -> [[7,4,1],[8,5,2],[9,6,3]]

The j loop starting at i + 1 is the whole trick: it swaps each off-diagonal pair exactly once. Transpose + reverse is far easier to get right than a four-way layer rotation, and it is still O(n²) time, O(1) extra space.

Worked example: fast power

Compute x^n in O(log n) instead of O(n) multiplications, using square-and-multiply (binary exponentiation). Each bit of n either contributes the current square or not:

def my_pow(x, n):
    if n < 0:
        x = 1 / x; n = -n
    res = 1
    while n:
        if n & 1:          # this bit is set → include the current power of x
            res *= x
        x *= x             # square for the next bit
        n >>= 1
    return res
# my_pow(2.0, 10) -> 1024.0 ;  my_pow(2.0, -2) -> 0.25

This is the same halving idea as binary search (Lesson 10), applied to exponentiation: handle the sign, then walk the bits of the exponent.

Step-by-step walkthrough

Trace Rotate Image (90° clockwise, in place) on a 3×3 matrix. Two simple in-place passes compose into a rotation: transpose (swap across the main diagonal), then reverse each row.

The top row 1 2 3 ends up as the right column, exactly as a clockwise turn should. Both passes swap values inside the original matrix, so the extra space is O(1). Counter-clockwise is the mirror: transpose, then reverse each column.

When to reach for it

Signals: “rotate / transpose / spiral a matrix”, “do it in place with O(1) extra space”, “implement pow / sqrt / integer multiply / divide”, Roman numerals, “reverse the digits”, or “without converting the string to a number”. Whenever the problem is clearly about the grid’s geometry or a number’s digits rather than a data structure, you are here.

Pitfalls

• Mutation order. In-place grid updates can overwrite a value you still need — do the transpose before the reverse, process layers outside-in, or (for Set Matrix Zeroes) stash markers in the first row/column and apply them last.
• Overflow (other languages). Python integers never overflow, but Reverse Integer, Multiply Strings and pow are overflow traps in Java/C++. Say “I’d clamp to the 32-bit range here” even if your Python code doesn’t need to — interviewers are listening for it.
• Off-by-one on layers / boundaries. Spiral and layer problems live and die on the loop bounds. Draw the 3×3 and 4×4 cases (odd vs even size) and check the centre.

Recap

Math & geometry is about index arithmetic and in-place work, not clever maths. Rotate = transpose + reverse rows; spiral = peel and rotate; set-zeroes = use row 0 / column 0 as marker storage; fast power = square-and-multiply in O(log n). The number problems are digit handling plus an overflow caveat for 32-bit languages. Signal: rotate/spiral a matrix, in place, implement pow/multiply, handle the digits directly.

Practice: 10 solved problems on math & geometry → — cover each one, solve it yourself, then check the tested code.

Next: Lesson 27 — Design a Data Structure, where you compose structures to hit O(1) operations.