Given a grid of 0s (water) and 1s (land), count the islands. Land cells that touch up, down, left or right belong to the same island.

Scan every cell. When you find a land cell that has not been visited, add one to the count and flood out from it with BFS or DFS, marking every connected land cell as visited. Because visited cells are skipped, each island is counted once. Each cell is visited a constant number of times, so time is O(rows × cols). Memory is O(rows × cols) for the visited table and the queue or stack in the worst case. You can save the visited table by changing visited land to water, if you are allowed to change the input.

How do you handle the four neighbours of a cell cleanly, and what mistakes do people make?

Keep a list of row and column offsets, such as (1, 0), (-1, 0), (0, 1) and (0, -1), and loop over it. For each offset compute the neighbour's row and column, and check that both are inside the grid before reading it. Common mistakes are checking bounds after reading (which crashes at the edges), mixing up rows and columns, and forgetting to mark cells visited, which causes endless loops.

Return all the elements of an m by n matrix in spiral order.

Keep four boundaries: top, bottom, left and right. Walk right along the top row and move top down by one. Walk down the right column and move right in by one. If rows remain, walk left along the bottom row and move bottom up. If columns remain, walk up the left column and move left in. Repeat while top is not past bottom and left is not past right. The checks before the last two sides stop a single leftover row or column from being walked twice. Time is O(m × n) because each cell is visited once, and extra memory is O(1) besides the output.

Rotate an n by n matrix 90 degrees clockwise in place, without a second matrix.

Transpose the matrix by swapping each cell [i][j] with [j][i] for j greater than i, then reverse each row. Cell (i, j) ends at (j, n - 1 - i), which is a 90 degree clockwise turn. Time is O(n²) because every cell is touched a constant number of times, and extra memory is O(1) because everything happens in place.

Matrix and 2D Grid Traversal

intermediate · 30 min · Asked often · Last reviewed 29 Oct 2026 · by TheLearningLoop Team

Key takeaways

A grid is a graph. Each cell is a node, and its up, down, left and right neighbours are its edges, so BFS and DFS work on it directly.
A direction array such as down, up, right, left turns the four neighbour checks into one loop. Always check the bounds first.
Flood fill counts connected groups (islands) in O(rows × cols) by marking every cell visited once.
Spiral order needs four moving boundaries. Rotating a square 90° clockwise in place is a transpose followed by reversing each row.

New to this topic? Read the overview first: Data Structures & Algorithms: The Big Picture

When to use grid traversal patterns

Use these patterns when you have:

A 2D array or map and a question about connected regions: "how many islands", "the size of the biggest area", "fill this region".
A need to move around a grid: a path from one cell to another, the shortest path through a maze, rotting oranges spreading each minute.
A layout question about the matrix itself: print it in spiral order, rotate it, transpose it, or set whole rows and columns to zero.
Any picture, board or map: pixels in an image, squares on a chessboard, tiles in a game.

Use something else when:

The cells are not laid out on a regular grid, such as cities joined by roads: use a graph with an adjacency list.
You only need sums over rectangles: use 2D prefix sums.
Each cell's answer depends on the cells before it (the cheapest path with only right and down moves): use dynamic programming.

There is nothing to import. A grid is a list of lists (or a flat array). The traversal is a loop and, for flood fill, a queue or a stack.

How grid traversal works

A grid is a graph. Each cell is a node, and its up, down, left and right neighbours are its edges. That means everything you know about BFS and DFS applies, with the neighbours coming from arithmetic instead of an adjacency list.

Keep a list of direction offsets, loop over it, and check the bounds before reading a neighbour.

directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]   # down, up, right, left

Three patterns cover most matrix questions:

Flood fill (connected regions). Scan every cell. When you find an unvisited cell of the right kind, count a new region and spread out from it with BFS or DFS, marking every connected cell visited. Because visited cells are skipped, each region is counted once.
Boundary walk (spiral order). Keep four boundaries: top, bottom, left and right. Walk one side, move that boundary inwards, then turn.
Layout tricks (rotate, transpose). Rotating a square 90° clockwise is a transpose (swap each cell with its mirror across the main diagonal) followed by reversing each row. No second matrix is needed.

A cell is marked visited when it is added to the queue, not when it is taken out. Otherwise the same cell can be added several times by different neighbours.

Try it

Pick one of the three problems, then press Run and step through. Rows are separated by /.

Matrix and grid traversal

Step 1 of 8 · Press Space to play, arrow keys to step

Rows of 0 and 1 separated by /, for example 110/110/001

Examples:

Map (1 = land, 0 = water)

Scanning row by row

A 1 is land and a 0 is water. Count the islands: groups of land cells that touch up, down, left or right. Scan the grid, and flood out from each new piece of land.

islands:: 0
cells visited:: 0
cells in the grid:: 20

Every technique touches each cell a constant number of times, so the work grows with the number of cells (rows times columns).

Speed

Things to try:

Count islands, "Three islands": the map 11000/11000/00100/00011 has 3 islands. The flood fill visits all 7 land cells once and skips the 13 water cells, out of 20 cells in total. Try "Diagonal touching" (100/010/001): there are 3 islands, because cells that only touch at a corner are not connected.
Spiral order, "3 by 3": 1 2 3/4 5 6/7 8 9 comes out as 1 2 3 6 9 8 7 4 5. Try "3 by 4" to see the boundaries shrink on a rectangle.
Rotate 90° clockwise, "3 by 3": three swaps transpose the matrix and three row reversals finish the turn, 6 operations in total, with no second matrix.

Grid traversal operations

Count islands (flood fill).

Make a visited table (or change visited land to water, if allowed).
For every cell, skip it unless it is unvisited land.
Count one island, mark the cell visited and put it in a queue.
Take a cell from the queue. For each of its four neighbours that is inside the grid, is land and is unvisited, mark it and add it to the queue.
Repeat step 4 until the queue is empty, then continue the scan.

Spiral order.

Set top = 0, bottom = rows - 1, left = 0, right = cols - 1.
Walk the top row left to right, then do top++. Walk the right column top to bottom, then do right--.
If top <= bottom, walk the bottom row right to left, then do bottom--.
If left <= right, walk the left column bottom to top, then do left++. Repeat.

Rotate 90° clockwise, in place. Swap m[i][j] with m[j][i] for every j > i, then reverse every row.

Interview fact. Cell (i, j) of an n × n matrix ends at (j, n - 1 - i) after a clockwise turn. Say that formula and then show that transpose plus reverse produces it.

Grid traversal time complexity

R is the number of rows and C is the number of columns.

Task	Time	Extra memory
Count islands (BFS or DFS)	O(R × C)	O(R × C) worst case for the visited table and queue
Spiral order	O(R × C)	O(1) besides the output
Rotate a square in place	O(n²)	O(1)
Shortest path in a maze (BFS)	O(R × C)	O(R × C)

Every cell is visited a constant number of times, so the work always grows with the number of cells, not with the number of regions or the length of any path.

Grid traversal vs other approaches

R × C is the number of cells.

What you need	BFS or DFS flood fill	Union-find	Dynamic programming	Check every pair of cells
Count connected regions once	O(R × C), simple	O(R × C) with extra code	Not applicable	O((R × C)²)
Regions that change as cells are added	Rerun each time	Near O(1) per update	Not applicable	Far too slow
Shortest path, every move costs 1	BFS: O(R × C)	Not applicable	Possible but unusual	Far too slow
Cheapest path, only right and down moves	Possible	Not applicable	O(R × C), simplest	Far too slow

The bold cells show where each wins. Flood fill is the default for one-off questions about regions and paths. Union-find wins when cells keep getting added.

How to explain grid traversal in an interview

Say first: "a grid is a graph, and each cell has up to four neighbours."
Show the direction array and say you check the bounds first.
Say when you mark cells visited: "when I add them to the queue, so none is added twice".
Choose BFS or DFS and say why: BFS for shortest paths, DFS or BFS for plain connectivity, and an explicit stack if the grid is large enough that recursion could overflow.
State both costs: O(rows × cols) time and O(rows × cols) memory in the worst case, and say how you would reduce it.

Where you meet grids in real systems

Anything laid out in rows and columns, such as a picture, a board or a map, is traversed with these patterns. Three examples are drawn out below, the first with code you can run, then more.

Example 1: Finding separate regions on a map

A mapping or game tool needs to know how many separate pieces of land are on a tile, so it can label each one or compute its size. The map is a grid of land and water cells, and each piece of land is a group of connected cells. Flood fill visits each cell once and counts the groups. Open the example below to see the picture and the code.

Code: count islands, and rotate a matrix in placeTime O(rows × cols)Memory O(rows × cols) for the islands, O(1) for the rotation

Each row is a row of the map: 1 is land and 0 is water. The four land cells at the top left form one island, the single cell in the middle is another, and the two cells at the bottom right are the third, so the answer is 3.

Run on the map above, all five versions report 3 islands. Run on the matrix 1 2 3 / 4 5 6 / 7 8 9, all five rotate it to 7 4 1 / 8 5 2 / 9 6 3. The Rust version takes the matrix as &mut Vec<Vec<i32>>, and the C++ code builds with -std=c++17.

from collections import deque

DIRECTIONS = [(1, 0), (-1, 0), (0, 1), (0, -1)]       # down, up, right, left


def count_islands(grid):
    """Count groups of connected 1s (land) in a grid of 0s and 1s.

    Scan every cell. When an unvisited 1 is found, that is a new island: flood out
    from it with a breadth-first search, marking every connected 1 as visited, so
    the island is never counted twice. Cells touch only up, down, left and right.

    Time:   O(rows * cols). Every cell is visited a constant number of times.
    Memory: O(rows * cols) for the visited table and, in the worst case, the queue.
    """
    rows, cols = len(grid), len(grid[0])
    visited = [[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 visited[r][c]:
                islands += 1                       # a new island starts here
                visited[r][c] = True
                queue = deque([(r, c)])
                while queue:
                    cr, cc = queue.popleft()
                    for dr, dc in DIRECTIONS:
                        nr, nc = cr + dr, cc + dc
                        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1 and not visited[nr][nc]:
                            visited[nr][nc] = True # mark when queued, so no cell is queued twice
                            queue.append((nr, nc))
    return islands


def rotate_clockwise(matrix):
    """Rotate a square matrix 90 degrees clockwise, in place.

    Step 1: transpose (swap matrix[i][j] with matrix[j][i]).
    Step 2: reverse every row.

    Time:   O(n^2). Every cell is moved a constant number of times.
    Memory: O(1). No second matrix is made.
    """
    n = len(matrix)
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    for row in matrix:
        row.reverse()

Example 2: Flood fill in a paint program

The paint bucket tool in an image editor fills a region of the same colour. It starts at the clicked pixel, spreads to each neighbour of the same colour, and stops at a different colour. That is flood fill on a grid of pixels, and the cost depends on the size of the region, not the size of the whole image.

Clicking the top left pixel (a 2) fills every connected 2 with a 9. The 2 in the bottom right corner is not connected to the region, so it stays 2.

Example 3: Rotating a photo

A phone rotates a picture when you turn it. A pixel at row i, column j of a square image moves to row j, column n - 1 - i. Transposing and then reversing each row gives the same result with swaps only, which is why in-place rotation needs no second copy of the picture for a square.

The first column of the original (1, 4, 7) becomes the first row of the result, read backwards: 7, 4, 1. Every other column turns into a row in the same way.

More real-world scenarios

4. Maze and pathfinding games

A game that must find the shortest way across a tile map runs BFS on the grid. Each tile is a node, walls are blocked cells, and BFS finds the path with the fewest steps.

5. Rotting oranges and spreading effects

Problems where something spreads each minute, such as a fire, a virus or rotting fruit, start BFS from all infected cells at once and count rounds, one round per minute.

6. Board games

Chess, Go and Minesweeper engines read neighbouring squares with direction arrays. Minesweeper's "reveal an empty area" is flood fill.

7. Image processing

Blur and edge-detection filters visit each pixel and its neighbours, and connected-component labelling uses flood fill to find separate objects in an image.

8. Spreadsheets

A spreadsheet is a grid of cells. Functions such as "sum this range" and "fill down" move through rows and columns, and detecting a block of related cells is a region problem.

9. Geographic information systems

Land-cover maps are stored as grids of cells. Tools find connected lakes or forests and measure their areas, using the same flood fill.

10. Printing and display layouts

Rendering a table, a calendar or a keyboard layout means walking rows and columns in a set order, and many layout questions in interviews ask for spiral or diagonal order.

Language standard libraries

No language has a built-in grid type with flood fill. You use nested lists or arrays and write the traversal. A queue type is built in.

Language	Structure or class	What it is under the hood	Notes
Java	`int[][]`, `ArrayDeque`	Array of arrays, circular-array queue	Use `ArrayDeque<int[]>` as the BFS queue. Rows of a 2D array can have different lengths.
C++	`std::vector<std::vector<int>>`, `std::queue`	Vector of vectors, queue adapter	Rows are separate allocations. For speed, one flat vector indexed by `r * cols + c` is common.
C#	`int[,]`, `int[][]`, `Queue<T>`	Rectangular array, array of arrays, queue	`int[,]` is a true rectangle. `Queue<(int, int)>` works with tuples.
Rust	`Vec<Vec<i32>>`, `VecDeque`	Vector of vectors, ring buffer	Index with `usize`, so convert signed offsets carefully, as in the example above.
Python	List of lists, `collections.deque`	Nested dynamic arrays, double-ended queue	Do not build a grid with `[[0] * n] * m`, because every row would be the same list. Use a comprehension.
Go	`[][]int`, slices	Slice of slices	`queue = queue[1:]` removes from the front without copying, which is fine for BFS.
JavaScript	Array of arrays	Nested arrays	`shift()` can be slow on very large queues, so use an index pointer for big grids.
Kotlin	`Array<IntArray>`, `ArrayDeque`	Array of primitive arrays, circular-array deque	`kotlin.collections.ArrayDeque` works as the BFS queue.

The pattern: the grid is nested arrays and the queue is a built-in type. The traversal is the part you always write yourself.

The takeaway

Whenever a system must find connected regions, shortest paths or neighbours on a grid, look for flood fill with BFS or DFS and a direction array. When cells are added over time and regions must be updated cheaply, it usually uses union-find instead.

Interview questions

Try answering out loud before you reveal hints. Interviewers care about how you reason, not just the final answer.

1.
Given a grid of 0s (water) and 1s (land), count the islands. Land cells that touch up, down, left or right belong to the same island.
medium
2.
How do you handle the four neighbours of a cell cleanly, and what mistakes do people make?
easy
3.
Return all the elements of an m by n matrix in spiral order.
medium
4.
Rotate an n by n matrix 90 degrees clockwise in place, without a second matrix.
medium

Finished this lesson?

Progress is saved on this device. Create a free account to keep it everywhere.

← Previous

Binary Search Tree

Graphs

Topics:MatrixGrid2d arrayFlood fillNumber of islandsSpiral orderRotate matrixBfsDfs