Map of Highest Peak
Problem Statement
You get a map where each cell is either water or land. Assign every cell a height so that:
- every water cell has height 0,
- every height is 0 or more,
- any two cells that share a side differ in height by at most 1.
Choose the heights so that the highest cell on the map is as high as possible. Return the height grid. If several grids reach the largest possible top height, any of them is accepted.
isWater, an m × n grid. 1 = water, 0 = land. There is at least one water cell.
An m × n height grid that follows the rules above and whose highest cell is as high as possible.
The water is the top-right cell, at height 0. The land next to it is at height 1, and the far corner is 2 steps from the water, so it can be 2.
The highest cell can reach 2. The bottom-middle cell is 2 steps from the nearest water, so 2 is the most it can be.
The only water is at the left end. The height goes up by 1 for each step away from it.
- • m == isWater.length and n == isWater[i].length
- • 1 ≤ m, n ≤ 1000
- • Each cell is 0 (land) or 1 (water).
- • There is at least one water cell.
Pattern Recognition Clues
Recognising these key signals in the problem description immediately identifies the pattern:
Approach Complexity Ladder
Start with water at 0 and land at unknown; sweep the grid, lowering each land cell to a neighbour's height + 1, until a sweep changes nothing
Put every water cell in the queue at height 0; each land cell gets the height of the first wave that reaches it
Start water at 0 and land at 'unknown'. Sweep the grid. For each land cell, look at its four neighbours and lower the cell to one more than the smallest neighbour if that is lower than its current value. Repeat sweeps until a whole sweep changes nothing. The stable grid is the answer.
Recognition rule for this sub-pattern:
Unlock Complete Visual Walkthrough & Optimal C++
The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.
First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.
How this concept connects to System Design & C++ Systems
Top engineering interviews test whether you understand how algorithms like Graph BFS / DFS translate into production architectures and low-level memory mechanics.