Math & Geometry

Matrix moves

Grid problems often hinge on index arithmetic. Staples:

• Rotate 90° in place — transpose, then reverse each row.
• Spiral / ring traversal — track four boundaries shrinking inward.
• Set matrix zeroes — use the first row/column as markers for O(1) space.

def rotate(matrix):                  # 90° clockwise, in place
    n = len(matrix)
    for i in range(n):
        for j in range(i + 1, n):    # transpose
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    for row in matrix:
        row.reverse()                # reverse each row

Number theory you’ll reuse

• GCD via Euclid: gcd(a, b) = gcd(b, a % b); LCM = a // gcd(a,b) * b. The extended Euclid finds modular inverses.
• Digit work: n % 10 peels the last digit, n //= 10 drops it — Reverse Integer, Palindrome Number, Happy Number, Add Digits.
• Primes: trial division up to √n tests one number; the Sieve of Eratosthenes lists all primes < n in O(n log log n) (“Count Primes”).
• Factorization — divide out factors up to √n.

Modular arithmetic

For “answer modulo 1e9+7” (huge counts), apply the mod at every step so values never overflow: (a + b) % M, (a * b) % M. Division under a mod uses the modular inverse (Fermat’s little theorem: a^(M-2) mod M for prime M). Common in combinatorics-heavy DP.

Fast exponentiation

Compute x^n (or x^n mod M) in O(log n) by squaring:

def fast_pow(x, n):
    result = 1
    while n:
        if n & 1: result *= x        # multiply when the bit is set
        x *= x                        # square
        n >>= 1
    return result

Powers “Pow(x, n),” modular exponentiation, and matrix exponentiation (e.g. Fibonacci in O(log n) via a 2×2 matrix power).

Combinatorics

• n!, nCr = n! / (r!(n−r)!) — precompute factorials (and inverse factorials under a mod) for O(1) per query.
• Pascal’s triangle — C(n,r) = C(n-1,r-1) + C(n-1,r) (a small DP).
• Catalan numbers — count valid parenthesizations, unique BSTs, etc.

Geometry basics

• Distance — squared distance avoids sqrt (and floating error) when only comparing.
• Orientation / cross product — sign of (b−a)×(c−a) tells left/right turn; the basis of convex hull and segment-intersection tests.
• Area — shoelace formula for polygons.

Sampling & probability

• Fisher–Yates shuffle — swap each element with a random earlier (or later) one → uniform permutation, O(n).
• Reservoir sampling — pick k uniform items from a stream of unknown length in O(1) space (see the randomized primer).

Overflow & precision

• Detect integer overflow before it happens by comparing against limits (relevant in fixed-int languages; Python ints are arbitrary precision but slow if huge).
• Prefer integer math; avoid floats when you can. When dividing, watch rounding and use tolerances (eps) for float comparisons.

Choosing in an interview

These problems reward spotting the closed form or invariant over brute force:

• Repeated multiply/power → fast exponentiation.
• Huge counts → modular arithmetic (+ inverse for division).
• “Count the ways” → combinatorics / Catalan.
• Primes/divisors → sieve / √n factorization.
• Grid transforms → index arithmetic (transpose+reverse, boundaries).

Look for the pattern in the numbers first; the code is usually short once you see it.