Map of Highest Peak: Multi-Source BFS on a Grid

You are given an m x n integer matrix isWater where isWater[i][j] == 0 represents a land cell and isWater[i][j] == 1 represents a water cell. You need to assign a height to each cell such that the height of water cells is 0, the absolute difference in height between any two adjacent cells (sharing an edge) is at most 1, and the maximum height in the matrix is as large as possible.

This is LeetCode 1765: Map of Highest Peak, a medium-difficulty problem that teaches multi-source BFS on a grid. If you have seen the "01 Matrix" problem, this one will feel familiar, but the framing is different enough to be worth studying on its own.

Why this problem matters

Grid problems that ask "find the distance from every cell to the nearest source" appear constantly in interviews and contests. The pattern is always the same: start BFS from all source cells at once and let the wavefront expand outward. Map of Highest Peak is a clean example of this pattern because the "height" you assign to each cell is exactly its BFS distance from the nearest water cell. Once you see that connection, the solution writes itself.

This problem also reinforces a general principle: when you need to compute distances from multiple sources simultaneously, you do not run BFS once per source. You run a single BFS with all sources in the initial queue. That cuts the time from O(k * m * n) to O(m * n), where k is the number of sources.

The key insight

Every water cell must have height 0. Every land cell should be as tall as possible, but adjacent cells can differ by at most 1. The tallest a land cell can be is its shortest distance to the nearest water cell. If it were any taller, the "at most 1" constraint would break somewhere along the path back to water.

This means you can frame the problem as multi-source BFS. Enqueue all water cells with height 0. Then expand outward: each unvisited neighbor gets height current + 1. Because BFS explores in order of distance, the first time you reach a cell is guaranteed to be along a shortest path. The heights are automatically maximized.

The algorithm:

1. Scan the grid. For every water cell, set its height to 0 and add it to the BFS queue.
2. For every land cell, set its height to -1 (unvisited).
3. Process the queue. For each cell, check its four neighbors. If a neighbor has height -1, set its height to the current cell's height plus 1 and enqueue it.
4. When the queue is empty, every cell has been assigned the maximum valid height.

The solution

from collections import deque

def highest_peak(is_water: list[list[int]]) -> list[list[int]]:
    rows, cols = len(is_water), len(is_water[0])
    height = [[-1] * cols for _ in range(rows)]
    queue = deque()

    for r in range(rows):
        for c in range(cols):
            if is_water[r][c] == 1:
                height[r][c] = 0
                queue.append((r, c))

    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    while queue:
        r, c = queue.popleft()
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and height[nr][nc] == -1:
                height[nr][nc] = height[r][c] + 1
                queue.append((nr, nc))

    return height

Let's walk through what each piece does.

The first loop initializes the BFS. It scans the entire grid, sets every water cell's height to 0, and adds it to the queue. Land cells stay at -1, which serves as the "unvisited" marker. This is the multi-source setup: instead of starting BFS from one cell, you start from every water cell simultaneously.

The BFS loop processes cells one at a time. For each cell, it checks all four neighbors. If a neighbor has not been visited yet (height is -1), it assigns a height one greater than the current cell and adds the neighbor to the queue. Because BFS processes cells in order of increasing distance, the first assignment is always the shortest path, which means the maximum valid height.

Notice there is no level-by-level processing with range(len(queue)) here. You do not need it because you are not tracking a "time" counter. The height is stored directly in the matrix, so each cell already knows its own distance. You just propagate it to unvisited neighbors.

Visual walkthrough

Let's trace through a 3x3 example where water cells sit at positions (0,2) and (2,0). Watch how BFS assigns heights level by level, expanding outward from both water cells at the same time.

Notice how cells equidistant from different water sources get the same height. Cell (1,1) is 2 steps from both (0,2) and (2,0), so it gets height 2. The wavefront from each water cell merges naturally because BFS explores all cells at distance 1 before any cell at distance 2.

Complexity analysis

Time is O(m * n) where m is the number of rows and n is the number of columns. The initialization scans every cell once. The BFS visits each cell at most once because a cell is only enqueued when its height changes from -1, and that happens exactly once. Total work is proportional to the grid size.

Space is O(m * n) for the height matrix and the BFS queue. The height matrix has m * n entries. The queue can hold at most m * n cells in the worst case (if the entire grid is water, all cells start in the queue). In practice, the queue holds only the current BFS frontier, which is typically much smaller.

The building blocks

1. Multi-source BFS initialization

The pattern of seeding a BFS queue with every source cell at once:

queue = deque()
for r in range(rows):
    for c in range(cols):
        if is_source(r, c):
            distance[r][c] = 0
            queue.append((r, c))

This is the only difference between single-source and multi-source BFS. You mark all sources with distance 0 and enqueue them before the BFS loop begins. The rest of the algorithm is identical. You will use this pattern in "Rotting Oranges" (LeetCode 994), "01 Matrix" (LeetCode 542), "Walls and Gates" (LeetCode 286), and any problem that asks for shortest distances from multiple starting points.

2. BFS distance propagation on a grid

The pattern of assigning each cell a value based on its BFS distance from the sources:

while queue:
    r, c = queue.popleft()
    for dr, dc in directions:
        nr, nc = r + dr, c + dc
        if in_bounds(nr, nc) and not visited(nr, nc):
            distance[nr][nc] = distance[r][c] + 1
            queue.append((nr, nc))

This is standard BFS on a grid with distance tracking. The key detail is that you store the distance directly in the result matrix and use -1 as the "unvisited" sentinel. When you dequeue a cell, its distance is already finalized, so you can safely assign distance + 1 to its neighbors. This avoids the need for a separate visited set.

Edge cases

Before submitting, think through these scenarios:

• Single water cell: the entire grid radiates outward from one source. The farthest cell gets a height equal to the maximum Manhattan distance from that water cell.
• All water: every cell has height 0. The BFS queue starts full and nothing gets enqueued during processing.
• One row or one column: the grid is essentially a 1D array. Heights increase linearly from each water cell.
• Water cells in opposite corners: heights form a diamond pattern. Cells equidistant from both sources get the same height, and the maximum height is at the center of the grid.
• Adjacent water cells: they both start at height 0 and their wavefronts overlap immediately. No conflict, because both assign the same values to shared neighbors.

From understanding to recall

You have seen how multi-source BFS solves Map of Highest Peak: seed the queue with all water cells at height 0, expand outward, and assign each land cell a height equal to its distance from the nearest water. The algorithm is short and the logic is clean.

But knowing how it works and writing it under pressure are two different things. The details that trip people up are small but critical. Do you initialize land cells to -1 or to infinity? Do you check height[nr][nc] == -1 or height[nr][nc] > height[r][c] + 1? Do you need level-by-level processing or not? These are not conceptual questions. They are recall questions, and they cost time in interviews.

Spaced repetition is how you move from understanding to automatic recall. You practice writing the multi-source initialization and the BFS propagation loop from memory at increasing intervals. After a few rounds, the code flows out without hesitation. You see "assign values based on distance from sources" in a problem statement, and the BFS template is already in your hands.

Related posts

• Rotting Oranges - Multi-source BFS where rotten oranges spread to neighbors each minute, the same "expand from all sources" pattern
• 01 Matrix - The near-twin of this problem: find the distance from every cell to the nearest 0 using the same multi-source BFS approach
• Pacific Atlantic Water Flow - Multi-source BFS from ocean borders, showing another angle on the "start from multiple sources" technique

CodeBricks breaks Map of Highest Peak into its multi-source BFS initialization and distance propagation building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a grid BFS problem shows up in your interview, you do not think about it. You just write it.