Two-dimensional lists and matrix problems in Python

Why it matters

Grids are everywhere. A game board is a grid of squares. A photo is a grid of pixels. A seating plan, a spreadsheet, a city map and a timetable are all grids. Matrix questions, which are questions about grids of numbers, are a favourite in technical interviews because they test whether you can keep track of two indexes at once without making a mistake.

This lesson builds the idea from the ground up. You will create grids, read them, change them, and solve four classic problems: transpose, rotate, spiral order and search. You will also see how a grid becomes a graph, which is the bridge to the graph module.

First principles: a list of lists

A two-dimensional array is an array whose boxes are themselves arrays. Python has no separate type for this. You build it as a list of lists: an outer list whose boxes are inner lists. Think of a cinema. The whole hall is one list, and each row of seats is a list inside it. To find one seat you need two numbers: which row, and which seat in that row. The row number is the first index, and the seat number is the second.

The expression m[1][2] means "take the list at index 1 of m, then take the box at index 2 inside it". It is read left to right, one bracket pair at a time, the same way you would find a seat by first finding its row.

Output:

6
3
3

Read the output carefully. m[1][2] is the value 6, because row 1 is [4, 5, 6] and column 2 is its third value. len(m) is 3, the number of rows, because the outer list has three boxes. len(m[0]) is 3, the length of the first row, which is the number of columns.

Each row is a separate list object in memory, and the outer list holds a reference to each row. This is why the grid has two lengths: the outer length counts rows, and the length of any one row counts its columns.

The literal above has a trailing comma after the last row and after the last value. Python allows it, and it makes the lines easier to add, remove or reorder when the grid is long.

Creating and filling a grid

There are three common ways to create a two-dimensional list. The first is a list comprehension, which builds a list by running a short loop inside brackets. [[0] * 3 for _ in range(2)] makes two rows of three zeros. The second is a literal, such as the one above, which lists the rows directly. The third is a jagged list, where each row has its own length:

Output:

[[1], [2, 3], [4, 5, 6]]
3

Jagged lists are legal, and they appear in some problems, such as a list of lists with uneven lengths. Most matrix problems assume a rectangle, where every row has the same length. When you read a problem, check which one it is. If the problem says "matrix", it is almost always a rectangle.

The list comprehension is the one to use for a grid of zeros. The shorter form [[0] * 3] * 2 looks the same, but it does something different, and the common mistakes section shows why it is dangerous.

Two rules keep you safe. The number of rows is len(m). The number of columns is len(m[0]), but only if len(m) is greater than 0. An empty grid has no first row, and m[0] raises IndexError.

Each row of a grid is a separate list object in memory, and the outer list holds one reference per row. A grid of 1,000 rows and 1,000 columns therefore creates 1,001 list objects. That is cheap, but it has a useful side effect. A row can be replaced or moved on its own, by changing one reference in the outer list. Swapping two rows is one line, m[i], m[j] = m[j], m[i], and it moves no individual values. The counter-clockwise rotation in the practice set uses the same idea.

Printing and looping

Printing m with print(m) shows the whole grid in one line, with each row in brackets. For a grid with one value per line, use a loop with print, or join the values of each row into text with " ".join(...).

The standard loop rule is that the row index goes on the outside and the column index on the inside. Python gives you a shorter form for the rows: for row in m: gives each row in turn, and for value in row: gives each value in that row. Use the index form, for i in range(len(m)), when you need to change a value in place or compare a cell with its neighbour.

Output:

1 2 3
4 5 6
7 8 9

The expression " ".join(str(v) for v in row) turns each number into text, then joins the pieces with a single space between them. It does not leave a trailing space at the end of the line, so the output matches what you would expect to see.

The inner loop in a grid program should use len(row), or len(m[i]), rather than len(m[0]). That is what makes the loop work for a jagged list, where row i may have a different length.

Worked example: row and column sums

A common task is to total each row and each column. The idea is that a single pass over every cell can add its value to two running totals: its row total and its column total. Keep one list of row totals and one list of column totals, sized from the grid's dimensions.

Save the program as main.py. Run it with python3 main.py, then type 2 3 and press Enter. Then type 1 2 3, press Enter, and type 4 5 6.

rows, cols = map(int, input().split())
m = [[int(x) for x in input().split()] for _ in range(rows)]
 
row_sums = [sum(row) for row in m]
col_sums = [sum(col) for col in zip(*m)]
print("Row sums:", row_sums)
print("Column sums:", col_sums)

Output:

Row sums: [6, 15]
Column sums: [5, 7, 9]

The row sums use one call to sum per row. The column sums use zip(*m). The star in *m passes each row as a separate argument, and zip then gives back the columns, one tuple per column. A tuple is a fixed group of values written in parentheses, such as (1, 4). The call zip(*m) is the way to turn rows into columns in Python, and the transpose section uses it again.

The loop version shows what happens inside. For each cell, add its value to row_sums[i] and to col_sums[j]. That is O(rows times cols) time, because each cell is visited once, and O(rows plus cols) extra space. The row totals and the column totals each add up to the same grand total, 21. Checking that the two totals match is a quick way to catch a typo in the loops.

Transpose: swapping rows and columns

The transpose of a matrix turns its rows into its columns. The value at row i, column j moves to row j, column i. A 2 by 3 grid becomes a 3 by 2 grid. The first row of the result is the first column of the original.

For a rectangle, you cannot swap in place, because the shape changes. In Python, zip(*m) builds the transpose in one line, because it returns the columns. Each column comes back as a tuple, so list(col) turns it into a list.

Save the program as main.py. Type 2 3, then 1 2 3, then 4 5 6, one line each.

rows, cols = map(int, input().split())
m = [[int(x) for x in input().split()] for _ in range(rows)]
 
t = [list(col) for col in zip(*m)]
for row in t:
    print(" ".join(str(v) for v in row))

Output:

1 4
2 5
3 6

The new grid t has cols rows and rows columns. The first line of the output is the first column of the original, which is 1 and 4. Now it is the first row.

The same result with explicit indexes uses a new grid of the flipped shape, t = [[0] * rows for _ in range(cols)], and the copy t[j][i] = m[i][j]. That copy looks backwards at first, but it is exactly the definition. The value at m[0][2], which is 3, goes to t[2][0], the third row, first column of the result.

For a square grid, you can transpose in place by swapping only the cells above the diagonal, where the column index is greater than the row index. Swapping the whole square would swap every pair twice and change nothing. The common mistakes section has the details.

Rotation: turning a square 90 degrees

Rotating a square grid by 90 degrees clockwise is a favourite interview question, because the answer looks like a puzzle until you see the trick. The trick is two simple steps.

First, transpose the square. Second, reverse each row. Check it on a 3 by 3 grid. Start with rows 1 2 3, 4 5 6, 7 8 9. The transpose gives rows 1 4 7, 2 5 8, 3 6 9. Reversing each row gives 7 4 1, 8 5 2, 9 6 3. That is the clockwise rotation: the old left column, read from bottom to top, became the new top row.

Because the rotation is done in place, the grid must be changed without making a new one. The transpose swaps the cells above the diagonal, and the reversal uses row.reverse(), which reverses one list in place. Save the program as main.py, then type 3, and the three rows 1 2 3, 4 5 6 and 7 8 9, one line each.

n = int(input())
m = [[int(x) for x in input().split()] for _ in range(n)]
 
for i in range(n):
    for j in range(i + 1, n):
        m[i][j], m[j][i] = m[j][i], m[i][j]
for row in m:
    row.reverse()
 
for row in m:
    print(" ".join(str(v) for v in row))

Output:

7 4 1
8 5 2
9 6 3

The transpose loop starts j at i + 1, so each pair above the diagonal is swapped exactly once. The reversal uses row.reverse(), which changes the row where it sits. Time is O(n squared) for an n by n grid, because each cell is touched a constant number of times. Space is O(1) extra, since the rotation happens in place.

Why does rotating counter-clockwise need a different recipe? Because the reverse-then-transpose order gives counter-clockwise instead. Both are correct for their direction. Check the direction on a small example before you rely on it, since a sign error here turns a clockwise answer into a counter-clockwise one. A short way to get a clockwise turn into a new grid is [list(row) for row in zip(*m[::-1])]. The slice m[::-1] reverses the rows first, and zip then transposes the result. The slice rule is covered earlier, in the prefix sums lesson.

Spiral order

Spiral order reads a grid in a spiral: across the top from left to right, down the right side, back along the bottom from right to left, up the left side, then repeat on the inner grid that remains. For a 3 by 3 grid it visits the values in the order 1, 2, 3, 6, 9, 8, 7, 4, 5.

The way to write this is to keep four borders, top, bottom, left and right. They mark the rectangle that has not been read yet. Each time you finish one side of the spiral, you move that border inward, so the next side is one step smaller. The loop stops when the borders cross.

Save the program as main.py. Type 2 3, then 1 2 3, then 4 5 6. The program below reads a grid and prints its spiral order.

def spiral(m):
    out = []
    top, bottom = 0, len(m) - 1
    left, right = 0, len(m[0]) - 1
    while top <= bottom and left <= right:
        for j in range(left, right + 1):
            out.append(m[top][j])
        top += 1
        for i in range(top, bottom + 1):
            out.append(m[i][right])
        right -= 1
        if top <= bottom:
            for j in range(right, left - 1, -1):
                out.append(m[bottom][j])
            bottom -= 1
        if left <= right:
            for i in range(bottom, top - 1, -1):
                out.append(m[i][left])
            left += 1
    return out
 
rows, cols = map(int, input().split())
m = [[int(x) for x in input().split()] for _ in range(rows)]
print(spiral(m))

Output:

[1, 2, 3, 6, 5, 4]

Trace the first loop. The borders start at top = 0, bottom = 1, left = 0, right = 2. The first for adds the top row, 1, 2, 3. Then top moves to 1. The second for adds the right column below the top, which is m[1][2], the value 6. Then right moves to 1. Now top <= bottom is still true, so the bottom row is read from right back to left. That reads m[1][1] and m[1][0], which are 5 and 4. The bottom border moves to 0, so bottom is now 0. The left <= right check is true, so the left column from bottom up to top is read. Since bottom is 0 and top is 1, that range is empty, and left moves to 1. The next pass of the outer loop checks top <= bottom as 1 <= 0, which is false, so the loop ends.

The range range(right, left - 1, -1) counts down from right to left, and it includes left. The stop value is left - 1, because a range never includes its stop value. Counting down is the reason for the -1 step.

The two if checks matter. They stop the program from reading the same row or column twice when a single row or column is left over. For a 1 by 3 grid, after the top row is read, top is 1 and bottom is 0, so the bottom row must not be read again. The if guards stop that duplicate read.

These are the results for four grids. A 3 by 3 grid gives [1, 2, 3, 6, 9, 8, 7, 4, 5], and the centre value 5 is read last, once, because the inner grid shrinks to a single cell. A 1 by 3 grid gives [1, 2, 3], and a 3 by 1 grid gives [1, 2, 3] too.

Each cell is added exactly once, so the time is O(rows times cols), and the space for the output is the same. The extra working space is a few indexes.

Searching a sorted grid

Suppose each row is sorted from left to right, and each column is sorted from top to bottom. Such a grid is common in data tables. A search for one value does not need to look at every cell. Start at the top-right corner. If its value is bigger than the target, the rest of its column is bigger too, so you can drop that column and move left. If the value is smaller than the target, the rest of its row is smaller too, so you can drop that row and move down.

Each step removes one row or one column, so the search takes at most rows + cols steps, which is O(rows plus cols). Compare that with checking every cell, which is O(rows times cols).

Output:

Found at row 1, column 1
Not found

Trace the target 5. The start cell is row 0, column 3, which holds 11. That is bigger than 5, so column 3 is dropped and c becomes 2. The cell m[0][2] holds 7, still bigger, so c becomes 1. The cell m[0][1] holds 4, which is smaller than 5, so row 0 is dropped and r becomes 1. The cell m[1][1] holds 5, which is the target. The function returns the row and the column.

Try the target 10 in your head before you run it. The path is different, and the answer is Not found. The search tells you a value is missing without having seen every cell, which is the point of the sorted structure.

This method needs the sorted rows and columns, and it needs a corner that has one bigger direction and one smaller direction. The top-right corner has that property. The top-left corner does not, because both its neighbours are bigger.

Grids as graphs: counting islands

A grid is also a graph. Each cell is a node, and two cells are connected when they touch on one side. Many grid problems are really graph problems in disguise. The classic one is counting islands. A grid of 0s and 1s describes a map, where 1 is land and 0 is water. An island is a group of land cells that touch on their sides, and you want to count the separate groups.

The idea is to scan the grid. When you find a land cell that you have not counted yet, you have found a new island. Then you explore everything connected to it, and mark each cell as seen, so no island is counted twice. The exploring uses a breadth-first search (BFS). BFS visits cells in rings: first the start, then its neighbours, then the neighbours of those, and so on. It uses a queue, which is a line where you add to the back and take from the front. The first cell added is the first one explored. Python's collections.deque is the queue to use, because popleft takes from the front in constant time. A plain list's pop(0) is slow on long queues, because it shifts every other item.

Each cell has up to four neighbours: up, down, left and right. You can store the moves in two small lists, dr for the row change and dc for the column change. A neighbour is valid only when it is inside the grid, and it is land, and it is not seen yet. Checking those three things before reading the grid is the key safety rule.

Save the program as main.py. Type 4 5, then 1 1 0 0 0, then 1 1 0 0 1, then 0 0 1 0 1, then 1 0 0 0 1, one line each.

from collections import deque
 
rows, cols = map(int, input().split())
grid = [[int(x) for x in input().split()] for _ in range(rows)]
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
 
seen = [[False] * cols for _ in range(rows)]
islands = 0
for r in range(rows):
    for c in range(cols):
        if grid[r][c] == 1 and not seen[r][c]:
            islands += 1
            queue = deque([(r, c)])
            seen[r][c] = True
            while queue:
                cr, cc = queue.popleft()
                for d in range(4):
                    nr = cr + dr[d]
                    nc = cc + dc[d]
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1 and not seen[nr][nc]:
                        seen[nr][nc] = True
                        queue.append((nr, nc))
print(f"Islands: {islands}")

Output:

Islands: 4

Trace the first island. The scan finds land at row 0, column 0 and counts island 1. The queue holds that cell. Taking it out, the four neighbours are checked. Up and left are outside the grid, so they are skipped. Down is row 1, column 0, which is land, so it is seen and queued. Right is row 0, column 1, which is land, so it is seen and queued. Next, row 1, column 0 is taken out, and its neighbours include row 1, column 1, which is land and joins the queue. Eventually the queue empties, and the whole first island is marked. The scan then continues across the grid. It reaches row 1, column 4, which is land and not seen, so the second island starts. Cells at row 2, column 2 and row 3, column 0 each start a further island, and the total is 4.

The check 0 <= nr < rows and 0 <= nc < cols must come first. Python chains comparisons, so 0 <= nr < rows means "nr is at least 0 and less than rows". If you read grid[nr][nc] before checking the bounds, a cell on the edge reads index -1 or index cols. Index cols raises IndexError, and index -1 does not raise anything in Python, which makes it worse. The debugging walkthrough shows that case.

A one-row grid also gives correct answers, since the only neighbours of a cell are the cells to its left and right. Type 1 5, then 1 0 1 1 0. The output is Islands: 2, because the runs of land are one cell at column 0 and two cells at columns 2 and 3.

The cost is O(rows times cols) time, because each cell is queued at most once, and O(rows times cols) memory for the seen table and the queue in the worst case.

A word on why the seen table matters so much. Without it, a cell can enter the queue once from each neighbour that touches it, and in an open grid each cell has up to four neighbours. The queue then holds far more entries than there are cells, and in a grid with loops the search may never finish. Marking a cell when you queue it, not when you take it off the queue, guarantees that each cell is queued exactly once. That one line is the difference between a program that finishes and one that runs out of memory.

Directions and neighbours

A neighbour is a cell that touches the current cell. Most grid problems use the four neighbours that share a side: up, down, left and right. Some problems also count the four diagonal cells, which gives eight neighbours. Read the statement to be sure. The island problem uses sides only, so two land cells that touch only at a corner are separate islands.

Moving up, down, left or right changes one index by 1 and leaves the other index alone. Moving up subtracts 1 from the row. Moving left subtracts 1 from the column. Writing the four moves as two small lists, one for the row change and one for the column change, lets one loop handle all four directions with the same code. Take the cell at row 1, column 1 of a 3 by 3 grid. Its four neighbours are row 0, column 1 (up), row 2, column 1 (down), row 1, column 0 (left) and row 1, column 2 (right). The loop never has to know which direction it is working on. It adds dr[d] and dc[d] for each d, and the four pairs (-1, 0), (1, 0), (0, -1) and (0, 1) produce the four neighbours.

For diagonal moves, you would add the four pairs (-1, -1), (-1, 1), (1, -1) and (1, 1) to the lists. The bounds check and the seen check stay exactly the same. That is why writing the moves as data is worth the small extra step: the rest of the program does not change.

BFS or DFS on a grid

Both breadth-first search (BFS) and depth-first search (DFS) visit every cell reachable from a start, so both count islands correctly. They differ in the order they visit cells, and that difference matters for other questions.

BFS uses a queue and visits cells in rings of growing distance from the start. The first time BFS reaches a cell, it has used the fewest steps. That makes BFS the right tool for shortest-path questions on an unweighted grid, where every move costs the same. Suppose you want the fewest moves from the top-left corner to the bottom-right corner through open cells. Run BFS with a dist table that starts at -1 for every cell. When you reach a neighbour that is open and has dist equal to -1, give it the current cell's distance plus one and queue it. When the bottom-right cell gets a distance, that number is the answer. The work is O(rows times cols) time and memory.

DFS goes as deep as it can along one path before it backs up. It is often written with recursion, where each call is one step deeper. Python limits the depth of recursion. The default limit is 1000 calls, and past it Python raises RecursionError. The following program shows the limit being reached.

Output:

1000
RecursionError: maximum recursion depth exceeded

A recursive DFS on a grid a few hundred cells on a side can go deeper than 1000 calls, so it raises RecursionError in Python. An explicit stack, which is a list used with append and pop, avoids that limit, and it works the same way as the queue in the island program. The only change is pop() in place of popleft(). DFS finds a path, but not the shortest one, so it is the wrong tool for distance questions.

The practical rule is this. Use BFS when distance matters. Use DFS with an explicit stack when you only need to visit or count regions and the grid is large. Both use the same seen table, and both need the bounds check before every read.

Common mistakes

1. Swapping rows and columns. A 2 by 3 grid has 2 rows and 3 columns. Creating the transpose as [[0] * rows for _ in range(cols)] gives the right shape, and [[0] * cols for _ in range(rows)] gives the wrong one. The transpose has cols rows.

2. Copying a grid with =. The line b = a gives the same grid a second name. Changing b[0][0] also changes a[0][0]. A real copy needs a new outer list and a copy of each row, for example b = [row[:] for row in a]. The shorter a.copy() copies only the outer list, so the rows are still shared.

3. Transposing the whole square. Swapping every pair in a square grid swaps each pair twice, so nothing changes. Only swap where the column index is greater than the row index.

4. Repeating a row with *. The expression [[0] * 3] * 2 makes two references to the same inner list. Changing one row changes both, and the program prints the same change twice.

Output:

[[0, 5, 0], [0, 5, 0]]
[[0, 5, 0], [0, 0, 0]]

The fix is the list comprehension [[0] * 3 for _ in range(2)], which builds a new inner list for each row.

5. Forgetting the guard if checks in spiral. Without them, a single leftover row or column is read twice, and the output has duplicates. The fix is the two checks shown in the spiral program.

6. Reading a neighbour before checking its bounds. Index 4 on a grid with 4 rows raises IndexError: list index out of range. Index -1 does not raise an error in Python, because Python counts from the end. The debugging walkthrough shows the silent version. Always check that the row and column are in range first.

7. Forgetting to mark a cell as seen. Without seen, the BFS can queue the same cell many times. In a grid with loops, the queue can grow without end. The fix is to mark each cell at the moment you queue it, not when you take it off the queue.

8. Mixing up the two lengths. len(m) is the number of rows. len(m[0]) is the number of columns. Using the wrong one for a loop bound gives an error that points at the wrong index, which is why it is worth writing both down before you start.

Debugging walkthrough: a neighbour check that reads the wrong cell

Here is a version of the neighbour count with the bounds check in the wrong place. The grid is the one from the islands section, and the cell is row 0, column 0, which has two land neighbours: row 1, column 0 and row 0, column 1.

Output:

3

The answer should be 2, but the program prints 3. The up neighbour of row 0 is row -1, which is outside the grid. Python does not raise an error for it, because a negative index counts from the end. The read grid[-1][0] returns the value from the last row, which is 1, so the program counts a land cell that does not touch this one. Nothing crashes, so the bug is hard to see.

The fix is to put the bounds check first in the same and chain. Python stops reading a chain as soon as one part is false, so 0 <= nr < rows and ... must come before grid[nr][nc] == 1. With the check first, the up neighbour is rejected before any read happens.

Output:

2

This pattern is worth remembering. When a check protects a read, put the check before the read, in the same and chain. A column index of cols raises an error, but a row index of -1 does not, so do not rely on the error to show you the mistake.

Variations and related problems

Diagonals. The main diagonal holds m[i][i], and the other diagonal holds m[i][n - 1 - i]. Both are single loops over i.

Zeroing rows and columns. If a cell is 0, set its whole row and whole column to 0. Record which rows and columns to clear first, then clear them, because clearing while scanning can erase a zero you have not yet seen.

Maximum sum rectangle. Choose a pair of rows, add their values column by column to get one list, then run Kadane from the Kadane lesson on that list. Doing this for every pair of rows gives the answer in O(rows squared times cols) time.

Flood fill. Painting a connected region of one colour is the island search with a different action. Replace the count with a paint operation.

Three-dimensional lists. [[[0] * k for _ in range(j)] for _ in range(i)] is a list of grids. It is the same idea with one more index, and it appears in video frames and in simulations. Learn the two-dimensional version first, because the loops extend directly. For heavy numeric grids, the NumPy library stores a grid as one block with a shape, and its indexing looks like m[i, j].

Interview-style questions

"What is the time complexity of visiting every cell?" O(rows times cols). Each cell is handled a constant number of times.

"How do you rotate a matrix in place?" Transpose the square, then reverse each row. The space is O(1) extra.

"How do you search a row-and-column sorted matrix?" Start at the top-right corner, move left when the value is too big, and move down when it is too small. The time is O(rows plus cols).

"How do you count islands?" Scan the grid. Each time you find an unseen land cell, add one to the count and run BFS or DFS from it, marking every reached cell. The time is O(rows times cols).

"What goes wrong with a neighbour check?" Reading the grid before checking the bounds. An index past the end raises an error, and a negative index silently reads from the other end.

A strong answer names the cost, the order of the checks, and the edge cases: an empty grid, a single row, and a single column.

Real-world uses

Image software stores a picture as a grid of pixel values. Rotating a photo is the matrix rotation from this lesson. Phones often store the turn as a note in the file instead of moving the pixels. A game board, such as a chess board or a grid puzzle, is a two-dimensional list with a simple way to find neighbours. Spreadsheet formulas that sum a column or a row use the same loops as the sums in the worked example. Map software treats a grid of land and water as a graph, and the island count is a basic step toward finding regions, routes and coverage.

Practice

Try each one before you read the answer. Save each program as main.py and run it with python3 main.py.

1. Print the sum of each row of a 3 by 3 matrix, one sum per line. Use the matrix [[1, 2, 3], [4, 5, 6], [7, 8, 9]]. The output is 6, 15 and 24.

Show the answer

Output:

6
15
24

The loop takes each row in turn, and sum(row) adds that row. A loop with indexes gives the same result: for i in range(len(m)), then sum(m[i]). The version with for row in m is safe for a jagged list, because each row brings its own length.

2. Print the main diagonal and the other diagonal of the same 3 by 3 matrix. The main diagonal is 1 5 9 and the other is 3 5 7.

Show the answer

Output:

1 5 9
3 5 7

As i grows, the index n - 1 - i moves one column left.

3. Trace spiral by hand on the 2 by 3 matrix [[1, 2, 3], [4, 5, 6]]. Write the order of the output. The expected output is 1, 2, 3, 6, 5, 4.

Show the answer

The top row gives 1, 2, 3. The right column below the top gives 6. The bottom row from right to left gives 5, 4. The left column has no rows between the top and the bottom, so its loop adds nothing. The output is [1, 2, 3, 6, 5, 4], which matches the spiral program in the spiral section on this input.

4. Given a 2 by 3 grid, write the transpose and print it. Input 2 3, then 1 2 3, then 4 5 6. The output has three rows: 1 4, 2 5 and 3 6. Write it without looking at the transpose section, then compare.

Show the answer

The solution is the transpose program in the transpose section. The key line is t = [list(col) for col in zip(*m)]. The explicit version uses t = [[0] * rows for _ in range(cols)] and the copy t[j][i] = m[i][j]. If you wrote [[0] * cols for _ in range(rows)] for t, the program makes a 2 by 3 grid, and the copy into t[j][i] fails with IndexError on the third value.

5. Count the cells in a grid that are strictly larger than all four neighbours (a peak). Input 3 3, then 1 2 1, 3 4 2, 1 2 1. The answer is 1, the cell with value 4. Handle the edge cells by treating a missing neighbour as smaller than any value.

Show the answer

rows, cols = map(int, input().split())
g = [[int(x) for x in input().split()] for _ in range(rows)]
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
 
peaks = 0
for i in range(rows):
    for j in range(cols):
        is_peak = True
        for d in range(4):
            ni = i + dr[d]
            nj = j + dc[d]
            if 0 <= ni < rows and 0 <= nj < cols and g[ni][nj] >= g[i][j]:
                is_peak = False
        if is_peak:
            peaks += 1
print(peaks)

The bounds check comes before the read, the same rule as the island program. A neighbour that is outside the grid is simply not compared, which means a missing neighbour does not stop a cell from being a peak. The output is 1.

6. Given a 3 by 3 grid of values, rotate it 90 degrees counter-clockwise. Use the grid 1 2 3, 4 5 6, 7 8 9. The result is 3 6 9, 2 5 8, 1 4 7. Hint: transpose, then reverse the order of the rows, not the values in each row.

Show the answer

Output:

3 6 9
2 5 8
1 4 7

m.reverse() reverses the outer list, so the rows change places. Only the references move, which is cheap, and the values in each row keep their order. Transpose followed by a reversal of the row order gives the counter-clockwise turn.

7. Find out whether a value exists in a grid where every row is sorted, and each row's first value is larger than the previous row's last value. Such a grid can be searched as one long sorted list with binary search. Write the program that does so, with the grid [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]] and target 3, which should print True.

Show the answer

Output:

True
False

Treat the grid as a flat list of rows * cols values. The flat index mid maps to row mid // cols and column mid % cols. This is only valid because the rows join into one sorted sequence.

8. Count how many islands a 1 by 5 grid of 1 0 1 1 0 has. The answer is 2 islands. Explain in one sentence why a single row is a special case of the island search.

Show the answer

The islands are the run 1 at column 0, and the run 1 1 at columns 2 and 3, so the count is 2. In a single row, the only neighbours of a cell are the cells to its left and right, so an island is a run of touching land cells. Counting runs is the same as counting islands.

9. Write the flood-fill version of the island program: given the same grid and the start cell row 0, column 0, print how many cells are reached. The grid in the islands section gives 4, because the island that contains the start has four land cells.

Show the answer

Output:

4

The count goes up by one each time a cell is taken from the queue, so the output is the size of the island that contains the start cell.

10. Write a program that reads a grid and prints the largest value in each column. Input 2 3, then 1 9 3, then 4 5 6. The output is [4, 9, 6].

Show the answer

rows, cols = map(int, input().split())
m = [[int(x) for x in input().split()] for _ in range(rows)]
 
print([max(col) for col in zip(*m)])

Output:

[4, 9, 6]

zip(*m) gives the columns, and max takes the largest value in each one. The loop version starts each column with its first row's value and compares the cells below. Both give the same answer, because every cell is read once.

What you now know

• A two-dimensional list is a list of lists. len(m) is the number of rows, and len(m[0]) is the number of columns.
• Build a grid with a list comprehension, [[0] * cols for _ in range(rows)], never with [[0] * cols] * rows.
• Use zip(*m) to get the columns of a grid. A transpose swaps rows and columns, and for a non-square grid it needs a new grid with the flipped shape.
• Rotate a square grid 90 degrees clockwise by transposing and then reversing each row, in O(n squared) time and O(1) extra space.
• Spiral order uses four shrinking borders and two guard checks, and it reads each cell once.
• A row-and-column sorted grid can be searched from the top-right corner in O(rows plus cols) time.
• Counting islands is a scan with a breadth-first search from each new land cell. Check the bounds before reading a neighbour, because a negative index in Python does not raise an error.