Master Grid and Matrix Neighbour Traversal for DSA Interviews. Discover Why Python's Negative Indexing Can Silently Return the Wrong Cell, How Boundary Checks Prevent Bugs, and How to Solve Grid-Based Coding Problems Correctly.
The interview insight: Python doesn't always throw an error when you cross a boundary. Sometimes, it takes you somewhere you never intended to go.
In many languages, an index of −1 crashes your program. In Python, it quietly works, and it gives you the last item. That is how a small grid bug can walk a worker to the wrong end of a warehouse.
The problem at Varastra
Varastra is an online store for Indian ethnic wear. Its warehouse stores sarees on racks. Each rack is a grid. The rows run from top to bottom. The columns run from left to right. Each cell is a bin with a number.
One Tuesday, a picker named Leo walked to the far end of the warehouse for no reason. (This story is made up.)
He had a restock slip. It told him to check the bins next to bin (0, 0), the top-left corner of Rack 3, for overflow. The slip listed bin (−1, 0) as one of the neighbours. There is no row minus one. But the system did not complain. It sent him to the bottom row of the rack, at the other end of the aisle.
Sam, a senior engineer, put the slip on the table. Dev wrote the code. Dev looked at it. "I checked that the row is not past the end," he said. "I forgot to check that it is not before the start."
"And Python did not stop you," Sam said.
"No. It took minus one and gave me the last row."
What a grid is
A grid is a list of lists. grid[r][c] is the cell in row r and column c. Both start at 0.
grid = [
[4, 7, 0, 3], # row 0
[2, 9, 5, 1], # row 1
[6, 0, 8, 2], # row 2
]
print(grid[1][2]) # 5
Reading one cell costs O(1). Walking the whole grid with r rows and c columns costs O(r × c).
Why minus one does not fail
In Python, a negative index counts from the end. a[-1] is the last item. a[-2] is the one before it. That is a handy feature in many places.
print(grid[-1]) # [6, 0, 8, 2] (the last row)
print(grid[-1][0]) # 6
print(grid[2][0]) # 6 (the same cell)
Now look at the diagram. Take cell (0, 0). Step "up" and you get row −1. Python does not say "this row does not exist." It says "the last row," which is row 2. So the code returns cell (2, 0), the wrong cell, with no error.
The buggy code
First, the four directions: up, down, left and right. Each is a step in row and column.
DIRS4 = [(-1, 0), (1, 0), (0, -1), (0, 1)]
Here is Dev's code. It checks only the upper bounds.
def neighbours_bad(grid, r, c):
out = []
for dr, dc in DIRS4:
nr, nc = r + dr, c + dc
if nr < len(grid) and nc < len(grid[0]):
out.append((nr, nc))
return out
Pause and predict
Before you run the buggy code: how many neighbours do you think neighbours_bad returns for the corner cell (0, 0)?
Answer: Four. It keeps (−1, 0) and (0, −1), and neither is a real cell.
Run it on cell (0, 0) of the grid above.
print(neighbours_bad(grid, 0, 0))
# [(-1, 0), (1, 0), (0, -1), (0, 1)]
There are four cells in the answer. A corner cell has only two real neighbours. The two extra ones, (−1, 0) and (0, −1), are not real. When code later uses them as grid[nr][nc], Python quietly reads from the wrong side of the grid.
The half fix that still fails
Tara, a new intern, tries to fix it by checking only the lower bound.
def neighbours_low_only(grid, r, c):
out = []
for dr, dc in DIRS4:
nr, nc = r + dr, c + dc
if nr >= 0 and nc >= 0:
out.append((nr, nc))
return out
Now (0, 0) is correct. But try the bottom-right corner.
print(neighbours_low_only(grid, 2, 3))
# [(1, 3), (3, 3), (2, 2), (2, 4)]
The cells (3, 3) and (2, 4) do not exist. Reading grid[3][3] raises IndexError: list index out of range. Fixing one edge is not enough. A cell has four edges.
The fix: check both bounds, every time
def neighbours(grid, r, c):
out = []
for dr, dc in DIRS4:
nr, nc = r + dr, c + dc
if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]):
out.append((nr, nc))
return out
The chain 0 <= nr < len(grid) checks both ends in one line. Learn to read it as "nr is inside the rack."
The cost is O(1) for each call, because it checks only four directions.
Test the corners
Bugs hide at the edges. So test the edges first. For a grid with 3 rows and 4 columns:
grid = [[4, 7, 0, 3], [2, 9, 5, 1], [6, 0, 8, 2]]
assert sorted(neighbours(grid, 0, 0)) == [(0, 1), (1, 0)]
assert len(neighbours(grid, 1, 1)) == 4
assert sorted(neighbours(grid, 2, 3)) == [(1, 3), (2, 2)]
assert neighbours([[1]], 0, 0) == []
assert grid[-1][0] == grid[2][0] # shows why the bug was silent
print("all tests pass")
- Cell (0, 0) has two neighbours: (0, 1) and (1, 0). These are the two cells highlighted in the diagram.
- Cell (1, 1) has four neighbours.
- Cell (2, 3) has two neighbours: (1, 3) and (2, 2).
- A grid with one cell has no neighbours.
Try it
Call neighbours(grid, 1, 0) and neighbours_bad(grid, 1, 0). The cell is in the middle of the left edge. What do you expect?
The fixed version returns three cells: (0, 0), (2, 0) and (1, 1). The buggy version adds a fourth one, (1, −1), which wraps to the last column.
A second grid trap: repeated rows
While Tara was at it, she found another quiet bug. Dev built a new rack like this.
def make_grid_bad(rows, cols, fill):
return [[fill] * cols] * rows
It looks right. But * rows does not make new rows. It repeats the same row object. Change one cell and every row changes.
x = make_grid_bad(3, 3, 0)
x[0][0] = 5
print([row[0] for row in x]) # [5, 5, 5]
The fix makes a fresh row each time.
def make_grid(rows, cols, fill):
return [[fill] * cols for _ in range(rows)]
y = make_grid(3, 3, 0)
y[0][0] = 5
print([row[0] for row in y]) # [5, 0, 0]
The [fill] * cols part is safe for numbers, strings and None. Those cannot change in place. It is not safe if fill is itself a list.
Row and column totals
Varastra also wants to know how many sarees sit in each row and each column of a rack.
def row_col_totals(grid):
if not grid:
return [], []
rows = [sum(row) for row in grid]
cols = [0] * len(grid[0])
for row in grid:
for j, v in enumerate(row):
cols[j] += v
return rows, cols
print(row_col_totals(grid)) # ([14, 17, 16], [12, 16, 13, 6])
Every cell is visited once. The time is O(r × c). The extra space is O(r + c). On a 1,000 × 1,000 grid, it took about 0.07 seconds in this test, on one machine.
Test the empty grid too. grid[0] would fail on it, so the if not grid line guards that.
Other languages
In Java, a negative array index throws an exception. In C++, it is undefined behaviour, and the program may read garbage. In Python, it quietly wraps. Python is kind here, but only if you meant to wrap. If you did not mean it, the bug hides.
How to spot a grid problem
- The problem has rows and columns, a board or a map. Draw it with coordinates first.
- The problem asks about neighbours. Write the direction list once. Check both bounds for each step.
- The problem asks for totals per row or column. Allocate the list for each one before you loop.
In an interview, say it out loud:
"I will check that the row and the column are both at least 0 and less than the size, because Python accepts negative indexes."
Takeaway: In Python, a negative index does not fail. It wraps. Check both bounds for every grid step, and test the corners.