Learn

You changed one cell of your grid and the whole column changed with it

2 November 2026 · One mistake, one counterexample

You need a grid of zeros, so you write one short line and move on to the interesting part. The search runs, the sample passes, and then on a tiny open board your code reports that the far corner cannot be reached. Nothing in the search is wrong. The grid was never a grid.

The situation

The task is to mark some cells of a board as walls and then search it. Building the board is the part nobody thinks about:

def mark_walls(rows, cols, walls):
    grid = [[0] * cols] * rows
    for r, c in walls:
        grid[r][c] = 1
    return grid

On a one-row board this is correct, and many samples are wide rather than tall, so it passes. The trouble needs two rows.

The input that breaks it

Call mark_walls(2, 2, [(0, 1)]). You expect [[0, 1], [0, 0]]: one wall, top right. You get [[0, 1], [0, 1]]. The wall appears in every row.

The reason is what each * copies. The inner [0] * cols repeats a number, and numbers cannot be changed in place, so writing to one slot simply puts a new value there. The outer * rows repeats a reference to that one inner list. There are not two rows; there are two names for the same row. Writing to grid[0][1] writes to grid[1][1], because they are the same slot. One line at the console proves it: grid[0] is grid[1] prints True.

The same mistake in a visited grid is worse, because it fails quietly. Take a two-by-two board with no walls, start at the top left and search for the bottom right. Marking the start visited also marks the cell below it, so the search never steps down. Stepping right marks the target in the second row as visited before anyone has reached it. The search ends and reports the target unreachable, on a board with no walls at all.

Java has the same trap, one step further from the obvious:

int[][] grid = new int[rows][];
int[] row = new int[cols];
Arrays.fill(grid, row);   // every entry points at one array
grid[0][1] = 1;           // grid[1][1] is now 1 as well

new int[rows][cols] gives each row its own array, and is also shorter.

The hidden assumption is repeating a row makes copies of it. It does for numbers. It does not for lists, arrays or any other object you can change in place.

The fix and the invariant

Build each row separately:

grid = [[0] * cols for _ in range(rows)]

The comprehension runs [0] * cols once per row, so each row is a new list. On the same input, mark_walls(2, 2, [(0, 1)]) now returns [[0, 1], [0, 0]], and grid[0] is grid[1] is False. Keeping [0] * cols for the inner list is fine, because what it repeats is a number.

The invariant to say: every row is its own object, so writing one cell changes exactly one cell.

What to say out loud

When you write the line that builds the grid, say: "I'm building each row separately, so the rows don't share storage. Writing one cell changes only that cell." It takes four seconds, and it tells the interviewer you know the difference between copying a value and copying a reference.

If the bug has already happened, name the input before you touch the code: "Two by two, one wall at the top right, and it shows up in both rows. That means my rows are the same list. I multiplied a list of lists." Then fix the one line. Saying the cause before the fix shows you diagnosed it, rather than changing lines until the output looked right.

The exercise

1. Search your last ten practice solutions for a list multiplied by a number where the thing repeated is itself a list, and for Arrays.fill with an array as the value.
2. For each one, predict in writing what grid[0] is grid[1] (or grid[0] == grid[1] on Java references) prints, then check.
3. Run the two-by-two search above by hand with the shared visited grid, and write down the step at which the target is wrongly marked.
4. Find the same trap in a dictionary: dict.fromkeys(names, []) gives every key one shared list. Write the two-key input that shows it.
5. In your next practice problem, say the "each row is its own object" sentence aloud as you build the grid.

Where this fits in Gadfly

Gadfly has four rooms, and in the algorithms room you code in Java or Python. In tutor mode it asks the next question instead of revealing the solution, so "what does your grid look like after the first wall is placed?" is the kind of question it would ask when a search goes wrong. "I'm stuck" gives one more step, up to pseudocode, never finished code.