Map of Highest Peak

Map of Highest Peak

What is this problem about?

In the Map of Highest Peak problem, you are given an integer matrix representing a topographical map where 0 is a land cell and 1 is a water cell. You must assign a height to every cell such that all water cells have a height of exactly 0, and any two adjacent cells (horizontally or vertically) have an absolute height difference of at most 1. Your goal is to maximize the height of the land cells and return the resulting height matrix.

Why is this asked in interviews?

This is a textbook Graph traversal problem. Interviewers use it to see if a candidate can correctly identify the need for a Multi-source Breadth-First Search (BFS). It perfectly evaluates your ability to ripple state outwards uniformly. Attempting to solve this with DFS or dynamic programming often leads to complex, failing logic because heights must grow uniformly from all water sources simultaneously.

Algorithmic pattern used

The definitive solution uses Multi-source Breadth-First Search (BFS).

1. Create a result matrix filled with -1 (indicating unvisited cells).
2. Scan the original grid: for every water cell (1), set its height to 0 in the result matrix and add its coordinates to a Queue.
3. Perform a standard BFS using the Queue. For each cell popped, look at its 4 neighbors. If a neighbor is unvisited (-1), assign it a height of current_cell_height + 1, and push it into the Queue. Because BFS guarantees the shortest path from a source, the height assigned will perfectly satisfy the constraints.

Example explanation

Grid:

1 0
0 0

(1 is water, 0 is land). Result matrix initialized:

 0 -1
-1 -1

Queue starts with [(0, 0)] (the water cell).

• Pop (0, 0) with height 0. Check neighbors.
• Neighbor (0, 1) is -1. Set to 0 + 1 = 1. Push (0, 1).
• Neighbor (1, 0) is -1. Set to 0 + 1 = 1. Push (1, 0). Result matrix:

0  1
1 -1

• Pop (0, 1) with height 1. Neighbor (1, 1) is -1. Set to 1 + 1 = 2. Push (1, 1). Result matrix:

0 1
1 2

Every land cell has been assigned the maximum valid height based on its shortest distance to water.

Common mistakes candidates make

A common mistake is trying to run a separate BFS from every single land cell to find its nearest water cell. This creates an $O((M \times N)^2)$ time complexity, leading to Time Limit Exceeded. You must work in reverse: start from ALL water cells simultaneously. Another mistake is forgetting to mark cells as "visited" before pushing them to the queue, which causes the queue to explode with duplicate coordinate entries.

Interview preparation tip

When tackling the Map of Highest Peak coding problem, recognize that "distance to the nearest source" problems always require Multi-source BFS. You don't need multiple queues; just enqueue all the source nodes (water cells) at the very beginning before the while loop starts. The queue will naturally process them in order of distance.