Matrix Traversal

Problem: A grid of '1' (land) and '0' (water). Land cells touching horizontally or vertically form one island. Count the islands.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: m == grid.length · n == grid[i].length · 1 ≤ m, n ≤ 300 · grid[i][j] is '0' or '1'.

From brute force to the pattern: Repeatedly merging land cells into groups is complex. A flood fill from each new land cell visits every cell once: O(r · c).

Spot it: "grid" + "connected horizontally or vertically" + "number of". That's the textbook outer scan + flood fill. The flood visualizer above runs exactly this algorithm.

Key insight: Every time the scan lands on unvisited land, you've found a brand-new island. Sink the whole island (turn it to water) so the scan never counts it again.

Approach (step by step):

1. Loop over every cell, row by row (the outer scan).
2. Skip water ('0') and land that is already sunk.
3. Unvisited '1' means a brand-new island: count += 1, sink the cell (set it to '0') and push it on a stack.
4. While the stack isn't empty: pop a cell, and for each in-bounds neighbor that is still '1', sink it then push it.
5. When the stack empties, the whole island has been sunk. Carry on with the outer scan.
6. Return count.

from typing import List


class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        number_of_rows = len(grid)
        number_of_cols = len(grid[0])
        island_count = 0
        # Outer scan: look at every cell exactly once, row by row
        for row in range(number_of_rows):
            for col in range(number_of_cols):
                if grid[row][col] == "1":
                    # Land that has not been sunk yet = a brand-new island
                    island_count = island_count + 1
                    # Sink the whole island so the scan never counts it again
                    self.sink_island(grid, row, col)
        return island_count

    def sink_island(self, grid, start_row, start_col):
        # Turn every land cell connected to (start_row, start_col) into water ("0")
        directions = [[-1, 0], [0, 1], [1, 0], [0, -1]]   # up, right, down, left
        number_of_rows = len(grid)
        number_of_cols = len(grid[0])
        grid[start_row][start_col] = "0"          # sink the first cell right away
        stack = []                                # land cells whose neighbours we still have to check
        stack.append([start_row, start_col])
        while len(stack) > 0:
            cell = stack.pop()
            row = cell[0]
            col = cell[1]
            for direction in directions:
                next_row = row + direction[0]
                next_col = col + direction[1]
                # Only look at the neighbour if it is inside the grid
                if next_row >= 0 and next_row < number_of_rows and next_col >= 0 and next_col < number_of_cols:
                    if grid[next_row][next_col] == "1":
                        grid[next_row][next_col] = "0"    # sink BEFORE pushing, so it is pushed only once
                        stack.append([next_row, next_col])

What the code is doing, line by line:

1. numIslands stores the grid size and sets island_count = 0.
2. Two nested for loops visit every cell (the outer scan). Water '0' is ignored.
3. When the scan finds a '1', it must be the first cell we've seen of a new island, because every cell of an island already found has been turned into '0'. So we add 1 and call sink_island.
4. sink_island turns the start cell into '0' and puts it on a stack (a plain list used last-in-first-out).
5. While the stack is not empty, it pops a cell and computes each neighbour's row and column from the directions list.
6. A neighbour is used only if it is inside the grid and still land. It is sunk immediately and pushed, so it can never be pushed a second time.
7. When the stack is empty, the whole island is water and the outer scan carries on. The final count is returned.

Dry run on the example:

Grid (example 2): 11000 / 11000 / 00100 / 00011

Scan reaches	Cell is	What happens	island_count
(0,0)	'1'	new island → sink (0,0), (1,0), (0,1), (1,1)	1
(0,1), (1,0), (1,1)	'0' now	already sunk, skip	1
(2,2)	'1'	new island → sink (2,2), which has no land neighbours	2
(3,3)	'1'	new island → sink (3,3), (3,4)	3
(3,4)	'0' now	skip	3
all other cells	'0'	water, skip	3

Edge cases to test:

• All water → 0.
• All land → 1.
• Diagonal neighbours do not connect islands.

Complexity: O(R·C) time; O(R·C) worst-case stack (a grid of all land).

Problem: Return all elements of an m × n matrix in clockwise spiral order, starting at the top-left.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: m == matrix.length · n == matrix[i].length · 1 ≤ m, n ≤ 10 · -100 ≤ matrix[i][j] ≤ 100

From brute force to the pattern: Simulating with a direction vector and a visited matrix uses O(r · c) extra space. Four shrinking fences visit each cell once with O(1) extra space.

Spot it: "spiral order" is a fixed geometric walk. Connectivity doesn't matter, so no visited set is needed.

Key insight: Keep four fences: top, bottom, left, right. Walk the top row and move top down. Walk the right column and move right left. Then the bottom row and the left column, but only if the fences haven't crossed. Without that check, a single leftover row or column gets added twice.

Approach (step by step):

1. Set four fences: top = 0, bottom = R−1, left = 0, right = C−1.
2. Walk the top row from left to right, then top += 1.
3. Walk the right column from top to bottom, then right −= 1.
4. If top ≤ bottom (a row is left), walk the bottom row right → left, then bottom −= 1.
5. If left ≤ right (a column is left), walk the left column bottom → top, then left += 1.
6. Repeat while top ≤ bottom and left ≤ right.

from typing import List


class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        result = []
        top = 0                          # first row we have NOT walked yet
        bottom = len(matrix) - 1         # last row we have NOT walked yet
        left = 0                         # first column we have NOT walked yet
        right = len(matrix[0]) - 1       # last column we have NOT walked yet
        while top <= bottom and left <= right:
            # 1) walk the top row from left to right, then that row is done
            for col in range(left, right + 1):
                result.append(matrix[top][col])
            top = top + 1
            # 2) walk the right column from top to bottom, then that column is done
            for row in range(top, bottom + 1):
                result.append(matrix[row][right])
            right = right - 1
            # 3) walk the bottom row from right to left - only if a row is still left
            if top <= bottom:
                col = right
                while col >= left:
                    result.append(matrix[bottom][col])
                    col = col - 1
                bottom = bottom - 1
            # 4) walk the left column from bottom to top - only if a column is still left
            if left <= right:
                row = bottom
                while row >= top:
                    result.append(matrix[row][left])
                    row = row - 1
                left = left + 1
        return result

What the code is doing, line by line:

1. Four "fence" variables mark the part of the matrix we haven't walked yet: top, bottom, left, right.
2. The while loop keeps going as long as there's at least one unwalked cell, meaning the fences haven't crossed.
3. Side 1: a forward for loop copies the top row. Then top moves down by one, because that row is finished.
4. Side 2: copies the right column from the new top down to bottom, then moves right one to the left.
5. Side 3: walks the bottom row backwards with a while loop (col = col - 1), but only if top ≤ bottom. Without this check, a single remaining row would be added twice.
6. Side 4: walks the left column upwards, but only if left ≤ right, then moves left right by one.
7. When the fences cross, every cell has been added exactly once, so result is returned.

Dry run on the example:

Matrix [[1,2,3,4],[5,6,7,8],[9,10,11,12]]

Loop	Side walked	Values added	Fences afterwards (top, bottom, left, right)
1	top row 0	1, 2, 3, 4	1, 2, 0, 3
1	right column 3	8, 12	1, 2, 0, 2
1	bottom row 2 (backwards)	11, 10, 9	1, 1, 0, 2
1	left column 0 (upwards)	5	1, 1, 1, 2
2	top row 1	6, 7	2, 1, 1, 2
2	right column 2	(none: top > bottom)	2, 1, 1, 1
2	bottom row	skipped: top > bottom	2, 1, 1, 1
2	left column 1	(none: row loop is empty)	2, 1, 2, 1 → loop stops

Result: [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]

Edge cases to test:

• A single row or a single column (don't walk back over it).
• A 1 × 1 matrix.
• Non-square matrices.

Complexity: O(R·C) time, O(1) extra space (besides the output).

Problem: Rotate an n × n matrix 90° clockwise in place.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: n == matrix.length == matrix[i].length · 1 ≤ n ≤ 20 · -1000 ≤ matrix[i][j] ≤ 1000

From brute force to the pattern: Copying into a new matrix with new[c][n − 1 − r] = old[r][c] uses O(n²) extra space, which the problem forbids. Transpose + reverse rows works in place.

Spot it: "rotate", "in place", square matrix. You need an index identity, not a traversal.

Key insight: A clockwise rotation sends (r, c) → (c, n−1−r). That equals a transpose ((r,c) → (c,r)) followed by a horizontal mirror ((r,c) → (r, n−1−c)). Both are easy to do in place.

Approach (step by step):

1. Transpose: for every r and every c > r, swap m[r][c] with m[c][r]. Each pair is swapped exactly once.
2. Mirror: reverse every row in place.
3. Nothing is returned. The matrix itself now holds the rotated image.

from typing import List


class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        size = len(matrix)
        # Step 1 - transpose: swap the value at (row, col) with the value at (col, row)
        for row in range(size):
            for col in range(row + 1, size):     # start right of the diagonal: each pair is swapped ONCE
                temp = matrix[row][col]          # keep one value safe while we overwrite it
                matrix[row][col] = matrix[col][row]
                matrix[col][row] = temp
        # Step 2 - mirror: reverse each row so the first column becomes the last
        for row in range(size):
            matrix[row].reverse()
        # Nothing is returned: LeetCode checks the matrix itself

What the code is doing, line by line:

1. size is the side length of the square matrix.
2. The transpose uses two loops, but the inner loop starts at row + 1. So we only touch cells to the right of the main diagonal. Each pair (row, col) / (col, row) is swapped exactly once. Starting at 0 would swap every pair twice and undo the work.
3. A swap needs three lines and a temp variable. Without it, the first assignment would overwrite a value we still need.
4. matrix[row].reverse() mirrors each row in place.
5. The method returns nothing, because the problem asks us to change the matrix in place.

Dry run on the example:

Step	Action	Matrix afterwards
start		[[1,2,3],[4,5,6],[7,8,9]]
transpose	swap (0,1) ↔ (1,0): 2 ↔ 4	[[1,4,3],[2,5,6],[7,8,9]]
transpose	swap (0,2) ↔ (2,0): 3 ↔ 7	[[1,4,7],[2,5,6],[3,8,9]]
transpose	swap (1,2) ↔ (2,1): 6 ↔ 8	[[1,4,7],[2,5,8],[3,6,9]]
mirror	reverse every row	[[7,4,1],[8,5,2],[9,6,3]] ✔

Edge cases to test:

• A 1 × 1 matrix.
• Even and odd sizes.
• Swapping both halves of the transpose (undoes it).

Complexity: O(n²) time, O(1) space.

Problem: Cells are 0 empty, 1 fresh orange, 2 rotten orange. Each minute, every rotten orange rots its 4-directional fresh neighbors. Return the minutes until no fresh orange remains, or -1 if that never happens.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: m == grid.length · n == grid[i].length · 1 ≤ m, n ≤ 10 · grid[i][j] is 0, 1, or 2.

From brute force to the pattern: Simulating minute by minute by rescanning the whole grid is O((r · c)²). A multi-source BFS spreads from all rotten oranges together and touches each cell once: O(r · c).

Spot it: "minimum minutes", "spreads to adjacent cells", and several starting points. That's multi-source BFS on a grid.

Key insight: Put every rotten orange in the queue at time 0. Then one BFS layer is exactly one minute. Count fresh oranges up front so you can tell at the end whether any were unreachable.

Approach (step by step):

1. Scan once: push every rotten orange into a queue and count the fresh ones.
2. While the queue isn't empty and fresh oranges remain, process exactly len(q) cells. That's one minute.
3. For each rotten cell, rot every fresh 4-neighbor (set it to 2), decrement fresh, and enqueue it.
4. After the layer, minutes += 1.
5. At the end, return minutes if fresh == 0, otherwise -1.

from collections import deque   # deque = queue with fast popleft(); BFS takes cells out in arrival order
from typing import List


class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        number_of_rows = len(grid)
        number_of_cols = len(grid[0])
        directions = [[-1, 0], [0, 1], [1, 0], [0, -1]]   # up, right, down, left
        queue = deque()
        fresh_count = 0
        # Step 1: put EVERY rotten orange in the queue (they all spread at the same moment)
        #         and count the fresh oranges.
        for row in range(number_of_rows):
            for col in range(number_of_cols):
                if grid[row][col] == 2:
                    queue.append([row, col])
                elif grid[row][col] == 1:
                    fresh_count = fresh_count + 1
        minutes = 0
        # Step 2: each pass of this loop is ONE minute
        while len(queue) > 0 and fresh_count > 0:
            rotten_this_minute = len(queue)       # only the oranges that were rotten at the start of this minute
            for position in range(rotten_this_minute):
                cell = queue.popleft()
                row = cell[0]
                col = cell[1]
                for direction in directions:
                    next_row = row + direction[0]
                    next_col = col + direction[1]
                    if next_row >= 0 and next_row < number_of_rows and next_col >= 0 and next_col < number_of_cols:
                        if grid[next_row][next_col] == 1:
                            grid[next_row][next_col] = 2          # it rots now (this also marks it visited)
                            fresh_count = fresh_count - 1
                            queue.append([next_row, next_col])    # it will spread NEXT minute
            minutes = minutes + 1
        # Step 3: if some fresh orange was never reached, it is impossible
        if fresh_count == 0:
            return minutes
        else:
            return -1

What the code is doing, line by line:

1. Read the grid size and write down the four directions.
2. Step 1 scans the grid once. Every rotten orange (value 2) goes into the queue, and every fresh one (value 1) adds 1 to fresh_count. Starting with all rotten oranges in the queue is what "multi-source BFS" means.
3. Step 2: the while loop runs once per minute. rotten_this_minute = len(queue) freezes how many oranges spread during this minute. Oranges that rot during the minute are added to the back of the queue and only spread next minute.
4. For each of those oranges, look at the 4 neighbours. A fresh neighbour turns into 2, fresh_count goes down by one, and it joins the queue.
5. After the layer, minutes = minutes + 1. The loop stops when there are no fresh oranges left, or nothing more can spread.
6. Step 3: if fresh_count is 0, return the minutes. Otherwise some orange was walled off, so return -1.

Dry run on the example:

Grid [[2,1,1],[1,1,0],[0,1,1]]; at the start the queue is [(0,0)] and fresh_count = 6.

Minute	Oranges spreading	Newly rotten	fresh_count after
1	(0,0)	(0,1), (1,0)	4
2	(0,1), (1,0)	(0,2), (1,1)	2
3	(0,2), (1,1)	(2,1)	1
4	(2,1)	(2,2)	0 → stop

fresh_count is 0, so the answer is 4.

Edge cases to test:

• No fresh oranges at the start → 0.
• A fresh orange that can never be reached → −1.
• No rotten oranges but some fresh ones → −1.

Complexity: O(R·C) time and space.

Problem: From any cell you may step up/down/left/right to a strictly larger value. Return the length of the longest such path.

Solve it on LeetCode ↗

Constraints: m == matrix.length · n == matrix[i].length · 1 ≤ m, n ≤ 200 · 0 ≤ matrix[i][j] ≤ 2³¹ - 1

From brute force to the pattern: DFS from every cell without memory recomputes the same paths over and over (exponential). The "strictly increasing" rule means there are no cycles, so caching each cell's answer makes it O(r · c).

Spot it: grid + 4-directional moves + "longest path". A plain DFS from every cell re-explores the same paths again and again (exponential). But "strictly increasing" means a path can never loop back, so the moves form a DAG. On a DAG, DFS + memoization works.

Key insight: longest_from(row, col) = 1 + max(longest_from(neighbor)) over larger neighbors. Each cell's answer never changes, so compute it once and cache it. This is grid traversal meeting DP.

Approach (step by step):

1. Define longest_from(row, col) = length of the longest increasing path that starts at (row, col).
2. longest_from(row, col) = 1 + max(longest_from(neighbor)) over neighbors with a strictly larger value, or just 1 if there are none.
3. Store each answer in the dictionary self.memo, keyed by (row, col), so each cell is solved only once.
4. No visited set is needed: values strictly increase along a path, so it can never come back to a cell.
5. The answer is the max of longest_from(row, col) over all cells.

from typing import List


class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        # Save these on self so the helper method can use them
        self.matrix = matrix
        self.number_of_rows = len(matrix)
        self.number_of_cols = len(matrix[0])
        self.memo = {}       # memo[(row, col)] = length of the longest increasing path STARTING at (row, col)
        best = 0
        for row in range(self.number_of_rows):
            for col in range(self.number_of_cols):
                length = self.longest_from(row, col)
                if length > best:
                    best = length
        return best

    def longest_from(self, row, col):
        # Already solved this cell? Then just reuse the stored answer.
        if (row, col) in self.memo:
            return self.memo[(row, col)]
        directions = [[-1, 0], [0, 1], [1, 0], [0, -1]]
        best_length = 1                          # a path made of only this cell has length 1
        for direction in directions:
            next_row = row + direction[0]
            next_col = col + direction[1]
            if next_row >= 0 and next_row < self.number_of_rows and next_col >= 0 and next_col < self.number_of_cols:
                # We may only step to a STRICTLY bigger number
                if self.matrix[next_row][next_col] > self.matrix[row][col]:
                    candidate = 1 + self.longest_from(next_row, next_col)
                    if candidate > best_length:
                        best_length = candidate
        self.memo[(row, col)] = best_length      # remember the answer for next time
        return best_length

What the code is doing, line by line:

1. longestIncreasingPath saves the matrix and its size on self so the helper method can read them. It also creates an empty dictionary memo.
2. It asks the helper for the longest path starting at every cell and keeps the biggest answer in best.
3. longest_from(row, col) first checks the memo. If this cell was solved before, it returns the stored number immediately. That's what turns an exponential search into linear time.
4. Otherwise it starts with best_length = 1 (the cell on its own) and tries the 4 neighbours.
5. A neighbour is only used if it's inside the grid and holds a strictly larger value. For each one, the path length is 1 + longest_from(neighbour), which is a recursive call.
6. No "visited" set is needed: numbers strictly increase along a path, so a path can never come back to a cell.
7. The best length is stored in the memo before returning, so this cell is never computed again.

Dry run on the example:

Matrix [[9,9,4],[6,6,8],[2,1,1]]. Final memo (longest path starting at each cell):

	col 0	col 1	col 2
row 0	1 (9)	1 (9)	2 (4 → 9 or 4 → 8)
row 1	2 (6 → 9)	2 (6 → 9)	1 (8)
row 2	3 (2 → 6 → 9)	4 (1 → 2 → 6 → 9)	2 (1 → 8)

For example, longest_from(2,1) (value 1) tries its bigger neighbours: up (6) gives 1 + 2 = 3 and left (2) gives 1 + 3 = 4. The best is 4.

Edge cases to test:

• All values equal → 1.
• A single cell → 1.
• A long snake-shaped increasing path.

Complexity: O(R·C) time (each cell is solved once, with 4 neighbor checks), O(R·C) space for the cache and recursion.

Problem: An image is a grid of color numbers. Starting from pixel (sr, sc), repaint it and every pixel connected to it 4-directionally with the same original color to color. Return the image.

Solve it on LeetCode ↗

Constraints: m == image.length · n == image[i].length · 1 ≤ m, n ≤ 50 · 0 ≤ image[i][j], color < 2¹⁶ · 0 ≤ sr < m · 0 ≤ sc < n

From brute force to the pattern: This is already a single flood fill: DFS or BFS from the start touches each pixel of the region once: O(r · c).

Spot it: "connected 4-directionally" + "same color" + repaint is the paint-bucket tool, which is the plain flood-fill template.

Approach (step by step):

1. Remember old = image[sr][sc]. If old == color, return immediately. Otherwise painted cells would still look "unvisited" and you'd loop forever.
2. Paint the start pixel and push it on a stack.
3. Pop a pixel. For each in-bounds neighbor that still has color old, paint it and push it.
4. When the stack is empty, return the image.

from typing import List


class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        # sr, sc = starting row and starting column (names given by LeetCode)
        number_of_rows = len(image)
        number_of_cols = len(image[0])
        old_color = image[sr][sc]
        if old_color == color:
            return image                     # nothing would change; also avoids looping forever
        directions = [[-1, 0], [0, 1], [1, 0], [0, -1]]
        image[sr][sc] = color                # painting a pixel also marks it as visited
        stack = []
        stack.append([sr, sc])
        while len(stack) > 0:
            cell = stack.pop()
            row = cell[0]
            col = cell[1]
            for direction in directions:
                next_row = row + direction[0]
                next_col = col + direction[1]
                if next_row >= 0 and next_row < number_of_rows and next_col >= 0 and next_col < number_of_cols:
                    if image[next_row][next_col] == old_color:
                        image[next_row][next_col] = color     # paint BEFORE pushing: never pushed twice
                        stack.append([next_row, next_col])
        return image

What the code is doing, line by line:

1. Remember the colour of the starting pixel in old_color. This is the colour we're allowed to spread through.
2. If it already equals the new colour, return straight away. Otherwise painted pixels would still look like old_color and we'd push them forever.
3. Paint the start pixel and push it onto the stack.
4. Pop a pixel and work out its 4 neighbours. Each neighbour that is inside the image and still has old_color is painted and pushed.
5. When the stack is empty, the whole connected region is painted, so return the image.

Dry run on the example:

image [[1,1,1],[1,1,0],[1,0,1]], start (1,1), color 2. old_color = 1.

Pop	Neighbours painted and pushed	Stack afterwards
(1,1)	(0,1), (1,0)	[(0,1), (1,0)]
(1,0)	(0,0), (2,0)	[(0,1), (0,0), (2,0)]
(2,0)	none (right is 0)	[(0,1), (0,0)]
(0,0)	none (already painted)	[(0,1)]
(0,1)	(0,2)	[(0,2)]
(0,2)	none	[] → done

Result [[2,2,2],[2,2,0],[2,0,1]]. The bottom-right 1 isn't connected, so it stays 1.

Edge cases to test:

• The new colour equals the old colour.
• A region that touches the border.
• A 1 × 1 image.

Complexity: O(R·C) time, O(R·C) worst-case stack.

Problem: Whenever a cell is 0, set its whole row and whole column to 0, in place. Follow-up: use only O(1) extra memory.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: m == matrix.length · n == matrix[0].length · 1 ≤ m, n ≤ 200 · -2³¹ ≤ matrix[i][j] ≤ 2³¹ - 1

From brute force to the pattern: Copying the matrix uses O(r · c) space; storing the rows and columns to clear uses O(r + c). Using the first row and column as marker storage gets it to O(1) extra space.

Spot it: A matrix plus row/column operations is an index walk, not connectivity. The catch: if you zero cells while scanning, the new zeros spread wrongly. You must record first and write later. To use O(1) memory, store the records inside the matrix itself (row 0 and column 0).

Approach (step by step):

1. Remember separately whether row 0 and column 0 originally contain a zero (they're about to be reused as marker storage).
2. Scan cells with r ≥ 1, c ≥ 1. For each zero, mark its row (matrix[r][0] = 0) and its column (matrix[0][c] = 0).
3. Scan r ≥ 1, c ≥ 1 again and zero any cell whose row marker or column marker is 0.
4. Finally zero row 0 and/or column 0 if the flags from step 1 say so. This must come last, because they held the markers.

from typing import List


class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        number_of_rows = len(matrix)
        number_of_cols = len(matrix[0])
        # Row 0 and column 0 are about to be used as "marker" storage,
        # so first remember whether they contain a zero of their own.
        first_row_has_zero = False
        for col in range(number_of_cols):
            if matrix[0][col] == 0:
                first_row_has_zero = True
        first_col_has_zero = False
        for row in range(number_of_rows):
            if matrix[row][0] == 0:
                first_col_has_zero = True
        # Pass 1: for every zero in the rest of the matrix, write a marker
        for row in range(1, number_of_rows):
            for col in range(1, number_of_cols):
                if matrix[row][col] == 0:
                    matrix[row][0] = 0       # marker: "row `row` must become all zeros"
                    matrix[0][col] = 0       # marker: "column `col` must become all zeros"
        # Pass 2: zero every cell whose row marker or column marker is set
        for row in range(1, number_of_rows):
            for col in range(1, number_of_cols):
                if matrix[row][0] == 0 or matrix[0][col] == 0:
                    matrix[row][col] = 0
        # Finally handle row 0 and column 0 themselves (they held the markers until now)
        if first_row_has_zero:
            for col in range(number_of_cols):
                matrix[0][col] = 0
        if first_col_has_zero:
            for row in range(number_of_rows):
                matrix[row][0] = 0

What the code is doing, line by line:

1. Two small loops check whether row 0 and column 0 already contain a zero, and save the answers in two True/False flags. We need these because we're about to overwrite row 0 and column 0 with markers.
2. Pass 1 looks at every cell except row 0 and column 0. When it finds a zero, it writes a 0 at the start of that row (matrix[row][0]) and at the top of that column (matrix[0][col]). Those cells act as notes saying "zero this row / column later".
3. Pass 2 visits the same cells again and sets a cell to 0 if its row note or its column note is 0. We don't zero anything during pass 1, because new zeros would be mistaken for original ones and spread too far.
4. Last, if the flags say so, row 0 and/or column 0 are zeroed completely. This has to happen at the very end, because those cells held the notes.
5. Only two extra variables are used, so the extra memory is O(1).

Dry run on the example:

matrix [[1,1,1],[1,0,1],[1,1,1]]

Step	What happens	Matrix afterwards
flags	row 0 has no zero, column 0 has no zero	unchanged
pass 1	(1,1) is 0 → set marker cells (1,0) and (0,1) to 0	[[1,0,1],[0,0,1],[1,1,1]]
pass 2	(1,2): row marker 0 → 0. (2,1): column marker 0 → 0. (2,2): no marker	[[1,0,1],[0,0,0],[1,0,1]]
flags	both False, nothing more to do	[[1,0,1],[0,0,0],[1,0,1]] ✔

Edge cases to test:

• A zero in the first row or first column.
• The whole matrix is zeros.
• A single row or column.

Complexity: O(R·C) time, O(1) extra space.

Problem: In a 0/1 grid, an island is a group of 4-directionally connected 1s. Return the size of the largest island, or 0 if there is none.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: m == grid.length · n == grid[i].length · 1 ≤ m, n ≤ 50 · grid[i][j] is either 0 or 1.

From brute force to the pattern: This is a single pass of flood fills: O(r · c).

Spot it: Same as Number of Islands (200), except the flood returns a size and we keep the maximum instead of a count.

Approach (step by step):

1. Outer scan over every cell.
2. On an unvisited 1, start a flood: sink it, push it, set area = 0.
3. Each time you pop a cell, area += 1, then sink and push its land neighbors.
4. When the flood ends, best = max(best, area).
5. Return best.

from typing import List


class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        best = 0
        for row in range(len(grid)):
            for col in range(len(grid[0])):
                if grid[row][col] == 1:
                    area = self.sink_and_measure(grid, row, col)   # size of this new island
                    if area > best:
                        best = area
        return best

    def sink_and_measure(self, grid, start_row, start_col):
        # Sink (set to 0) every land cell connected to the start, counting them as we go
        directions = [[-1, 0], [0, 1], [1, 0], [0, -1]]
        number_of_rows = len(grid)
        number_of_cols = len(grid[0])
        grid[start_row][start_col] = 0
        stack = []
        stack.append([start_row, start_col])
        area = 0
        while len(stack) > 0:
            cell = stack.pop()
            area = area + 1                      # count each cell once, when it is popped
            row = cell[0]
            col = cell[1]
            for direction in directions:
                next_row = row + direction[0]
                next_col = col + direction[1]
                if next_row >= 0 and next_row < number_of_rows and next_col >= 0 and next_col < number_of_cols:
                    if grid[next_row][next_col] == 1:
                        grid[next_row][next_col] = 0      # sink before pushing
                        stack.append([next_row, next_col])
        return area

What the code is doing, line by line:

1. The outer scan is the same as in Number of Islands: visit every cell, and treat each remaining 1 as a new island.
2. Instead of counting islands, we ask the helper for the island's size and keep the largest in best.
3. sink_and_measure is a normal flood fill. Every cell popped from the stack adds 1 to area. Cells are sunk when pushed, so each one is popped (and counted) exactly once.
4. When the stack is empty, area is the number of cells in the island and is returned.

Dry run on the example:

Small example [[1,1,0,0],[0,1,0,1],[0,0,0,1]]

Scan reaches	Island cells sunk	area	best
(0,0)	(0,0), (0,1), (1,1)	3	3
(1,3)	(1,3), (2,3)	2	3
everything else	0 or already sunk	-	3

Edge cases to test:

• No land → 0.
• One large island.
• Many single-cell islands.

Complexity: O(R·C) time and space.

Problem: A board holds 'X' and 'O'. Flip every region of 'O's that is completely surrounded by 'X' into 'X'. A region that touches the border can't be surrounded, so it stays.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: m == board.length · n == board[i].length · 1 ≤ m, n ≤ 200 · board[i][j] is 'X' or 'O'.

From brute force to the pattern: Flood-filling from each 'O' region and checking whether it touches the border is O((r · c)²) in the worst case. Starting from the border marks every survivor in one pass: O(r · c).

Spot it: Regions on a grid call for a flood. The trick is reverse thinking: instead of testing each region for "is it surrounded?", flood from the border to find the regions that are safe. Everything else gets captured.

Approach (step by step):

1. For every 'O' on the border, flood its region and mark it 'S' (safe).
2. Scan the whole board once more: 'S' → 'O' (restore the safe cells) and everything else → 'X'. Any 'O' left at this point was surrounded.

from typing import List


class Solution:
    def solve(self, board: List[List[str]]) -> None:
        number_of_rows = len(board)
        number_of_cols = len(board[0])
        # Step 1: every 'O' on the border can't be surrounded -> mark its whole region as safe ('S')
        for row in range(number_of_rows):
            for col in range(number_of_cols):
                on_border = row == 0 or row == number_of_rows - 1 or col == 0 or col == number_of_cols - 1
                if on_border and board[row][col] == "O":
                    self.mark_safe(board, row, col)
        # Step 2: anything still 'O' was surrounded -> capture it; 'S' cells go back to 'O'
        for row in range(number_of_rows):
            for col in range(number_of_cols):
                if board[row][col] == "S":
                    board[row][col] = "O"
                else:
                    board[row][col] = "X"

    def mark_safe(self, board, start_row, start_col):
        # Flood fill that turns a border-connected region of 'O' into 'S'
        directions = [[-1, 0], [0, 1], [1, 0], [0, -1]]
        number_of_rows = len(board)
        number_of_cols = len(board[0])
        board[start_row][start_col] = "S"
        stack = []
        stack.append([start_row, start_col])
        while len(stack) > 0:
            cell = stack.pop()
            row = cell[0]
            col = cell[1]
            for direction in directions:
                next_row = row + direction[0]
                next_col = col + direction[1]
                if next_row >= 0 and next_row < number_of_rows and next_col >= 0 and next_col < number_of_cols:
                    if board[next_row][next_col] == "O":
                        board[next_row][next_col] = "S"
                        stack.append([next_row, next_col])

What the code is doing, line by line:

1. The idea is reverse thinking. Instead of asking "is this region surrounded?" for every region, find the regions that are definitely not surrounded: the ones touching the border.
2. Step 1 loops over all cells. on_border is True for cells in the first or last row or column. Every border 'O' starts a flood fill (mark_safe) that turns its whole region into 'S' (safe).
3. mark_safe is the usual stack flood fill, spreading only through 'O' cells.
4. Step 2 rewrites every cell: 'S' goes back to 'O', and everything else becomes 'X'. An 'O' still left at this point wasn't connected to the border, so it gets captured.

Dry run on the example:

board XXXX / XOOX / XXOX / XOXX

Step	What happens	Board afterwards
1	The only border 'O' is (3,1). Its region is just itself → 'S'	XXXX / XOOX / XXOX / XSXX
2	(1,1), (1,2), (2,2) are still 'O' → 'X'. (3,1) 'S' → 'O'	XXXX / XXXX / XXXX / XOXX ✔

Edge cases to test:

• Everything is 'O' → nothing changes.
• A single row or column.
• An 'O' region that touches the border only at a corner.

Complexity: O(R·C) time and space.

Problem: heights is an island map. Rain flows from a cell to a 4-neighbor whose height is ≤ the current cell's. The Pacific touches the top and left edges, the Atlantic the bottom and right edges. Return every cell from which water can reach both oceans.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: m == heights.length · n == heights[r].length · 1 ≤ m, n ≤ 200 · 0 ≤ heights[r][c] ≤ 10⁵

From brute force to the pattern: A DFS from every cell to check whether water reaches each ocean is O((r · c)²). Two reverse flood fills, one per ocean, solve it in O(r · c).

Spot it: Asking "can every cell reach the border?" separately would be slow. Reverse the flow instead: start at each ocean's border cells (multi-source) and flood uphill, to neighbors that are ≥ the current cell. Then intersect the two reach sets.

Approach (step by step):

1. Pacific sources = top row + left column. Atlantic sources = bottom row + right column.
2. From each set of sources, run a DFS that moves to neighbors with height ≥ current. Water could flow from there down to here.
3. The answer is every cell in both reach sets.

from typing import List


class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        number_of_rows = len(heights)
        number_of_cols = len(heights[0])
        # Pacific touches the top row and the left column
        pacific_starts = []
        for col in range(number_of_cols):
            pacific_starts.append([0, col])
        for row in range(number_of_rows):
            pacific_starts.append([row, 0])
        # Atlantic touches the bottom row and the right column
        atlantic_starts = []
        for col in range(number_of_cols):
            atlantic_starts.append([number_of_rows - 1, col])
        for row in range(number_of_rows):
            atlantic_starts.append([row, number_of_cols - 1])
        reaches_pacific = self.climb_from(heights, pacific_starts)
        reaches_atlantic = self.climb_from(heights, atlantic_starts)
        # A cell is an answer when water from it reaches BOTH oceans
        result = []
        for row in range(number_of_rows):
            for col in range(number_of_cols):
                if (row, col) in reaches_pacific and (row, col) in reaches_atlantic:
                    result.append([row, col])
        return result

    def climb_from(self, heights, starts):
        # Walk UPHILL (to neighbours at least as high) from all start cells.
        # Every cell we reach can drain DOWN to these starts, i.e. to this ocean.
        directions = [[-1, 0], [0, 1], [1, 0], [0, -1]]
        number_of_rows = len(heights)
        number_of_cols = len(heights[0])
        seen = set()                     # cells reached so far, stored as (row, col)
        stack = []
        for start in starts:
            if (start[0], start[1]) not in seen:
                seen.add((start[0], start[1]))
                stack.append(start)
        while len(stack) > 0:
            cell = stack.pop()
            row = cell[0]
            col = cell[1]
            for direction in directions:
                next_row = row + direction[0]
                next_col = col + direction[1]
                if next_row >= 0 and next_row < number_of_rows and next_col >= 0 and next_col < number_of_cols:
                    if (next_row, next_col) not in seen:
                        if heights[next_row][next_col] >= heights[row][col]:   # uphill or flat
                            seen.add((next_row, next_col))
                            stack.append([next_row, next_col])
        return seen

What the code is doing, line by line:

1. Build two lists of starting cells: Pacific border cells (top row + left column) and Atlantic border cells (bottom row + right column).
2. climb_from runs one flood fill from all starts of an ocean at once (multi-source). It moves to a neighbour only if the neighbour is at least as high. Water could flow from that neighbour down to the cell we came from, so the neighbour can drain into this ocean.
3. seen is a set of (row, col) tuples. It's both the visited mark and the answer: every cell whose water reaches this ocean.
4. We get one set for the Pacific and one for the Atlantic, then scan every cell and keep those that are in both sets.
5. Climbing up from the oceans visits each cell at most twice. Testing every cell separately would cost far more.

Dry run on the example:

Small example heights [[1,2],[4,3]]

Ocean	Start cells	Climb uphill to	Reach set
Pacific	(0,0)=1, (0,1)=2, (1,0)=4	from (0,1)=2 up to (1,1)=3	{(0,0), (0,1), (1,0), (1,1)}
Atlantic	(1,0)=4, (1,1)=3, (0,1)=2	nothing: (0,0)=1 is lower than every neighbour	{(0,1), (1,0), (1,1)}

Both oceans: [[0,1],[1,0],[1,1]]. Cell (0,0) has height 1 and both its neighbours are higher, so its water can only reach the Pacific.

Edge cases to test:

• A 1 × 1 grid.
• Flat regions (equal heights let water flow both ways).
• A single row or column.

Complexity: O(R·C) time and space (each cell is visited at most once per ocean).

Problem: In an n × n grid of 0 (open) and 1 (blocked), find the length of the shortest path from the top-left to the bottom-right through open cells, moving in any of 8 directions. The length counts cells, including both ends. Return -1 if there's no path.

Solve it on LeetCode ↗

Constraints: n == grid.length · n == grid[i].length · 1 ≤ n ≤ 100 · grid[i][j] is 0 or 1

From brute force to the pattern: DFS tries many paths and doesn't naturally give the shortest. BFS reaches each cell first along a shortest path: O(n²).

Spot it: "shortest" + unweighted grid moves means BFS. "8-directionally connected" means use the 8-direction list.

Approach (step by step):

1. If the start or the goal is blocked, return -1.
2. BFS from (0, 0) with distance 1 (the start cell counts). Mark it visited.
3. Pop a cell. If it's the goal, return its distance.
4. Push every open, unvisited 8-neighbor with distance + 1, marking it on push.
5. If the queue empties first, return -1.

from collections import deque   # deque = queue with fast popleft()
from typing import List


class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        size = len(grid)
        if grid[0][0] == 1 or grid[size - 1][size - 1] == 1:
            return -1                               # start or goal is blocked
        # All 8 directions: 4 straight + 4 diagonal
        directions = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]
        grid[0][0] = 1                              # reuse the grid: 1 now also means "visited"
        queue = deque()
        queue.append([0, 0, 1])                     # [row, col, number of cells on the path so far]
        while len(queue) > 0:
            item = queue.popleft()
            row = item[0]
            col = item[1]
            distance = item[2]
            if row == size - 1 and col == size - 1:
                return distance                     # BFS reaches the goal first by a shortest path
            for direction in directions:
                next_row = row + direction[0]
                next_col = col + direction[1]
                if next_row >= 0 and next_row < size and next_col >= 0 and next_col < size:
                    if grid[next_row][next_col] == 0:
                        grid[next_row][next_col] = 1          # mark when adding to the queue
                        queue.append([next_row, next_col, distance + 1])
        return -1                                   # queue empty: no path exists

What the code is doing, line by line:

1. If the start or the goal is blocked, no path is possible, so return -1.
2. directions lists all 8 moves, because the problem allows diagonal steps.
3. The grid itself is the visited marker: we write 1 into a cell when we add it to the queue, so it's never added twice.
4. Each queue item stores [row, col, distance], where distance counts the cells on the path including the start, so the start has distance 1.
5. BFS pops the oldest item. If it's the goal, its distance is the shortest possible, because BFS explores paths in order of length.
6. Every open neighbour is marked and added with distance + 1. If the queue empties, return -1.

Dry run on the example:

grid [[0,0,0],[1,1,0],[1,1,0]]

Pop [row, col, distance]	Open neighbours added
[0, 0, 1]	[0, 1, 2]
[0, 1, 2]	[0, 2, 3], [1, 2, 3] (diagonal)
[0, 2, 3]	none new
[1, 2, 3]	[2, 2, 4]
[2, 2, 4]	goal reached → return 4

Edge cases to test:

• The start or end cell is 1 → −1.
• A 1 × 1 grid with a 0 → 1.
• Diagonal shortcuts.

Complexity: O(n²) time and space.

Problem: Grid of 0 (empty) and 1 (obstacle). You move 4-directionally and may knock down at most k obstacles. Return the minimum number of steps from the top-left to the bottom-right, or -1.

Solve it on LeetCode ↗

Constraints: m == grid.length · n == grid[i].length · 1 ≤ m, n ≤ 40 · 1 ≤ k ≤ m * n · grid[i][j] is either 0 or 1. · grid[0][0] == grid[m - 1][n - 1] == 0

From brute force to the pattern: Plain BFS ignores removals; DFS over every choice is exponential. BFS over (cell, removals left) states finds the shortest path in O(r · c · k).

Spot it: "minimum steps" on a grid means BFS. But the position alone isn't enough to describe where you are: arriving at the same cell with more knock-downs left is genuinely better. So the BFS state is (r, c, removals_left).

Approach (step by step):

1. Shortcut: if k ≥ R + C − 2, you can bulldoze a straight Manhattan path, so return R + C − 2.
2. Keep best_left[row][col] = the most removals left with which any BFS state has reached (row, col).
3. BFS layer by layer from (0, 0, k). Each layer is one step.
4. Moving into a cell costs grid[nr][nc] removals. Enqueue the new state only if nrem > best[nr][nc]. A state with fewer steps and at least as many removals already dominates it.
5. Return the step count when the goal is popped, or -1 if the queue empties.

from collections import deque   # deque = queue with fast popleft()
from typing import List


class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        # k = how many obstacles we are allowed to remove (name given by LeetCode)
        number_of_rows = len(grid)
        number_of_cols = len(grid[0])
        straight_line_steps = number_of_rows + number_of_cols - 2
        if k >= straight_line_steps:
            return straight_line_steps              # enough removals to walk straight to the goal
        # best_left[row][col] = the most removals still available when any state reached this cell
        best_left = []
        for row in range(number_of_rows):
            best_left.append([-1] * number_of_cols) # -1 = never reached yet
        best_left[0][0] = k
        directions = [[-1, 0], [0, 1], [1, 0], [0, -1]]
        queue = deque()
        queue.append([0, 0, k])                     # a BFS state = [row, col, removals left]
        steps = 0
        while len(queue) > 0:
            layer_size = len(queue)                 # all states in this layer are `steps` moves away
            for position in range(layer_size):
                state = queue.popleft()
                row = state[0]
                col = state[1]
                removals_left = state[2]
                if row == number_of_rows - 1 and col == number_of_cols - 1:
                    return steps
                for direction in directions:
                    next_row = row + direction[0]
                    next_col = col + direction[1]
                    if next_row >= 0 and next_row < number_of_rows and next_col >= 0 and next_col < number_of_cols:
                        # Walking into an obstacle (value 1) uses up one removal
                        new_left = removals_left - grid[next_row][next_col]
                        # Only worth it if we arrive with MORE removals than any earlier visit
                        # (this also rejects new_left == -1, i.e. no removal available)
                        if new_left > best_left[next_row][next_col]:
                            best_left[next_row][next_col] = new_left
                            queue.append([next_row, next_col, new_left])
            steps = steps + 1
        return -1

What the code is doing, line by line:

1. Shortcut: a path straight to the goal takes rows + cols − 2 steps. If we may remove at least that many obstacles, that path always works.
2. best_left is a table built row by row with append. It stores, for each cell, the most removals left that any visit has had. It starts at -1, meaning "never reached".
3. The BFS state is [row, col, removals_left]. Position alone isn't enough: reaching a cell with more removals left is genuinely better.
4. The queue is processed one layer at a time, and each layer is one more step. When the goal is popped, steps is the answer.
5. Moving into a cell subtracts its value (0 or 1) from the removals left. The new state is added only if it beats best_left for that cell. An earlier visit with at least as many removals and fewer steps is always at least as good. The same check also blocks moves when no removal is left (new_left would be -1).

Dry run on the example:

grid rows 000 / 110 / 000 / 011 / 000, k = 1. States are written (row, col, removals left).

steps	States popped in this layer
0	(0,0,1)
1	(1,0,0) (broke an obstacle), (0,1,1)
2	(2,0,0), (1,1,0), (0,2,1)
3	(3,0,0), (2,1,0), (1,2,0), (1,2,1)
4	(4,0,0), (2,2,0), (2,2,1)
5	(4,1,0), (3,2,0) (broke the obstacle at (3,2))
6	(4,2,0) = goal → return 6

Edge cases to test:

• k ≥ r + c − 3 → the Manhattan distance (you can go straight through).
• A 1 × 1 grid → 0.
• Unreachable even with removals → −1.

Complexity: O(R·C·k) time and space, since each cell can be entered with up to k+1 different removal counts.

Problem: An n × n grid holds distinct elevations. At time t the water level is t, and you can swim freely between 4-adjacent cells whose elevations are both ≤ t. What is the least time at which you can get from the top-left to the bottom-right?

Solve it on LeetCode ↗

Constraints: n == grid.length · n == grid[i].length · 1 ≤ n ≤ 50 · 0 ≤ grid[i][j] < n² · Each value grid[i][j] is unique.

From brute force to the pattern: Simulating time t = 0, 1, 2, … with a flood fill each time is O(n⁴). A min-heap search (or binary search on t plus a flood fill) gives O(n² log n).

Spot it: The cost of a path is its highest cell (a bottleneck), and you want the path whose highest cell is lowest. That's Dijkstra on a grid with a min-heap, where cost is combined with max instead of +.

Approach (step by step):

1. Push (grid[0][0], 0, 0) into a min-heap and mark the start as seen.
2. Pop the entry with the smallest time t. If it's the goal, return t.
3. For each unseen neighbor, push (max(t, its elevation), nr, nc) and mark it seen.
4. Popped times never decrease, so the first time the goal is popped its time is optimal.

import heapq                    # heapq = a min-heap: heappop() always returns the smallest item
from typing import List


class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        size = len(grid)
        directions = [[-1, 0], [0, 1], [1, 0], [0, -1]]
        heap = []
        heapq.heappush(heap, [grid[0][0], 0, 0])    # [time needed so far, row, col]
        seen = set()
        seen.add((0, 0))
        while len(heap) > 0:
            item = heapq.heappop(heap)              # the cheapest cell we can reach next
            time_needed = item[0]
            row = item[1]
            col = item[2]
            if row == size - 1 and col == size - 1:
                return time_needed                  # first time the goal comes out = best time
            for direction in directions:
                next_row = row + direction[0]
                next_col = col + direction[1]
                if next_row >= 0 and next_row < size and next_col >= 0 and next_col < size:
                    if (next_row, next_col) not in seen:
                        seen.add((next_row, next_col))
                        # A path is only as good as its highest cell
                        new_time = time_needed
                        if grid[next_row][next_col] > new_time:
                            new_time = grid[next_row][next_col]
                        heapq.heappush(heap, [new_time, next_row, next_col])
        return -1

What the code is doing, line by line:

1. The "cost" of a path is the highest elevation on it, because you have to wait until the water reaches that height. We want the path whose highest cell is as low as possible.
2. A min-heap (heapq) always gives back the item with the smallest first number. Each item is [time needed so far, row, col].
3. Pop the cheapest cell. If it's the goal, return its time. Popped times never go down, so the first time the goal comes out is the best.
4. For each unseen neighbour, its time is the larger of the current time and the neighbour's elevation (the if-block computes this maximum by hand). Mark it seen and push it.
5. This is Dijkstra's algorithm with "maximum" in place of "sum".

Dry run on the example:

grid [[0,2],[1,3]]

Pop [time, row, col]	Pushed	Heap afterwards
[0, 0, 0]	[2, 0, 1], [1, 1, 0]	[1,1,0], [2,0,1]
[1, 1, 0]	[3, 1, 1] (max of 1 and 3)	[2,0,1], [3,1,1]
[2, 0, 1]	nothing new	[3,1,1]
[3, 1, 1]	goal → return 3

Edge cases to test:

• A 1 × 1 grid → that cell's value.
• The start cell is high (the answer is at least grid[0][0]).
• A high wall that must be crossed.

Complexity: O(n² log n) time, O(n²) space. (Alternative: binary search on t + flood fill.)

Problem: Each cell of board is live (1) or dead (0). Apply Conway's rules to all cells simultaneously: a live cell with 2 or 3 live neighbours lives, otherwise it dies; a dead cell with exactly 3 live neighbours becomes live. Update board in place.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: m == board.length · n == board[i].length · 1 ≤ m, n ≤ 25 · board[i][j] is 0 or 1.

From brute force to the pattern: Copying the board and reading neighbours from the copy uses O(r · c) extra space. Encoding both states in each cell does it in place.

Spot it: Visit every cell and look at its 8 neighbours: a matrix traversal with a direction list. The difficulty is "simultaneously": once a cell is overwritten, its neighbours would read the new value.

Key insight: Keep both states in one integer. Bit 0 (value & 1) is the current state; set bit 1 (value | 2) to mark "alive next round". Neighbours only read bit 0, so they still see the old board. A final pass shifts every cell right by one (value >> 1) to keep just the new state.

Approach:

1. For every cell, count live neighbours using board[nr][nc] & 1 (only the current state).
2. If the cell will be alive next round (live with 2–3 neighbours, or dead with exactly 3), set bit 1: board[r][c] |= 2.
3. After all cells are marked, replace each value with value >> 1, the next state.

class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        rows = len(board)
        cols = len(board[0])
        directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
        # pass 1: decide the next state, store it in bit 1 (value 2)
        for r in range(rows):
            for c in range(cols):
                live = 0
                for dr, dc in directions:
                    nr = r + dr
                    nc = c + dc
                    if 0 <= nr < rows and 0 <= nc < cols:
                        live = live + (board[nr][nc] & 1)   # bit 0 = the CURRENT state
                alive_now = board[r][c] & 1
                if alive_now == 1 and (live == 2 or live == 3):
                    board[r][c] = board[r][c] | 2           # survives
                if alive_now == 0 and live == 3:
                    board[r][c] = board[r][c] | 2           # is born
        # pass 2: keep only the next state
        for r in range(rows):
            for c in range(cols):
                board[r][c] = board[r][c] >> 1

What the code is doing, line by line:

1. directions: the 8 neighbour offsets (including diagonals).
2. if 0 <= nr < rows and 0 <= nc < cols: skip neighbours outside the board.
3. live + (board[nr][nc] & 1): & 1 keeps only bit 0, the cell's state before this round, even if that neighbour was already marked with bit 1.
4. board[r][c] | 2: set bit 1 = "alive next round". Bit 0 is untouched, so later neighbours still read the old state.
5. Cells that die or stay dead simply never get bit 1.
6. board[r][c] >> 1: shift right by one bit, dropping the old state and keeping the new one (3 → 1, 2 → 1, 1 → 0, 0 → 0).

Dry run on the example:

board = [[0, 1, 0], [0, 0, 1], [1, 1, 1], [0, 0, 0]] (LeetCode Example 1). Result [[0, 0, 0], [1, 0, 1], [0, 1, 1], [0, 1, 0]].

cell	now	live neighbours	rule	value after pass 1	after >> 1
(0, 0)	0	1	stays dead	0	0
(0, 1)	1	1	dies	1	0
(0, 2)	0	2	stays dead	0	0
(1, 0)	0	3	born	2	1
(1, 1)	0	5	stays dead	0	0
(1, 2)	1	3	survives	3	1
(2, 0)	1	1	dies	1	0
(2, 1)	1	3	survives	3	1
(2, 2)	1	2	survives	3	1
(3, 0)	0	2	stays dead	0	0
(3, 1)	0	3	born	2	1
(3, 2)	0	2	stays dead	0	0

Edge cases to test:

• Cells on the border have fewer neighbours.
• A 1 × 1 board.
• Stable patterns (nothing changes).

Complexity: O(rows · cols) time (8 checks per cell), O(1) extra space.

Problem: Simulate a robot (turn left −2, right −1, move k) that stops before obstacles; return the maximum squared distance from the origin.

Solve it on LeetCode ↗

Constraints: 1 ≤ commands.length ≤ 10⁴ · commands[i] is either -2, -1, or an integer in the range [1, 9]. · 0 ≤ obstacles.length ≤ 10⁴ · -3 * 10⁴ ≤ xi, yi ≤ 3 * 10⁴ · The answer is guaranteed to be less than 2³¹.

From brute force to the pattern: Scanning the obstacle list on every step is O(steps · obstacles); a set makes each check O(1).

Spot it: A pure simulation on the grid. Keep the direction as an index into [(0,1),(1,0),(0,−1),(−1,0)] and obstacles in a hash set for O(1) checks.

Why not another pattern? Checking each step against the obstacle list is O(obstacles) per step.

Approach:

1. Direction index d: right turn d + 1, left turn d + 3 (mod 4).
2. Move k single steps; stop before a step that lands on an obstacle.
3. After each command, update the maximum x² + y².

class Solution:
    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # north, east, south, west
        blocked = set(map(tuple, obstacles))
        x = y = 0
        d = 0
        best = 0
        for cmd in commands:
            if cmd == -1:
                d = (d + 1) % 4  # turn right
            elif cmd == -2:
                d = (d + 3) % 4  # turn left
            else:
                dx, dy = dirs[d]
                for _ in range(cmd):
                    if (x + dx, y + dy) in blocked:
                        break  # stop in front of the obstacle
                    x += dx
                    y += dy
                best = max(best, x * x + y * y)
        return best

What the code is doing, line by line:

1. Turning is moving through the direction list: +1 clockwise, +3 (= −1) counter-clockwise.
2. Single steps are needed so the robot stops exactly in front of an obstacle.
3. An obstacle at the origin only matters when moving back onto it, which the step check handles naturally.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Obstacle at (0, 0).
• Several turns in a row.
• The maximum distance happens mid-route, not at the end.

Complexity: O(Σ steps + obstacles) time, O(obstacles) space.

Problem: In a grid of land (0) and water (1), count islands of 0s completely surrounded by water (not touching the edge).

Solve it on LeetCode ↗

Constraints: 1 ≤ grid.length, grid[0].length ≤ 100 · 0 ≤ grid[i][j] ≤1

From brute force to the pattern: Running a fresh border check for each land cell separately is O((mn)²); two flood-fill passes are O(mn).

Spot it: An island is closed unless it touches the border. Flood-fill from every border land cell to remove those islands, then count the islands left (each flood fill = one island).

Why not another pattern? Checking "does this island touch the border?" during one DFS works too, but the two-pass version avoids early-return mistakes.

Approach:

1. Flood-fill (turn to 1) every land cell connected to the border.
2. Scan the grid; each remaining 0 starts a new closed island: count it and flood-fill it.

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])

        def sink(r, c):
            stack = [(r, c)]
            grid[r][c] = 1
            while stack:
                r, c = stack.pop()
                for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0:
                        grid[nr][nc] = 1  # turn land into water so it's not counted again
                        stack.append((nr, nc))

        for r in range(rows):
            for c in range(cols):
                if (r in (0, rows - 1) or c in (0, cols - 1)) and grid[r][c] == 0:
                    sink(r, c)  # touches the border: not closed
        closed = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 0:
                    closed += 1  # every remaining island is closed
                    sink(r, c)
        return closed

What the code is doing, line by line:

1. The first pass removes exactly the islands that reach the border.
2. Each flood fill in the second pass consumes one whole closed island.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• All land touches the border → 0.
• A single enclosed land cell.
• Nested shapes (water inside land inside water).

Complexity: O(m · n) time, O(m · n) worst-case stack.

Problem: Each cell is one of 6 street pieces. Starting at (0, 0) and following streets, can you reach the bottom-right cell?

Solve it on LeetCode ↗

Constraints: m == grid.length · n == grid[i].length · 1 ≤ m, n ≤ 300 · 1 ≤ grid[i][j] ≤ 6

From brute force to the pattern: Following streets without a visited set can loop forever; DFS with seen is O(mn).

Spot it: A grid graph traversal where edges depend on cell types. An edge between two cells exists only when both pieces connect to each other: my street must point to the neighbour, and the neighbour's street must point back.

Why not another pattern? Following only your own street's exits can step into a neighbour whose piece doesn't connect back.

Approach:

1. Table of exits per street type, as (dr, dc).
2. DFS from (0, 0). For each exit (dr, dc), the neighbour must have exit (−dr, −dc).
3. Return true on reaching the corner.

class Solution:
    def hasValidPath(self, grid: List[List[int]]) -> bool:
        L, R, U, D = (0, -1), (0, 1), (-1, 0), (1, 0)
        exits = {1: (L, R), 2: (U, D), 3: (L, D), 4: (R, D), 5: (L, U), 6: (R, U)}
        rows, cols = len(grid), len(grid[0])
        seen = {(0, 0)}
        stack = [(0, 0)]
        while stack:
            r, c = stack.pop()
            if (r, c) == (rows - 1, cols - 1):
                return True
            for dr, dc in exits[grid[r][c]]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in seen:
                    if (-dr, -dc) in exits[grid[nr][nc]]:  # the neighbour connects back to us
                        seen.add((nr, nc))
                        stack.append((nr, nc))
        return False

What the code is doing, line by line:

1. exits[t] lists the two directions street type t opens towards.
2. Moving (dr, dc) arrives at the neighbour from direction (−dr, −dc), which its street must open to.
3. Standard DFS with a visited set finds whether the corner is reachable.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A 1×1 grid → true.
• Streets that point toward each other but don't match.
• Loops of streets.

Complexity: O(m · n) time and space.

Problem: Is there a cycle of length ≥ 4 moving between adjacent cells with the same letter (no immediate backtracking)?

Solve it on LeetCode ↗

Constraints: m == grid.length · n == grid[i].length · 1 ≤ m, n ≤ 500 · grid consists only of lowercase English letters.

From brute force to the pattern: Searching for cycles from every cell separately is O((mn)²); one DFS per component is O(mn).

Spot it: Cycle detection in an undirected graph: DFS remembering each cell's parent. Meeting an already visited cell (other than the parent) closes a cycle; in a grid such a cycle always has length ≥ 4.

Why not another pattern? Union-find over equal-letter edges also works; DFS with a parent is the direct translation of the definition.

Approach:

1. For each unvisited cell, start an iterative DFS carrying (cell, parent).
2. For each same-letter neighbour: if it isn't the parent and is visited → cycle.
3. Otherwise mark it visited and push it with the current cell as parent.

class Solution:
    def containsCycle(self, grid: List[List[str]]) -> bool:
        rows, cols = len(grid), len(grid[0])
        seen = [[False] * cols for _ in range(rows)]
        for sr in range(rows):
            for sc in range(cols):
                if seen[sr][sc]:
                    continue
                seen[sr][sc] = True
                stack = [(sr, sc, -1, -1)]  # cell and the cell we came from
                while stack:
                    r, c, pr, pc = stack.pop()
                    for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                        if not (0 <= nr < rows and 0 <= nc < cols) or grid[nr][nc] != grid[r][c]:
                            continue
                        if (nr, nc) == (pr, pc):
                            continue  # don't walk straight back
                        if seen[nr][nc]:
                            return True  # reached a visited cell another way: a cycle
                        seen[nr][nc] = True
                        stack.append((nr, nc, r, c))
        return False

What the code is doing, line by line:

1. Each component of equal letters is explored once.
2. In a tree-shaped component, every visited neighbour is the parent. Any other visited neighbour means two different routes, i.e. a cycle.
3. Grid cycles can't be shorter than 4, so the length condition holds automatically.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A 2×2 block of the same letter (smallest cycle).
• A long snake without a cycle.
• All distinct letters.

Complexity: O(m · n) time and space.

Problem: Rotate every layer (ring) of an even-sized grid counter-clockwise k times (k up to 10⁹).

Solve it on LeetCode ↗

Constraints: m == grid.length · n == grid[i].length · 2 ≤ m, n ≤ 50 · Both m and n are even integers. · 1 ≤ grid[i][j] ≤ 5000 · 1 ≤ k ≤ 10⁹

From brute force to the pattern: Simulating each single rotation is O(k · m · n). Unrolling, shifting once and writing back is O(m · n).

Spot it: A layer is a cycle of cells. Read it into a list in clockwise order, rotate the list (k % length), and write it back along the same path. Counter-clockwise by one = every value moves one step back along the clockwise list.

Why not another pattern? Rotating one step at a time k times is O(k · cells) with k up to 10⁹.

Approach:

1. For each layer l: list the cells clockwise (top row, right column, bottom row reversed, left column upward).
2. vals = [grid[r][c] for (r, c) in cells], shift by s = k % len(cells): vals[s:] + vals[:s].
3. Write the shifted values back into the same cells.

class Solution:
    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
        m, n = len(grid), len(grid[0])
        for layer in range(min(m, n) // 2):
            top, left = layer, layer
            bottom, right = m - 1 - layer, n - 1 - layer
            cells = [(top, c) for c in range(left, right)]  # clockwise walk of this ring
            cells += [(r, right) for r in range(top, bottom)]
            cells += [(bottom, c) for c in range(right, left, -1)]
            cells += [(r, left) for r in range(bottom, top, -1)]
            vals = [grid[r][c] for r, c in cells]
            s = k % len(cells)  # full turns change nothing
            vals = vals[s:] + vals[:s]  # counter-clockwise: each value moves one place back
            for (r, c), v in zip(cells, vals):
                grid[r][c] = v
        return grid

What the code is doing, line by line:

1. Each side range stops one short of the corner so every ring cell appears exactly once.
2. A counter-clockwise rotation moves the value at position i + 1 to position i in the clockwise list: a left shift.
3. k % len(cells) removes complete turns.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• k a multiple of a layer's length (no change for that layer).
• 2×2 grid.
• Rectangular grids (layers of different shapes).

Complexity: O(m · n) time and O(m + n) extra space per layer.

Problem: In an m × n grid with given black cells, count how many 2×2 blocks contain exactly 0, 1, 2, 3 and 4 black cells.

Solve it on LeetCode ↗

Constraints: 2 ≤ m ≤ 10⁵ · 2 ≤ n ≤ 10⁵ · 0 ≤ coordinates.length ≤ 10⁴ · coordinates[i].length == 2 · 0 ≤ coordinates[i][0] < m · 0 ≤ coordinates[i][1] < n · It is guaranteed that coordinates contains pairwise distinct coordinates.

From brute force to the pattern: Checking all (m − 1)(n − 1) blocks is up to 10¹⁰. Visiting only blocks next to black cells is O(k).

Spot it: The grid can be 10⁵ × 10⁵, but there are only 10⁴ black cells. Each black cell lies in at most four blocks (top-left corners (x−1..x, y−1..y)). A hash map counts black cells per block that has any; every other block has 0.

Why not another pattern? Scanning every block is O(m · n) = 10¹⁰.

Approach:

1. For each black cell (x, y), for each top-left corner (x − dx, y − dy) with dx, dy ∈ {0, 1} inside the valid range, increment count[corner].
2. answer[c] = number of corners with count c (for 1..4).
3. answer[0] = (m − 1)(n − 1) − (number of corners in the map).

from collections import Counter

class Solution:
    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:
        blocks = Counter()  # top-left corner -> black cells inside that block
        for x, y in coordinates:
            for bx in (x - 1, x):
                for by in (y - 1, y):
                    if 0 <= bx < m - 1 and 0 <= by < n - 1:
                        blocks[(bx, by)] += 1  # this block contains (x, y)
        answer = [0] * 5
        for count in blocks.values():
            answer[count] += 1
        answer[0] = (m - 1) * (n - 1) - len(blocks)  # blocks no black cell touched
        return answer

What the code is doing, line by line:

1. The block with top-left (bx, by) covers rows bx..bx+1 and columns by..by+1, so cell (x, y) is in the blocks with bx ∈ {x−1, x} and by ∈ {y−1, y}.
2. Corners outside 0..m−2 / 0..n−2 don't start a valid block.
3. All blocks not in the map are fully white.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No black cells → all blocks have 0.
• Black cells on the border (fewer blocks).
• A full 2×2 black square (count 4).

Complexity: O(k) time and space for k black cells.

Problem: For every k × k submatrix, return the minimum absolute difference between two distinct values in it (0 if all equal).

Solve it on LeetCode ↗

Constraints: 1 ≤ m == grid.length ≤ 30 · 1 ≤ n == grid[i].length ≤ 30 · -10⁵ ≤ grid[i][j] ≤ 10⁵ · 1 ≤ k ≤ min(m, n)

From brute force to the pattern: Comparing all pairs in each window is O(k⁴) per window; sorting the window is O(k² log k).

Spot it: Grids are at most 30 × 30, so each window can be handled directly. The closest pair of numbers is always adjacent after sorting, so sort the window's distinct values and take the smallest neighbouring gap.

Why not another pattern? Comparing every pair inside a window is O(k⁴) per window; sorting is O(k² log k).

Approach:

1. For each top-left (i, j): collect the window's values into a set and sort them.
2. If there's only one distinct value, the answer is 0.
3. Otherwise the answer is the minimum of vals[t + 1] − vals[t].

class Solution:
    def minAbsDiff(self, grid: List[List[int]], k: int) -> List[List[int]]:
        m, n = len(grid), len(grid[0])
        ans = [[0] * (n - k + 1) for _ in range(m - k + 1)]
        for i in range(m - k + 1):
            for j in range(n - k + 1):
                vals = sorted({grid[r][c] for r in range(i, i + k) for c in range(j, j + k)})  # distinct values
                if len(vals) > 1:
                    ans[i][j] = min(b - a for a, b in zip(vals, vals[1:]))  # closest pair is adjacent once sorted
        return ans

What the code is doing, line by line:

1. The set removes duplicates, since only distinct values count.
2. In sorted order, the closest pair of values must be neighbours.
3. A window with one distinct value keeps the default 0.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• k = 1 → all zeros.
• All values equal in a window → 0.
• Negative values.

Complexity: O((m − k + 1)(n − k + 1) · k² log k) time, O(k²) extra space.

Problem: Given a height map on a 2D grid, return the volume of water it traps after raining.

Solve it on LeetCode ↗

Constraints: m == heightMap.length · n == heightMap[i].length · 1 ≤ m, n ≤ 200 · 0 ≤ heightMap[i][j] ≤ 2 * 10⁴

From brute force to the pattern: For each cell, finding the lowest escape path with a search is O((mn)²). One heap-driven flood fill is O(mn log mn).

Spot it: Water at a cell is limited by the lowest wall on the path to the outside. Start with every border cell in a min-heap; pop the lowest, look at its unvisited neighbours: a lower neighbour fills to the current level. The neighbour joins the boundary at max(its height, level). This is Dijkstra-like flooding on the matrix.

Why not another pattern? The 1D two-pointer trick doesn't extend to 2D: water can escape in any direction, not just left or right.

Approach:

1. Push all border cells (height, r, c) into a min-heap, marked visited.
2. Pop the lowest boundary cell. For each unvisited neighbour: add max(0, level − height) water.
3. Push the neighbour with level max(level, height) and mark it visited.

import heapq

class Solution:
    def trapRainWater(self, heightMap: List[List[int]]) -> int:
        rows, cols = len(heightMap), len(heightMap[0])
        heap = []
        seen = [[False] * cols for _ in range(rows)]
        for r in range(rows):
            for c in range(cols):
                if r in (0, rows - 1) or c in (0, cols - 1):
                    heapq.heappush(heap, (heightMap[r][c], r, c))  # the outer wall
                    seen[r][c] = True
        water = 0
        while heap:
            level, r, c = heapq.heappop(heap)  # lowest point of the current wall
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < rows and 0 <= nc < cols and not seen[nr][nc]:
                    seen[nr][nc] = True
                    h = heightMap[nr][nc]
                    water += max(0, level - h)  # fills up to the lowest wall
                    heapq.heappush(heap, (max(level, h), nr, nc))  # becomes part of the wall
        return water

What the code is doing, line by line:

1. The border can't hold water; it forms the initial wall around everything else.
2. Popping the lowest wall cell is safe: no other route to the outside from its neighbour is lower than this level.
3. A neighbour lower than the level holds level − h water and then acts as a wall of height level.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Grids with fewer than 3 rows or columns → 0.
• A basin inside a basin.
• A low gap in the border drains a region.

Complexity: O(m · n · log(m · n)) time, O(m · n) space.

Problem: Ships are horizontal or vertical lines of X, separated by water. Count them in one pass with O(1) extra memory.

Solve it on LeetCode ↗

Constraints: m == board.length · n == board[i].length · 1 ≤ m, n ≤ 200 · board[i][j] is either '.' or 'X'.

From brute force to the pattern: Flood fill is also O(mn) but needs extra memory or modifies the board.

Spot it: Flood fill would count islands but modifies the board or uses memory. Since ships are straight lines, each has exactly one head: the cell with no ship cell above or to its left. Count heads in a matrix scan.

Why not another pattern? DFS flood fill works but needs a visited set or mutation; the follow-up forbids both.

Approach:

1. For each X: skip it if the cell above or to the left is X.
2. Otherwise it's a ship's first cell: count it.

class Solution:
    def countBattleships(self, board: List[List[str]]) -> int:
        ships = 0
        for r, row in enumerate(board):
            for c, cell in enumerate(row):
                if cell != "X":
                    continue
                if r > 0 and board[r - 1][c] == "X":
                    continue  # continuation of a vertical ship
                if c > 0 and row[c - 1] == "X":
                    continue  # continuation of a horizontal ship
                ships += 1  # the top-left end of a ship
        return ships

What the code is doing, line by line:

1. A straight ship has exactly one cell whose up and left neighbours are not ship cells.
2. Ships never touch, so a neighbouring X always belongs to the same ship.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Single-cell ships.
• Vertical ships.
• No ships.

Complexity: O(m · n) time, O(1) space.

Problem: Return all elements of the matrix in zig-zag diagonal order.

Solve it on LeetCode ↗

Constraints: m == mat.length · n == mat[i].length · 1 ≤ m, n ≤ 10⁴ · 1 ≤ m * n ≤ 10⁴ · -10⁵ ≤ mat[i][j] ≤ 10⁵

From brute force to the pattern: Direction-bouncing simulation is the same O(mn) but much more fiddly.

Spot it: Cells on one anti-diagonal share r + c. Walk the diagonals d = 0 … m + n − 2, alternating direction → a matrix traversal by index arithmetic.

Why not another pattern? Simulating the bouncing direction with boundary cases is easy to get wrong.

Approach:

1. For each d: rows run from max(0, d − n + 1) to min(d, m − 1); c = d − r.
2. Collect that diagonal top to bottom; reverse it when d is even.
3. Append.

class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        m, n = len(mat), len(mat[0])
        out = []
        for d in range(m + n - 1):  # every anti-diagonal r + c = d
            diag = [mat[r][d - r] for r in range(max(0, d - n + 1), min(d, m - 1) + 1)]  # top to bottom
            out.extend(diag[::-1] if d % 2 == 0 else diag)  # even diagonals go up
        return out

What the code is doing, line by line:

1. The row bounds keep c = d − r inside 0..n − 1.
2. The first diagonal goes up and right (bottom to top), which is the reverse of top-to-bottom.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• One row or one column.
• 1×1.
• Non-square matrices.

Complexity: O(m · n) time, O(min(m, n)) extra space per diagonal.

Problem: Apply one click to a Minesweeper board and return the board after the reveal rules.

Solve it on LeetCode ↗

Constraints: m == board.length · n == board[i].length · 1 ≤ m, n ≤ 50 · board[i][j] is either 'M', 'E', 'B', or a digit from '1' to '8'. · click.length == 2 · 0 ≤ clickr < m · 0 ≤ clickc < n · board[clickr][clickc] is either 'M' or 'E'.

From brute force to the pattern: This is the simulation; an explicit stack avoids recursion limits on large boards.

Spot it: Revealing a blank spreads to its neighbours, then theirs → a flood fill (DFS/BFS) over 8 directions on the matrix.

Why not another pattern? Revealing cells one at a time without a fill misses the cascade.

Approach:

1. If the click is on M, mark it X and return.
2. DFS from the click: count mines around an E cell.
3. Count > 0 → write the digit and stop; 0 → write B and continue to unrevealed neighbours.

class Solution:
    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:
        rows, cols = len(board), len(board[0])
        r, c = click
        if board[r][c] == "M":
            board[r][c] = "X"  # clicked a mine: game over
            return board
        around = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
        stack = [(r, c)]
        while stack:
            r, c = stack.pop()
            if board[r][c] != "E":
                continue  # already revealed
            cells = [(r + dr, c + dc) for dr, dc in around if 0 <= r + dr < rows and 0 <= c + dc < cols]
            mines = sum(board[nr][nc] in "MX" for nr, nc in cells)
            if mines:
                board[r][c] = str(mines)  # a number stops the spread
            else:
                board[r][c] = "B"  # blank: reveal everything around it
                stack.extend((nr, nc) for nr, nc in cells if board[nr][nc] == "E")
        return board

What the code is doing, line by line:

1. Only blank (B) cells spread; digit cells stop the cascade.
2. The != "E" check skips cells pushed twice before being revealed.
3. Mines are never revealed by the spread, since a cell next to a mine is a digit.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Clicking a mine.
• Clicking a numbered cell.
• A large empty region.

Complexity: O(m · n) time and space.

Problem: Rows have different lengths. Return all values diagonal by diagonal, each diagonal from bottom-left to top-right.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · 1 ≤ nums[i].length ≤ 10⁵ · 1 ≤ sum(nums[i].length) ≤ 10⁵ · 1 ≤ nums[i][j] ≤ 10⁵

From brute force to the pattern: Scanning the full bounding rectangle wastes time on missing cells; bucketing touches only real values.

Spot it: Same diagonal = same r + c. Rows are ragged, so instead of walking a rectangle, bucket existing cells by r + c in a hash map (or list of lists).

Why not another pattern? Walking every diagonal of the bounding rectangle visits up to 10¹⁰ empty positions.

Approach:

1. For rows from the last to the first, for each column: append to buckets[r + c].
2. Concatenate the buckets in order of r + c.

from collections import defaultdict

class Solution:
    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:
        buckets = defaultdict(list)
        for r in range(len(nums) - 1, -1, -1):  # bottom rows first
            for c, v in enumerate(nums[r]):
                buckets[r + c].append(v)  # same diagonal, already bottom-to-top
        return [v for d in range(len(buckets)) for v in buckets[d]]

What the code is doing, line by line:

1. Visiting rows bottom-up appends each diagonal in the required order.
2. Every key from 0 to the largest r + c occurs (cell (0, 0) starts it, and each row is contiguous), so range(len(buckets)) covers all.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Very uneven row lengths.
• One row.
• One column.

Complexity: O(N) time and space for N values.

Problem: Fill an n × n matrix with 1..n² in clockwise spiral order.

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 20

From brute force to the pattern: This is the direct simulation.

Spot it: Matrix traversal with shrinking boundaries: top row, right column, bottom row, left column, then move all four bounds inward.

Why not another pattern? Direction-turning with visited checks works but boundary shrinking is simpler.

Approach:

1. top, bottom, left, right bounds; k = 1.
2. Fill top row, right column, bottom row (if any), left column (if any).
3. Shrink the bounds and repeat.

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        grid = [[0] * n for _ in range(n)]
        top, bottom, left, right = 0, n - 1, 0, n - 1
        k = 1
        while top <= bottom and left <= right:
            for c in range(left, right + 1):
                grid[top][c] = k; k += 1  # top row, left to right
            top += 1
            for r in range(top, bottom + 1):
                grid[r][right] = k; k += 1  # right column, downwards
            right -= 1
            for c in range(right, left - 1, -1):
                grid[bottom][c] = k; k += 1  # bottom row, right to left
            bottom -= 1
            for r in range(bottom, top - 1, -1):
                grid[r][left] = k; k += 1  # left column, upwards
            left += 1
        return grid

What the code is doing, line by line:

1. Each side shrinks its bound after being filled, so no cell is written twice.
2. For a square matrix the loops naturally stop when the bounds cross.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• n = 1.
• Even n.
• Odd n (centre cell).

Complexity: O(n²) time, O(1) extra space.

Problem: Flip any rows or columns (toggle all bits). Read each row as a binary number; maximise the sum.

Solve it on LeetCode ↗

Constraints: m == grid.length · n == grid[i].length · 1 ≤ m, n ≤ 20 · grid[i][j] is either 0 or 1.

From brute force to the pattern: All flip combinations are exponential; the greedy is O(mn).

Spot it: The leading bit is worth more than all lower bits combined, so first make every row start with 1 (row flips). After that, each column independently should have as many 1s as possible (column flips) — a greedy matrix scan.

Why not another pattern? Trying all 2^(m + n) flip combinations is exponential.

Approach:

1. Rows starting with 0 count as flipped.
2. For each column c: ones = cells equal to the row's first bit.
3. Add max(ones, m − ones) · 2^(n − 1 − c).

class Solution:
    def matrixScore(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        total = 0
        for c in range(n):
            ones = sum(row[c] == row[0] for row in grid)  # after flipping rows so they start with 1
            total += max(ones, m - ones) << (n - 1 - c)  # flip the column if that gives more 1s
        return total

What the code is doing, line by line:

1. A cell equals 1 after the row flip exactly when it matches the row's first bit.
2. Column choices don't interact, so each takes the better of its two options.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• One column.
• Already all ones.
• Ties in a column.

Complexity: O(m · n) time, O(1) space.

Problem: Swap adjacent rows so every cell above the main diagonal is 0. Return the fewest swaps, or −1.

Solve it on LeetCode ↗

Constraints: n == grid.length == grid[i].length · 1 ≤ n ≤ 200 · grid[i][j] is either 0 or 1

From brute force to the pattern: Permutations are factorial; the greedy is O(n²).

Spot it: Only each row's count of trailing zeros matters: row i needs at least n − 1 − i. Fill positions top-down, each time bubbling up the nearest row that qualifies (a greedy on an array derived from the matrix).

Why not another pattern? Searching over row permutations is factorial.

Approach:

1. zeros[r] = trailing zeros of row r.
2. For i from 0: find the first j ≥ i with zeros[j] ≥ n − 1 − i; none → −1.
3. Move it up: add j − i swaps, shift rows down.

class Solution:
    def minSwaps(self, grid: List[List[int]]) -> int:
        n = len(grid)
        zeros = []
        for row in grid:
            k = 0
            while k < n and row[n - 1 - k] == 0:
                k += 1
            zeros.append(k)  # trailing zeros of this row
        swaps = 0
        for i in range(n):
            need = n - 1 - i
            j = i
            while j < n and zeros[j] < need:
                j += 1  # nearest row that can sit at position i
            if j == n:
                return -1
            swaps += j - i
            zeros.insert(i, zeros.pop(j))  # bubble it up, others shift down by one
        return swaps

What the code is doing, line by line:

1. Requirements decrease going down, so a row good enough for position i is good enough for anything lower.
2. Choosing the nearest qualifying row minimises swaps now and keeps stronger rows available.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Already valid → 0.
• Impossible → −1.
• n = 1.

Complexity: O(n²) time, O(n) space.

Problem: Each operation adds or subtracts x from one cell. Return the fewest operations to make all cells equal, or −1.

Solve it on LeetCode ↗

Constraints: m == grid.length · n == grid[i].length · 1 ≤ m, n ≤ 10⁵ · 1 ≤ m * n ≤ 10⁵ · 1 ≤ x, grid[i][j] ≤ 10⁴

From brute force to the pattern: Every target value is too slow; the median is optimal.

Spot it: Adding x keeps each value's remainder mod x, so all remainders must match. Then the cost is Σ |v − t| / x, minimised at the median of the flattened matrix.

Why not another pattern? Trying every target value is O(range · mn).

Approach:

1. Flatten; if any value has a different v % x, return −1.
2. Sort; t = the median.
3. Return Σ |v − t| // x.

class Solution:
    def minOperations(self, grid: List[List[int]], x: int) -> int:
        vals = sorted(v for row in grid for v in row)
        if any((v - vals[0]) % x for v in vals):
            return -1  # different remainders can never meet
        median = vals[len(vals) // 2]  # minimises the sum of distances
        return sum(abs(v - median) for v in vals) // x

What the code is doing, line by line:

1. Values can only move in steps of x, so their remainder never changes.
2. The sum of absolute distances is minimised at the median.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Different remainders → −1.
• Single cell → 0.
• Even count (either middle works).

Complexity: O(mn log(mn)) time, O(mn) space.

Problem: Paint the cells of mat in the order of the values in arr. Return the first index at which some row or column is fully painted.

Solve it on LeetCode ↗

Constraints: m == mat.length · n = mat[i].length · arr.length == m * n · 1 ≤ m, n ≤ 10⁵ · 1 ≤ m * n ≤ 10⁵ · 1 ≤ arr[i], mat[r][c] ≤ m * n · All the integers of arr are unique. · All the integers of mat are unique.

From brute force to the pattern: Rechecking rows and columns each step is O(mn(m + n)); counters make it O(mn).

Spot it: Locate a value's cell in O(1) with a hash map, then keep painted counts per row and column.

Why not another pattern? Scanning the row and column after each paint is O(m + n) per step.

Approach:

1. where[value] = (r, c).
2. For each arr[i]: increment rows[r] and cols[c].
3. If rows[r] == n or cols[c] == m, return i.

class Solution:
    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        where = {mat[r][c]: (r, c) for r in range(m) for c in range(n)}
        rows, cols = [0] * m, [0] * n  # painted cells per row / column
        for i, v in enumerate(arr):
            r, c = where[v]
            rows[r] += 1
            cols[c] += 1
            if rows[r] == n or cols[c] == m:
                return i  # a whole row or column is painted
        return -1

What the code is doing, line by line:

1. A row is complete when n of its cells are painted, a column when m are.
2. Values are distinct, so each paint touches one cell.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• One row (the first paint completes a column).
• One column.
• Completion on the last paint.

Complexity: O(m · n) time and space.

Problem: Start at a 1, follow 2, 0, 2, 0, … along a diagonal, optionally turning 90° clockwise once. Return the longest such segment.

Solve it on LeetCode ↗

Constraints: n == grid.length · m == grid[i].length · 1 ≤ n, m ≤ 500 · grid[i][j] is either 0, 1 or 2.

From brute force to the pattern: Exploring all paths from every 1 repeats work; memoisation makes it linear in the states.

Spot it: From each cell the segment continues in its direction or turns once; the rest of the path depends only on (cell, direction, whether the turn is used, next expected value) → memoised DFS on the matrix.

Why not another pattern? Walking every path from every 1 separately repeats the same suffixes many times.

Approach:

1. Directions in clockwise order: ↘, ↙, ↖, ↗.
2. go(r, c, d, can_turn, want): 0 if outside or the value isn't want; else 1 + the best of continuing straight and (if allowed) turning clockwise.
3. For every 1 and each direction: 1 + go(next cell, d, True, 2).

from functools import lru_cache

class Solution:
    def lenOfVDiagonal(self, grid: List[List[int]]) -> int:
        n, m = len(grid), len(grid[0])
        dirs = [(1, 1), (1, -1), (-1, -1), (-1, 1)]  # clockwise: down-right, down-left, up-left, up-right

        @lru_cache(maxsize=None)
        def go(r, c, d, can_turn, want):  # longest continuation starting at (r, c)
            if not (0 <= r < n and 0 <= c < m) or grid[r][c] != want:
                return 0
            nxt = 2 if want == 0 else 0  # sequence 2, 0, 2, 0, ...
            dr, dc = dirs[d]
            best = go(r + dr, c + dc, d, can_turn, nxt)  # keep going straight
            if can_turn:
                nd = (d + 1) % 4  # one clockwise turn
                best = max(best, go(r + dirs[nd][0], c + dirs[nd][1], nd, False, nxt))
            return 1 + best

        best = 0
        for r in range(n):
            for c in range(m):
                if grid[r][c] == 1:
                    for d, (dr, dc) in enumerate(dirs):
                        best = max(best, 1 + go(r + dr, c + dc, d, True, 2))
        return best

What the code is doing, line by line:

1. The state captures everything that affects the rest of the segment, so memoisation is safe.
2. The turn changes the direction for the next step and uses up the turn.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No 1 → 0.
• A segment of just the 1.
• Turning at the very first step.

Complexity: O(n · m · 4 · 2) states with O(1) work each.