SyntaxPilot
Courses/DSA and Coding Problems/Lesson 85
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 85 of 90

Matrix problems: rotate image, spiral order, set matrix zeroes

queued

These are the notes for DSA episode 85: three matrix problems that interviewers love, each with a trap. Rotate image (LeetCode 48): writing each pixel straight to its new place scrambles the photo, and a second matrix runs out of memory on a 14000 × 14000 photo; a quarter turn is a transpose plus a mirror, both made of swaps. Spiral order (LeetCode 54): four walls that move inward, with two checks so a single row is not read twice. Set matrix zeroes (LeetCode 73): zeroing as you go makes the zeros spread, a copy is correct but times out on 6000 × 6000; the fix keeps its notes in the first row and column plus two flags, O(1) extra memory. Every program below was run with javac 21 (25-second limit and Java's default 1.5 GB heap on the recording machine, like the SyntaxPilot compiler), g++ 13 and Python 3, and every output shown is real (timings vary by machine).

The problems, in real life

Real life In code
A photo is a grid of pixels; tap "rotate" turn an n × n matrix 90° clockwise
A teacher walks the seating chart: front, side, back, other side, inner ring spiral order of an m × n matrix
A broken cinema seat closes its whole row and column a 0 zeroes its row and column
The phone has no room for a second copy of the photo "in place": O(1) extra memory

Every word, from zero

  • Matrix / 2D array: a grid of numbers; a[i][j] is row i, column j. int[][] in Java is an array of row arrays.
  • n × n (square) / m × n: m rows and n columns.
  • In place: change the given matrix itself, using only O(1) extra memory (a few variables).
  • Clockwise rotation by 90°: the cell (i, j) moves to (j, n − 1 − i); the top row becomes the right column.
  • Transpose: swap a[i][j] with a[j][i]; rows become columns, the main diagonal stays.
  • Main diagonal: the cells (i, i) from the top-left to the bottom-right.
  • Mirror (reverse) a row: swap its first and last elements, then the next pair inward.
  • Two pointers: two indices moving toward each other (l from the left, r from the right).
  • Spiral order: reading the outer ring clockwise, then the next ring, and so on.
  • Boundary / wall: the variables top, bottom, left, right marking the part not read yet.
  • Marker / note: a value written to remember something for a later pass.
  • Flag: a boolean that remembers one yes/no fact.
  • Heap (Java memory): where new objects live; its maximum size is fixed when the program starts.
  • OutOfMemoryError: what Java throws when new cannot get enough heap.

Problem 1: rotate image (LeetCode 48)

Rotate an n × n matrix 90° clockwise, in place.

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

Obvious idea 1: write each pixel straight to its new place

import java.util.*;

public class Main {
    static void rotate(int[][] m) {
        int n = m.length;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                m[j][n - 1 - i] = m[i][j];
    }
    public static void main(String[] args) {
        int[][] a = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        rotate(a);
        System.out.println(Arrays.deepToString(a));
    }
}

Output (real):

[[7, 4, 1], [2, 5, 2], [1, 2, 1]]

Scrambled: we wrote into cells we had not read yet, so their old values were lost.

Obvious idea 2: a second matrix

import java.util.*;

public class Main {
    static void rotate(int[][] m) {
        int n = m.length;
        int[][] r = new int[n][n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                r[j][n - 1 - i] = m[i][j];
        for (int i = 0; i < n; i++) m[i] = r[i];
    }
    public static void main(String[] args) {
        int[][] a = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        rotate(a);
        System.out.println(Arrays.deepToString(a));
        int[][] b = {{1, 2}, {3, 4}}, c = {{5}};
        rotate(b);
        rotate(c);
        System.out.println(Arrays.deepToString(b) + " " + Arrays.deepToString(c));
    }
}

Output (real):

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

Correct, but it needs a second n × n matrix. A camera-sized photo:

        int n = 14_000;
        int[][] a = new int[n][n];
        for (int i = 0; i < n; i++) Arrays.fill(a[i], i);
        long t0 = System.nanoTime();
        rotate(a);
        System.out.println(a[0][0] + " " + a[0][n - 1] + ", " + (System.nanoTime() - t0) / 1000000 + " ms");

With the copy: java.lang.OutOfMemoryError: Java heap space. The photo is about 784 MB (196 million ints); the photo plus a copy does not fit in Java's 1.5 GB heap.

The key insight: quarter turn = transpose + mirror

1 2 3      transpose      1 4 7      mirror each row      7 4 1
4 5 6     ---------->     2 5 8     ----------------->    8 5 2
7 8 9                     3 6 9                           9 6 3

Both steps are swaps, so nothing is ever overwritten before it is read, and no second matrix is needed. Transpose only the upper triangle (j > i), or each pair is swapped twice.

Solution in Java

import java.util.*;

public class Main {
    static void rotate(int[][] m) {
        int n = m.length;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) {
                int t = m[i][j]; m[i][j] = m[j][i]; m[j][i] = t;
            }
        for (int[] row : m)
            for (int l = 0, r = n - 1; l < r; l++, r--) {
                int t = row[l]; row[l] = row[r]; row[r] = t;
            }
    }
    public static void main(String[] args) {
        int[][] a = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        rotate(a);
        System.out.println(Arrays.deepToString(a));
        int[][] b = {{1, 2}, {3, 4}}, c = {{5}};
        rotate(b);
        rotate(c);
        System.out.println(Arrays.deepToString(b) + " " + Arrays.deepToString(c));
    }
}

Output (real):

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

The big photo with this version: 13999 0, 2056 ms (row i was full of i; after the turn the top row runs from 13999 down to 0).

A real bug: transpose with j from 0

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

Each pair was swapped twice (undoing the transpose), so only the mirror is left.

Problem 2: spiral order (LeetCode 54)

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

Input Output
[[1,2,3,4],[5,6,7,8],[9,10,11,12]] [1,2,3,4,8,12,11,10,9,5,6,7]
[[1,2,3]] (one row) [1,2,3]
[[1],[2],[3]] (one column) [1,2,3]
[[7]] [7]

The idea: four walls that move in

Keep top, bottom, left, right. Walk the top row (then top++), the right column (then right--), the bottom row backwards (then bottom--), the left column upwards (then left++), and repeat while top <= bottom && left <= right.

First try: no checks inside the loop

import java.util.*;

public class Main {
    static List<Integer> spiral(int[][] a) {
        List<Integer> res = new ArrayList<>();
        int top = 0, bottom = a.length - 1, left = 0, right = a[0].length - 1;
        while (top <= bottom && left <= right) {
            for (int j = left; j <= right; j++) res.add(a[top][j]);
            top++;
            for (int i = top; i <= bottom; i++) res.add(a[i][right]);
            right--;
            for (int j = right; j >= left; j--) res.add(a[bottom][j]);
            bottom--;
            for (int i = bottom; i >= top; i--) res.add(a[i][left]);
            left++;
        }
        return res;
    }
    public static void main(String[] args) {
        System.out.println(spiral(new int[][]{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}}));
        System.out.println(spiral(new int[][]{{1, 2, 3}}));
        System.out.println(spiral(new int[][]{{1}, {2}, {3}}));
        System.out.println(spiral(new int[][]{{7}}));
    }
}

Output (real):

[1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7, 6]
[1, 2, 3, 2, 1]
[1, 2, 3, 2]
[7]

With one row, after the top row top = 1 > bottom = 0: the walls have crossed, but the loop body still walks "the bottom row", which is the same row backwards. The 3 × 4 example also gets an extra 6.

Solution in Java: check before the third and fourth side

import java.util.*;

public class Main {
    static List<Integer> spiral(int[][] a) {
        List<Integer> res = new ArrayList<>();
        int top = 0, bottom = a.length - 1, left = 0, right = a[0].length - 1;
        while (top <= bottom && left <= right) {
            for (int j = left; j <= right; j++) res.add(a[top][j]);
            top++;
            for (int i = top; i <= bottom; i++) res.add(a[i][right]);
            right--;
            if (top <= bottom) {
                for (int j = right; j >= left; j--) res.add(a[bottom][j]);
                bottom--;
            }
            if (left <= right) {
                for (int i = bottom; i >= top; i--) res.add(a[i][left]);
                left++;
            }
        }
        return res;
    }
    public static void main(String[] args) {
        System.out.println(spiral(new int[][]{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}}));
        System.out.println(spiral(new int[][]{{1, 2, 3}}));
        System.out.println(spiral(new int[][]{{1}, {2}, {3}}));
        System.out.println(spiral(new int[][]{{7}}));
    }
}

Output (real):

[1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]
[1, 2, 3]
[1, 2, 3]
[7]

Problem 3: set matrix zeroes (LeetCode 73)

If a cell is 0, set its entire row and column to 0, in place. Only the original zeros count.

Input Output
[[1,1,1],[1,0,1],[1,1,1]] [[1,0,1],[0,0,0],[1,0,1]]
[[0,1,2,0],[3,4,5,2],[1,3,1,5]] [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

Obvious idea 1: zero the row and column as soon as you see a 0

import java.util.*;

public class Main {
    static void setZeroes(int[][] a) {
        int m = a.length, n = a[0].length;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (a[i][j] == 0) {
                    for (int k = 0; k < n; k++) a[i][k] = 0;
                    for (int k = 0; k < m; k++) a[k][j] = 0;
                }
    }
    public static void main(String[] args) {
        int[][] a = {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
        int[][] b = {{0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}};
        setZeroes(a);
        setZeroes(b);
        System.out.println(Arrays.deepToString(a));
        System.out.println(Arrays.deepToString(b));
    }
}

Output (real):

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

The zeros we write are found later by the same loop, and they spread.

Obvious idea 2: search a copy, zero the real matrix

import java.util.*;

public class Main {
    static void setZeroes(int[][] a) {
        int m = a.length, n = a[0].length;
        int[][] old = new int[m][];
        for (int i = 0; i < m; i++) old[i] = a[i].clone();
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (old[i][j] == 0) {
                    for (int k = 0; k < n; k++) a[i][k] = 0;
                    for (int k = 0; k < m; k++) a[k][j] = 0;
                }
    }
    public static void main(String[] args) {
        int[][] a = {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
        int[][] b = {{0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}};
        setZeroes(a);
        setZeroes(b);
        System.out.println(Arrays.deepToString(a));
        System.out.println(Arrays.deepToString(b));
    }
}

Output (real):

[[1, 0, 1], [0, 0, 0], [1, 0, 1]]
[[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]

Correct, but O(m·n·(m + n)) time and O(m·n) extra memory. A 6000 × 6000 hall with one broken seat in ten:

        int n = 6000;
        int[][] a = new int[n][n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) a[i][j] = (i * 7 + j * 13) % 10 == 0 ? 0 : 1;
        long t0 = System.nanoTime(), zeros = 0;
        setZeroes(a);
        for (int[] row : a) for (int x : row) if (x == 0) zeros++;
        System.out.println(zeros + " zeros, " + (System.nanoTime() - t0) / 1000000 + " ms");

With the copy: Time Limit Exceeded (25 s) (3.6 million zeros × 12,000 writes each: over 4 × 10¹⁰).

The key insight: notes first, zero later, and keep the notes inside the matrix

We only need to know which rows and which columns contain a zero. Two boolean arrays would do it in O(m + n) memory. Better: row 0 stores the column notes and column 0 stores the row notes. Writing a 0 into a[0][j] is safe, because if column j has a zero, a[0][j] will be zeroed anyway. Since a[0][0] would be shared by row 0 and column 0, two flags (row0, col0) remember whether the first row or column had a zero before we wrote any notes.

1  2  3  4        1  0  3  0        1  0  3  0
5  0  7  8   →    0  0  7  8   →    0  0  0  0
9 10 11  0        0 10 11  0        0  0  0  0
13 14 15 16       13 14 15 16       13  0 15  0
 zeros            notes in row 0     inner cells from the notes;
                  and column 0       row0/col0 flags: false

Solution in Java

import java.util.*;

public class Main {
    static void setZeroes(int[][] a) {
        int m = a.length, n = a[0].length;
        boolean row0 = false, col0 = false;
        for (int j = 0; j < n; j++) if (a[0][j] == 0) row0 = true;
        for (int i = 0; i < m; i++) if (a[i][0] == 0) col0 = true;
        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                if (a[i][j] == 0) { a[i][0] = 0; a[0][j] = 0; }
        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                if (a[i][0] == 0 || a[0][j] == 0) a[i][j] = 0;
        if (row0) for (int j = 0; j < n; j++) a[0][j] = 0;
        if (col0) for (int i = 0; i < m; i++) a[i][0] = 0;
    }
    public static void main(String[] args) {
        int[][] a = {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
        int[][] b = {{0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}};
        setZeroes(a);
        setZeroes(b);
        System.out.println(Arrays.deepToString(a));
        System.out.println(Arrays.deepToString(b));
    }
}

Output (real):

[[1, 0, 1], [0, 0, 0], [1, 0, 1]]
[[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]

The big hall with this version: 36000000 zeros, 137 ms (every seat ends up zero, because a broken seat sits in every row and column).

A real bug: no flags

Without the last two lines (and the two flags), the original zeros in row 0 and column 0 are forgotten:

[[1, 0, 1], [0, 0, 0], [1, 0, 1]]
[[0, 1, 2, 0], [3, 4, 5, 0], [1, 3, 1, 0]]

The same solutions in C++

#include <bits/stdc++.h>
using namespace std;
using Grid = vector<vector<int>>;

void rotate(Grid& m) {
    int n = m.size();
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) swap(m[i][j], m[j][i]);   // transpose
    for (auto& row : m) reverse(row.begin(), row.end());          // mirror each row
}

vector<int> spiral(const Grid& a) {
    vector<int> res;
    int top = 0, bottom = a.size() - 1, left = 0, right = a[0].size() - 1;
    while (top <= bottom && left <= right) {
        for (int j = left; j <= right; j++) res.push_back(a[top][j]);
        top++;
        for (int i = top; i <= bottom; i++) res.push_back(a[i][right]);
        right--;
        if (top <= bottom) { for (int j = right; j >= left; j--) res.push_back(a[bottom][j]); bottom--; }
        if (left <= right) { for (int i = bottom; i >= top; i--) res.push_back(a[i][left]); left++; }
    }
    return res;
}

void setZeroes(Grid& a) {
    int m = a.size(), n = a[0].size();
    bool row0 = false, col0 = false;
    for (int j = 0; j < n; j++) if (a[0][j] == 0) row0 = true;
    for (int i = 0; i < m; i++) if (a[i][0] == 0) col0 = true;
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            if (a[i][j] == 0) { a[i][0] = 0; a[0][j] = 0; }
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            if (a[i][0] == 0 || a[0][j] == 0) a[i][j] = 0;
    if (row0) for (int j = 0; j < n; j++) a[0][j] = 0;
    if (col0) for (int i = 0; i < m; i++) a[i][0] = 0;
}

void show(const Grid& g) {
    for (auto& r : g) { for (size_t j = 0; j < r.size(); j++) cout << (j ? " " : "") << r[j]; cout << " | "; }
    cout << "\n";
}

int main() {
    Grid a = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    rotate(a); show(a);
    for (int x : spiral({{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}})) cout << x << " ";
    cout << "\n";
    for (int x : spiral({{1, 2, 3}})) cout << x << " ";
    cout << "\n";
    Grid b = {{0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}};
    setZeroes(b); show(b);
}

Output (real):

7 4 1 | 8 5 2 | 9 6 3 | 
1 2 3 4 8 12 11 10 9 5 6 7 
1 2 3 
0 0 0 0 | 0 4 5 0 | 0 3 1 0 |

The same solutions in Python

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


def spiral(a):
    res = []
    top, bottom, left, right = 0, len(a) - 1, 0, len(a[0]) - 1
    while top <= bottom and left <= right:
        for j in range(left, right + 1):
            res.append(a[top][j])
        top += 1
        for i in range(top, bottom + 1):
            res.append(a[i][right])
        right -= 1
        if top <= bottom:
            for j in range(right, left - 1, -1):
                res.append(a[bottom][j])
            bottom -= 1
        if left <= right:
            for i in range(bottom, top - 1, -1):
                res.append(a[i][left])
            left += 1
    return res


def set_zeroes(a):
    m, n = len(a), len(a[0])
    row0 = any(a[0][j] == 0 for j in range(n))
    col0 = any(a[i][0] == 0 for i in range(m))
    for i in range(1, m):
        for j in range(1, n):
            if a[i][j] == 0:
                a[i][0] = a[0][j] = 0
    for i in range(1, m):
        for j in range(1, n):
            if a[i][0] == 0 or a[0][j] == 0:
                a[i][j] = 0
    if row0:
        for j in range(n):
            a[0][j] = 0
    if col0:
        for i in range(m):
            a[i][0] = 0


a = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
rotate(a)
print(a)
print(spiral([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]))
print(spiral([[1, 2, 3]]), spiral([[1], [2], [3]]))
b = [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]]
set_zeroes(b)
print(b)

Output (real):

[[7, 4, 1], [8, 5, 2], [9, 6, 3]]
[1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]
[1, 2, 3] [1, 2, 3]
[[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]

Complexity

Problem Approach Time Extra memory Big test
Rotate write in place directly O(n²) O(1) wrong
Rotate second matrix O(n²) O(n²) 14000²: OutOfMemoryError
Rotate transpose + mirror O(n²) O(1) fits
Spiral four walls O(m·n) O(1) (plus the output) –
Zeroes zero as you go O(m·n·(m+n)) O(1) wrong
Zeroes copy O(m·n·(m+n)) O(m·n) 6000²: Time Limit Exceeded
Zeroes two boolean arrays O(m·n) O(m + n) fast
Zeroes row 0 / column 0 notes + 2 flags O(m·n) O(1) fast

Common mistakes

Mistake What you see (real) Why Fix
m[j][n-1-i] = m[i][j] in place [[7, 4, 1], [2, 5, 2], [1, 2, 1]] overwrote cells before reading them transpose + mirror (swaps)
A copy of a huge matrix OutOfMemoryError: Java heap space two copies don't fit in place
Transpose with j from 0 [[3, 2, 1], [6, 5, 4], [9, 8, 7]] each pair swapped twice j from i + 1
Spiral without the two checks [1, 2, 3, 2, 1] for one row walls crossed mid-lap if (top <= bottom), if (left <= right)
Zero rows and columns as you go almost everything is 0 new zeros spread notes first, zero later
No row0 / col0 flags [[0, 1, 2, 0], [3, 4, 5, 0], [1, 3, 1, 0]] the notes hide the original zeros check row 0 and column 0 first
a.length for the number of columns ArrayIndexOutOfBoundsException on non-square input rows ≠ columns columns = a[0].length

Mini project: a tiny photo editor

Represent a grayscale image as an int[][] of 0–255 values. Add commands: rotate right, rotate left, flip, and crop (copy a sub-rectangle). Print the image as characters (# for dark, . for light) after each command, and check that four rotate rights give back the original.

Practice

1. Spiral Matrix II (LeetCode 59): fill 1..n² in spiral order.

2. Rotate counter-clockwise in place.

3. Game of Life (LeetCode 289) in place: keep the next state in a second bit of each cell (the same "notes inside the matrix" idea).

Solutions
import java.util.*;

public class Main {
    // 1. Spiral Matrix II (LeetCode 59): fill 1..n² in spiral order, same four walls.
    static int[][] generate(int n) {
        int[][] g = new int[n][n];
        int top = 0, bottom = n - 1, left = 0, right = n - 1, v = 1;
        while (top <= bottom && left <= right) {
            for (int j = left; j <= right; j++) g[top][j] = v++;
            top++;
            for (int i = top; i <= bottom; i++) g[i][right] = v++;
            right--;
            if (top <= bottom) { for (int j = right; j >= left; j--) g[bottom][j] = v++; bottom--; }
            if (left <= right) { for (int i = bottom; i >= top; i--) g[i][left] = v++; left++; }
        }
        return g;
    }
    // 2. Rotate counter-clockwise: transpose, then reverse the order of the rows.
    static void rotateLeft(int[][] m) {
        int n = m.length;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) { int t = m[i][j]; m[i][j] = m[j][i]; m[j][i] = t; }
        for (int top = 0, bot = n - 1; top < bot; top++, bot--) { int[] t = m[top]; m[top] = m[bot]; m[bot] = t; }
    }
    // 3. Game of Life (LeetCode 289) in place: bit 0 = now, bit 1 = next (the same "notebook inside the matrix" idea).
    static void gameOfLife(int[][] b) {
        int m = b.length, n = b[0].length;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                int live = 0;
                for (int di = -1; di <= 1; di++)
                    for (int dj = -1; dj <= 1; dj++) {
                        if (di == 0 && dj == 0) continue;
                        int r = i + di, c = j + dj;
                        if (r >= 0 && r < m && c >= 0 && c < n) live += b[r][c] & 1;
                    }
                if ((b[i][j] & 1) == 1 && (live == 2 || live == 3)) b[i][j] |= 2;
                if ((b[i][j] & 1) == 0 && live == 3) b[i][j] |= 2;
            }
        for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) b[i][j] >>= 1;
    }
    public static void main(String[] args) {
        System.out.println(Arrays.deepToString(generate(3)));
        int[][] a = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        rotateLeft(a);
        System.out.println(Arrays.deepToString(a));
        int[][] life = {{0, 1, 0}, {0, 0, 1}, {1, 1, 1}, {0, 0, 0}};
        gameOfLife(life);
        System.out.println(Arrays.deepToString(life));
    }
}

Output (real):

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

Quick quiz

Clockwise is "transpose, then mirror each row". What turns a matrix counter-clockwise? A) transpose, then reverse the order of the rows B) transpose, then mirror each row C) transpose twice D) transpose only

Answer

A. The transpose of 1 2 3 / 4 5 6 / 7 8 9 is 1 4 7 / 2 5 8 / 3 6 9; reversing the order of the rows gives 3 6 9 / 2 5 8 / 1 4 7, a quarter turn counter-clockwise.

Interview questions

  1. Why can't you rotate by writing each cell to its new place? You overwrite cells you haven't read yet. Use swaps (transpose + mirror) or rotate four cells at a time in a cycle.
  2. What is the four-cell cycle method? For each layer, move top → right → bottom → left → top with one temporary variable; also O(1) memory.
  3. How do you avoid duplicates in spiral order? Re-check top <= bottom before the bottom row and left <= right before the left column.
  4. Why is it safe to use row 0 and column 0 as markers? A marked cell would be zeroed anyway; only the original zeros of row 0 and column 0 need the two flags.
  5. What changes for an m × n rotation? It cannot be in place in the same array shape; you need an n × m result.
  6. Time and space of each optimal solution? All O(m·n) time and O(1) extra space.

Glossary

Term Meaning
Matrix / 2D array A grid; a[i][j] is row i, column j
In place Change the input itself with O(1) extra memory
Transpose Swap a[i][j] and a[j][i]
Main diagonal Cells (i, i)
Mirror a row Reverse it with two pointers
Spiral order Outer ring clockwise, then inner rings
Wall / boundary top, bottom, left, right of the unread part
Marker / note A value written to remember something
Flag A boolean remembering one fact
Heap Java's memory for objects, with a fixed maximum
OutOfMemoryError Thrown when the heap has no room

Summary

  • In place means never overwriting a cell before you have read it.
  • Rotate clockwise = transpose (upper triangle) + mirror each row; counter-clockwise = transpose + reverse the rows.
  • Spiral = four walls moving inward, re-checked before the third and fourth side.
  • Set zeroes = notes first, zero later; keep the notes in row 0 and column 0, with two flags for those lines themselves.
  • All three run in O(m·n) time with O(1) extra memory.
  • Next episode: design problems: insert-delete-getRandom O(1) and the LFU cache.