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 rowi, columnj.int[][]in Java is an array of row arrays. - n × n (square) / m × n:
mrows andncolumns. - 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]witha[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 (
lfrom the left,rfrom the right). - Spiral order: reading the outer ring clockwise, then the next ring, and so on.
- Boundary / wall: the variables
top,bottom,left,rightmarking the part not read yet. - Marker / note: a value written to remember something for a later pass.
- Flag: a
booleanthat remembers one yes/no fact. - Heap (Java memory): where
newobjects live; its maximum size is fixed when the program starts. - OutOfMemoryError: what Java throws when
newcannot 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
- 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.
- What is the four-cell cycle method? For each layer, move
top → right → bottom → left → topwith one temporary variable; also O(1) memory. - How do you avoid duplicates in spiral order? Re-check
top <= bottombefore the bottom row andleft <= rightbefore the left column. - 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.
- What changes for an m × n rotation? It cannot be in place in the same array shape; you need an
n × mresult. - 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.