Lists and 2D grids¶

~20 min · prerequisite: Part 3, Data (lists and slicing)

What you will be able to do¶

Read, change, and slice a list, and tell which operations copy data and which change it in place.
Build a 2D grid with separate rows, avoiding the [[0] * m] * n trap.
Visit the neighbours of a grid cell without reading outside the grid.

The idea¶

A list is an ordered row of values. Each value has an index, and the first index is 0. A list can hold any mix of values, including other lists. Think of numbered gym lockers: locker 0 is the leftmost, and len(a) counts the lockers. The index -1 means the last locker, a trap in grids.

Operations differ in cost. a.append(x) and a.pop() work at the end and move no other value. a.pop(0) and a.insert(0, x) shift every value, so their cost grows with the length of the list. The Python wiki's time complexity page lists these costs. A contest input can hold 200,000 numbers, so shifting inside a loop can run past the time limit. Lesson 4 shows a structure for removing items from the front.

A slice such as a[1:4] makes a new list of the values at indexes 1, 2, and 3.

A 2D grid is a list of lists. The expression grid[r][c] reads row r, column c. Build an empty grid like this:

n, m = 2, 3
grid = [[0] * m for _ in range(n)]

The comprehension makes a new row each time. The expression [[0] * m] * n repeats one row reference n times, so every row is the same list.

When you step to a neighbouring cell, check that it is inside the grid with 0 <= r < n and 0 <= c < m. A negative index does not raise an error. It wraps around to the end of the list.

Worked example¶

def neighbours(r: int, c: int, n: int, m: int) -> list[tuple[int, int]]:
    result = []
    for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        nr = r + dr
        nc = c + dc
        if 0 <= nr < n and 0 <= nc < m:
            result.append((nr, nc))
    return result

grid = [[0] * 3 for _ in range(2)]
grid[0][1] = 7
print(grid)
print(neighbours(0, 0, 2, 3))

The output is:

[[0, 7, 0], [0, 0, 0]]
[(1, 0), (0, 1)]

Line by line, this is what Python does:

The loop visits four offsets: up, down, left, and right. dr, dc unpacks each pair.
nr and nc hold the new cell. The if keeps it only when both coordinates are inside the grid, so for (0, 0) the moves up and left are dropped.

Try it¶

The block compares the two ways of building a grid.

def build_grids():
    bad = [[0] * 3] * 2
    good = [[0] * 3 for _ in range(2)]
    bad[0][0] = 9
    good[0][0] = 9
    return bad, good

bad, good = build_grids()
assert bad == [[9, 0, 0], [9, 0, 0]]
assert good == [[9, 0, 0], [0, 0, 0]]
assert bad[0] is bad[1]
assert good[0] is not good[1]

Common mistakes¶

Building a grid with * n on a row. After grid = [[0] * 3] * 2 and grid[0][0] = 9, the grid prints [[9, 0, 0], [9, 0, 0]]. No error appears, but every row changed. Use the comprehension.
Using an index past the end. Running a = [1, 2, 3] and then print(a[3]) gives:
```
IndexError: list index out of range
```
Indexing with a tuple. Writing grid[r, c] instead of grid[r][c] gives:
```
TypeError: list indices must be integers or slices, not tuple
```
Trusting a negative index. If r is 0 and you read grid[r - 1][c] without a bounds check, Python reads the last row and no error appears.

Practice¶

Write the function named in each problem. The samples are checks.

Row sums (easy). Write row_sums(rows). Return the sum of each row. Sample: row_sums([[1, 2, 3], [4, 5, 6]]) returns [6, 15].
Border count (easy). Write border_count(grid). The argument is a list of equal-length strings. Count the cells on the outer edge of the grid. Sample: border_count(["abcd", "efgh", "ijkl"]) returns 10.
Adjacent pairs (medium). Write adjacent_pairs(grid). # marks a filled cell and . an empty one. Count the pairs of filled cells that touch horizontally or vertically. Sample: adjacent_pairs(["##.", ".##", "#.."]) returns 3.
Rotate clockwise (medium). Write rotate_cw(grid). Return the grid turned 90 degrees clockwise. Sample: rotate_cw([[1, 2, 3], [4, 5, 6]]) returns [[4, 1], [5, 2], [6, 3]].
Islands (stretch). Write count_islands(grid) with the same # and . strings. Filled cells that connect horizontally or vertically form one island. Return the number of islands. Sample: count_islands(["##..", "#..#", "..##"]) returns 2.

Solution

```python def row_sums(rows): return [sum(row) for row in rows]

assert row_sums([[1, 2, 3], [4, 5, 6]]) == [6, 15] ```

```python def border_count(grid): n, m = len(grid), len(grid[0]) total = 0 for r in range(n): for c in range(m): if r in (0, n - 1) or c in (0, m - 1): total += 1 return total

assert border_count(["abcd", "efgh", "ijkl"]) == 10 ```

```python def adjacent_pairs(grid): n, m = len(grid), len(grid[0]) total = 0 for r in range(n): for c in range(m - 1): if grid[r][c] == "#" and grid[r][c + 1] == "#": total += 1 for r in range(n - 1): for c in range(m): if grid[r][c] == "#" and grid[r + 1][c] == "#": total += 1 return total

assert adjacent_pairs(["##.", ".##", "#.."]) == 3 ```

```python def rotate_cw(grid): return [list(col) for col in zip(*grid[::-1])]

assert rotate_cw([[1, 2, 3], [4, 5, 6]]) == [[4, 1], [5, 2], [6, 3]] ```

grid[::-1] reverses the rows, so zip reads each column from the bottom up.

```python def count_islands(grid): n, m = len(grid), len(grid[0]) seen = [[False] * m for _ in range(n)] islands = 0 for r in range(n): for c in range(m): if grid[r][c] == "#" and not seen[r][c]: islands += 1 stack = [(r, c)] seen[r][c] = True while stack: x, y = stack.pop() for nx, ny in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]: if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] == "#" and not seen[nx][ny]: seen[nx][ny] = True stack.append((nx, ny)) return islands

assert count_islands(["##..", "#..#", "..##"]) == 2 ```

Recap¶

A list keeps its order. append and pop() at the end are cheap, but pop(0) shifts every value.
Build grids with [[0] * m for _ in range(n)], never with * n applied to a row.
Check 0 <= r < n and 0 <= c < m before you use neighbour coordinates, because -1 is a valid index.