Assign each water cell height 0 and fill every land cell with the minimum possible height so that neighboring cells differ by at most 1.
You are given an binary matrix isWater, where isWater[i][j] = 1 means the cell is water and 0 means the cell is land.
Build a height map such that:
- Every water cell has height
0. - Every land cell has a non-negative integer height.
- For any two cells that share an edge, their heights differ by at most
1. - Among all valid height maps, the resulting map should make every land cell as low as possible.
Return any valid height map that satisfies these conditions.
The goal is to propagate heights outward from all water cells simultaneously so each cell gets its distance-like minimum height from water.
Input Format
isWater: a binary matrix of size .1represents water and0represents land.
Output Format
- Return an matrix of integers representing the heights of all cells.
Constraints
- The grid contains at least one water cell.
- Heights must be non-negative integers.
- Adjacent cells (up, down, left, right) must differ by at most
1.
Example 1
Input
isWater = [[0,1],[0,0]]
Output
[[1,0],[2,1]]
Explanation
The water cell is at height 0. Its neighbors get height 1, and the remaining land cell gets the smallest possible height that keeps adjacent differences at most 1.
Example 2
Input
isWater = [[1,0,0],[0,0,0]]
Output
[[0,1,2],[1,2,3]]
Explanation
Heights increase by 1 as you move farther from the water source.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.