# Math & Matrix — Part 2: Interview Problems

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

## 1. Rotate 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
```

## 2. Spiral 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
```

## 3. Set 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
```

## 4. Pow(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
```

## 5. Count 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)
```

## 6. Happy 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
```