Map of Highest Peak - Problem

You are given an integer matrix isWater of size m x n that represents a map of land and water cells.

If isWater[i][j] == 0, cell (i, j) is a land cell.
If isWater[i][j] == 1, cell (i, j) is a water cell.

You must assign each cell a height in a way that follows these rules:

  • The height of each cell must be non-negative.
  • If the cell is a water cell, its height must be 0.
  • Any two adjacent cells must have an absolute height difference of at most 1. A cell is adjacent to another cell if the former is directly north, east, south, or west of the latter (i.e., their sides are touching).

Find an assignment of heights such that the maximum height in the matrix is maximized.

Return an integer matrix height of size m x n where height[i][j] is cell (i, j)'s height. If there are multiple solutions, return any of them.

Input & Output

Example 1 — Basic Island
$ Input: isWater = [[0,1],[0,0]]
Output: [[1,0],[2,1]]
💡 Note: Water cell at (0,1) has height 0. Adjacent cells get height 1. Cell (1,0) is distance 2 from water, so height 2.
Example 2 — Multiple Water Sources
$ Input: isWater = [[0,0,1],[1,0,0],[0,0,0]]
Output: [[1,1,0],[0,1,1],[1,2,2]]
💡 Note: Two water cells at (0,2) and (1,0). Heights are minimum distance to any water cell.
Example 3 — All Water
$ Input: isWater = [[1,1],[1,1]]
Output: [[0,0],[0,0]]
💡 Note: All cells are water, so all heights are 0.

Constraints

  • m == isWater.length
  • n == isWater[i].length
  • 1 ≤ m, n ≤ 1000
  • isWater[i][j] is 0 or 1
  • There is at least one water cell

Visualization

Tap to expand
Map of Highest Peak: Water-Based Height AssignmentInput: Land & Water01000=Land, 1=WaterBFS from waterProcess: Distance Calculationd=1d=0d=?d=1Distance from waterAssign heightsOutput: Height Matrix1021Heights = distancesEach land cell gets height equal to its minimum distance from any water cellAdjacent cells differ by at most 1 → Maximum possible heights achievedWater (0)Height 1Height 2Height 3+
Understanding the Visualization
1
Input Matrix
0=land, 1=water cells marked
2
Distance Calculation
Each cell gets height = min distance to water
3
Height Matrix
Final heights maximize the maximum value
Key Takeaway
🎯 Key Insight: Multi-source BFS from all water cells simultaneously gives optimal heights in O(mn) time
Asked in
Google 15 Amazon 12 Microsoft 8 Facebook 6
23.4K Views
Medium Frequency
~15 min Avg. Time
892 Likes
Ln 1, Col 1
Smart Actions
💡 Explanation
AI Ready
💡 Suggestion Tab to accept Esc to dismiss
// Output will appear here after running code
Code Editor Closed
Click the red button to reopen