Matrices & Simulation

Almost. In C, a 2D array is one block, row after row. In Java, int[][] is an array of references to row arrays (JLS chapter 10). Each row is its own int[], but the rows can sit anywhere in the heap. Reading along a row is still the fast direction. Need one truly continuous block? Use a flat int[rows * cols] with r * cols + c.

Every row holds exactly cols cells. So the first cols indices are row 0, the next cols are row 1, and so on. Dividing by cols counts how many full rows come before index i. The remainder i % cols is how far into that row you are.

In a grid, row 0 is at the top and row numbers grow as you go down, like lines in a file or pixels on a screen. So moving up means going to a smaller row: r - 1. Moving down is r + 1, left is c - 1, right is c + 1. That's why {{-1,0},{0,1},{1,0},{0,-1}} reads up, right, down, left: clockwise.

Watch one row. After a clockwise turn, the top row becomes the right column, and row 1 becomes the column just left of it. So old row r lands in column n − 1 − r. Along that row, left-to-right becomes top-to-bottom, so old column c becomes row c. Check on the 3 × 3 example: 7 sits at (2, 0) and moves to (0, 0) — the top-left of [[7,4,1],…].

Counter-clockwise: transpose, then reverse each column (or reverse each row first, then transpose). 180°: reverse the order of the rows, then reverse each row. Or rotate clockwise twice. Write the mapping first: 180° sends (r, c) to (n − 1 − r, n − 1 − c).

When top == bottom, one row is still left to print. Take [[1, 2, 3]]: top = 0 and bottom = 0 at the start. With <, the loop never runs and you return an empty list. The walls are inclusive — both top and bottom are rows you still have to print. Same for left and right.

Each corner belongs to exactly one side, because a wall moves right after its side is walked. The top row prints both top corners, then top++. So the right column starts one row lower and skips the top-right corner. Then right--, so the bottom row skips the bottom-right corner. Then bottom--, so the left column skips the bottom-left one. Dry-run a 3 × 3 once with the sim and watch the four walls move. Simple hai.

The top and bottom rows are visited only once per trip; the middle rows are visited twice. With numRows = 4, going down covers rows 0, 1, 2, 3 (4 characters). Coming back up covers only rows 2 and 1 (2 characters), because row 3 and row 0 belong to the next trip. That's 4 + 2 = 6 = 2 · 4 − 2. Row 0 then takes indices 0, 6, 12, …

No. By the usual interview convention, the space you must return doesn't count. Say it out loud: "O(1) extra space besides the output."

Because the zeros you write look exactly like original zeros. When the scan reaches them, it wipes more rows and columns that should have stayed. Record which rows and columns must go first, then write.

A mark in matrix[r][0] means row r will become all zeros, so that cell was going to be 0 anyway. The same holds for matrix[0][c]. The only facts you'd lose are row 0's and column 0's own zeros, so you save those in two booleans before marking.

Every cell must change at the same moment. If you update (0, 0) first, then (0, 1) counts the new (0, 0) instead of the old one, and the generation comes out wrong. Keep the old state readable: a copy, or the old state in bit 0.

Think of each cell as a two-digit binary number: the right digit is now, the left digit is next. So 0 = 00, 1 = 01, 2 = 10, 3 = 11. cell & 1 reads only the right digit (now). That's why a cell holding 2 (born next) still counts as dead for its neighbours: 2 & 1 = 0. cell |= 2 sets the left digit to 1 ("alive next") without touching the right one. cell >>= 1 drops the right digit, so next becomes now: 3 → 1, 2 → 1, 1 → 0, 0 → 0.

Read the problem first. Rotate Image says "do not allocate another matrix", so a copy breaks the rule there. Set Matrix Zeroes asks for in place, and its follow-up asks for O(1) space: the row and column flags (O(m + n)) are a good first answer. In Game of Life, solving it in place is the follow-up, so a copy first is fine. Say the cost out loud. Then offer the in-place version: "I can drop the extra space by keeping the marks inside the matrix." A working simple answer beats a half-written clever one.