Algorithms & Coding Interviews · Greedy, DP & Bits

Math & Matrix

A few math identities and matrix tricks come up constantly: gcd, fast exponentiation, modular arithmetic, the sieve, cycle detection, and in-place matrix transformations. Learn each with a template, the language pitfalls (overflow, BigInt, negative modulo), and watch Rotate Image, Spiral Matrix and binary exponentiation animated.

🧮 Algorithms & Coding Interviews● Intermediate⏱ 10 min read▶ 3 interactive🛠️ 4 exercises

🎯 What you'll learn

gcd, fast power, the sieve and modular arithmetic
In-place matrix rotation, spiral order and marker tricks
Overflow and precision across Python, TS and C#
Six LeetCode problems with animated walkthroughs

📚 Before you start

Bit manipulation

Part 1The Pattern

A handful of math tools and matrix manipulations show up again and again: gcd (Euclid), fast exponentiation (O(log n) by squaring), modular arithmetic for huge answers ("return the result mod 10⁹ + 7"), the sieve of Eratosthenes for primes, cycle detection on number sequences, and in-place matrix transformations (rotate, spiral order, marking rows/columns). None of these need deep math, just the right identity and careful indexing.

Rotating a matrix 90° clockwise = transpose + reverse each row

1Templates

typescript

function gcd(a: number, b: number): number {
  while (b) [a, b] = [b, a % b];
  return a;
}

function fastPow(x: number, n: number, mod: number): number {
  let result = 1n, base = BigInt(x) % BigInt(mod), e = BigInt(n);
  const m = BigInt(mod);
  while (e > 0n) {                   // BigInt avoids precision loss above 2^53
    if (e & 1n) result = (result * base) % m;
    base = (base * base) % m;
    e >>= 1n;
  }
  return Number(result);
}

function sieve(n: number): number[] {
  const isPrime = new Array(n).fill(true);
  isPrime[0] = isPrime[1] = false;
  for (let p = 2; p * p < n; p++) if (isPrime[p]) for (let q = p * p; q < n; q += p) isPrime[q] = false;
  return isPrime.flatMap((v, i) => (v && i < n ? [i] : []));
}

function mathDemo(a: number, b: number, x: number, k: number, m: number, n: number): any[] {
  return [gcd(a, b), fastPow(x, k, m), sieve(n)];
}

python

def gcd(a, b):
    while b:
        a, b = b, a % b              # Euclid: gcd(a, b) = gcd(b, a mod b)
    return a

def fast_pow(x, n, mod):             # x^n mod m in O(log n)
    result = 1
    x %= mod
    while n:
        if n & 1:
            result = result * x % mod
        x = x * x % mod
        n >>= 1
    return result

def sieve(n):                        # primes < n in O(n log log n)
    is_prime = [True] * n
    is_prime[0:2] = [False, False][:n]
    for p in range(2, int(n ** 0.5) + 1):
        if is_prime[p]:
            for q in range(p * p, n, p):
                is_prime[q] = False
    return [i for i in range(n) if is_prime[i]]

def math_demo(a, b, x, k, m, n):
    return [gcd(a, b), fast_pow(x, k, m), sieve(n)]

2Modular Arithmetic

(a + b) % m = ((a % m) + (b % m)) % m, and the same for multiplication: reduce after every step to keep numbers small.
Division needs a modular inverse: for a prime m, a⁻¹ = a^(m−2) mod m (Fermat), computed with fast power.
In JavaScript, products above 2⁵³ lose precision: use BigInt for modular multiplication with large moduli. In C#, use long (and checked blocks if you want overflow errors).

3Matrix Patterns

Task	Idea
rotate 90° clockwise in place	transpose (swap `m[i][j]` and `m[j][i]`), then reverse each row
rotate counter-clockwise	transpose, then reverse each column (or reverse rows first)
spiral order	four boundaries `top, bottom, left, right`; walk one edge, shrink that boundary
set matrix zeroes in O(1) space	use the first row and column as markers (plus one flag for the first column)
diagonal traversal	cells with the same `r + c` (anti-diagonal) or `r − c` (diagonal)
2D binary search (sorted rows & columns)	start at the top-right; move left or down: O(m + n)

Under the HoodWhy Fast Power Is O(log n)▾

Write n in binary: x¹³ = x⁸ · x⁴ · x¹ (13 = 1101₂). Squaring x repeatedly gives x, x², x⁴, x⁸ … (one squaring per bit), and you multiply in the powers whose bit is set. So you do about 2·log₂ n multiplications instead of n. The same trick computes Fibonacci numbers in O(log n) with matrix exponentiation, and it underpins RSA and Diffie–Hellman (modular exponentiation with 2048-bit numbers).

⚠️ Common Pitfalls

Overflow before taking the modulus (a * b in 32-bit C#, or above 2⁵³ in JS).
Negative modulo in JS/C# (-7 % 3 == -1): normalize with ((x % m) + m) % m.
Negative exponents in pow(x, n): use 1 / x^(−n), and beware −(−2³¹) overflowing in C#.
Spiral off-by-one: after walking the top row, top += 1 before the right column, and check bounds before walking back.
Sieve upper bound: the outer loop only needs p * p < n.

📋 Quick Reference

text

gcd: while b: a, b = b, a % b · lcm = a / gcd * b
fast pow: while n: if n&1: r *= x; x *= x; n >>= 1   (mod after each step)
sieve: for p*p < n: if prime: mark p*p, p*p+p, …
rotate CW: transpose + reverse rows · spiral: shrink 4 boundaries

Part 2Interview Problems

Six problems: three in-place matrix transformations, binary exponentiation, the sieve, and cycle detection on a number sequence.

1Rotate Image (LeetCode 48)

🟠 Medium. Rotate an n × n matrix 90° clockwise in place.

text

[[1,2,3],[4,5,6],[7,8,9]] → [[7,4,1],[8,5,2],[9,6,3]]

Approach. Transpose (swap across the main diagonal), then reverse every row. Both steps are in place.

Complexity. O(n²) time, O(1) extra space.

typescript

function rotate(matrix: number[][]): void {
  const n = matrix.length;
  for (let i = 0; i < n; i++)
    for (let j = i + 1; j < n; j++) [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
  for (const row of matrix) row.reverse();
}

python

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

2Spiral Matrix (LeetCode 54)

🟠 Medium. Return all elements of an m × n matrix in spiral order.

text

[[1,2,3],[4,5,6],[7,8,9]] → [1,2,3,6,9,8,7,4,5]

Approach. Keep four boundaries. Walk the top row left→right (then top++), the right column top→bottom (right--), the bottom row right→left if rows remain (bottom--), and the left column bottom→top if columns remain (left++).

Complexity. O(m · n) time, O(1) extra space.

typescript

function spiralOrder(matrix: number[][]): number[] {
  const res: number[] = [];
  let top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1;
  while (top <= bottom && left <= right) {
    for (let c = left; c <= right; c++) res.push(matrix[top][c]);
    top++;
    for (let r = top; r <= bottom; r++) res.push(matrix[r][right]);
    right--;
    if (top <= bottom) { for (let c = right; c >= left; c--) res.push(matrix[bottom][c]); bottom--; }
    if (left <= right) { for (let r = bottom; r >= top; r--) res.push(matrix[r][left]); left++; }
  }
  return res;
}

python

def spiral_order(matrix):
    res = []
    top, bottom, left, right = 0, len(matrix) - 1, 0, len(matrix[0]) - 1
    while top <= bottom and left <= right:
        for c in range(left, right + 1):
            res.append(matrix[top][c])
        top += 1
        for r in range(top, bottom + 1):
            res.append(matrix[r][right])
        right -= 1
        if top <= bottom:
            for c in range(right, left - 1, -1):
                res.append(matrix[bottom][c])
            bottom -= 1
        if left <= right:
            for r in range(bottom, top - 1, -1):
                res.append(matrix[r][left])
            left += 1
    return res

3Set Matrix Zeroes (LeetCode 73)

🟠 Medium. If a cell is 0, set its entire row and column to 0, in place with O(1) extra space.

text

[[1,1,1],[1,0,1],[1,1,1]] → [[1,0,1],[0,0,0],[1,0,1]]

Approach. Use the first row and first column as marker storage: for each zero at (r, c), set matrix[r][0] and matrix[0][c] to 0. Remember separately whether the first column itself had a zero. Then zero cells based on the markers (skipping row/column 0), then handle the first row and column last.

Complexity. O(m · n) time, O(1) extra space.

typescript

function setZeroes(matrix: number[][]): void {
  const m = matrix.length, n = matrix[0].length;
  const firstColZero = matrix.some((row) => row[0] === 0);
  for (let r = 0; r < m; r++) for (let c = 1; c < n; c++) if (matrix[r][c] === 0) { matrix[r][0] = 0; matrix[0][c] = 0; }
  for (let r = 1; r < m; r++) for (let c = 1; c < n; c++) if (matrix[r][0] === 0 || matrix[0][c] === 0) matrix[r][c] = 0;
  if (matrix[0][0] === 0) matrix[0].fill(0);
  if (firstColZero) for (let r = 0; r < m; r++) matrix[r][0] = 0;
}

python

def set_zeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    first_col_zero = any(matrix[r][0] == 0 for r in range(m))
    for r in range(m):
        for c in range(1, n):
            if matrix[r][c] == 0:
                matrix[r][0] = matrix[0][c] = 0      # markers
    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 matrix[0][0] == 0:
        for c in range(n):
            matrix[0][c] = 0
    if first_col_zero:
        for r in range(m):
            matrix[r][0] = 0

4Pow(x, n) (LeetCode 50)

🟠 Medium. Implement x raised to the integer power n (n may be negative).

text

x = 2, n = 10 → 1024

Approach. Binary exponentiation: square the base each step and multiply it into the result when the current bit of n is 1. For negative n, compute the positive power and take the reciprocal.

Complexity. O(log |n|) time, O(1) space.

typescript

function myPow(x: number, n: number): number {
  if (n < 0) { x = 1 / x; n = -n; }
  let result = 1;
  while (n > 0) {
    if (n % 2 === 1) result *= x;      // avoid bitwise ops: |n| may exceed 2^31 - 1
    x *= x;
    n = Math.floor(n / 2);
  }
  return result;
}

python

def my_pow(x, n):
    if n < 0:
        x, n = 1 / x, -n
    result = 1.0
    while n:
        if n & 1:
            result *= x
        x *= x
        n >>= 1
    return result

5Count Primes (LeetCode 204)

🟠 Medium. Return the number of primes strictly less than n.

text

n = 10 → 4   (2, 3, 5, 7)

Approach. Sieve of Eratosthenes: for every prime p with p² < n, mark multiples starting at p² (smaller multiples were already marked by smaller primes). Count the unmarked numbers.

Complexity. O(n log log n) time, O(n) space.

typescript

function countPrimes(n: number): number {
  if (n < 3) return 0;
  const isPrime = new Uint8Array(n).fill(1);
  isPrime[0] = isPrime[1] = 0;
  for (let p = 2; p * p < n; p++) if (isPrime[p]) for (let q = p * p; q < n; q += p) isPrime[q] = 0;
  return isPrime.reduce((a, b) => a + b, 0);
}

python

def count_primes(n):
    if n < 3:
        return 0
    is_prime = [True] * n
    is_prime[0] = is_prime[1] = False
    p = 2
    while p * p < n:
        if is_prime[p]:
            for q in range(p * p, n, p):
                is_prime[q] = False
        p += 1
    return sum(is_prime)

6Happy Number (LeetCode 202)

🟢 Easy. Repeatedly replace n by the sum of the squares of its digits. n is happy if this reaches 1; otherwise it loops forever. Return whether n is happy.

text

19 → 82 → 68 → 100 → 1 → happy

Approach. The sequence either reaches 1 or enters a cycle. Detect the cycle with a seen set, or with Floyd's tortoise and hare for O(1) space (exactly like a linked list cycle).

Complexity. O(log n) per step; the sequence quickly falls below a few hundred.

typescript

function isHappy(n: number): boolean {
  const next = (x: number): number => { let s = 0; while (x) { const d = x % 10; s += d * d; x = Math.floor(x / 10); } return s; };
  let slow = n, fast = next(n);
  while (fast !== 1 && slow !== fast) { slow = next(slow); fast = next(next(fast)); }
  return fast === 1;
}

python

def is_happy(n):
    def nxt(x):
        return sum(int(d) ** 2 for d in str(x))
    slow, fast = n, nxt(n)
    while fast != 1 and slow != fast:
        slow, fast = nxt(slow), nxt(nxt(fast))
    return fast == 1

🧠 Key takeaways

Euclid gcd, fast power O(log n), sieve O(n log log n).
Reduce mod m after every step; use BigInt in JS and long in C# for big products.
Rotate CW = transpose + reverse rows; spiral = shrink four boundaries; O(1) markers in row/col 0.
Number sequences that may loop → cycle detection (seen set or Floyd).

🛠️ Practice exercises

Each exercise is a file in this topic folder. Code exercises are self-checking: run them and make the checks pass.

algo_math_and_matrix_exercise_1.py

TS PY

algo_math_and_matrix_exercise_2.py

TS PY

✅ Check yourself

Answer the questions — feedback is instant.

1. How many multiplications does fast power need for x^1000?

Square and multiply.

2. Rotate an n×n matrix 90° clockwise in place:

Two in-place passes.

3. In JavaScript, -7 % 3 is…

Normalize negatives.

4. Why does the sieve start marking at p²?

k·p with k < p already handled.

Source: algo_math_and_matrix_theory_1.md, algo_math_and_matrix_theory_2.md · generated by tools/build_lessons.py