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.
Examples
Example 1:
$$ \begin{array}{|c|c|} \hline \colorbox{green}0 & \colorbox{blue}1 \\ \hline \colorbox{green}0 & \colorbox{green}0 \\ \hline \end{array} \longrightarrow \begin{array}{|c|c|} \hline \colorbox{green}1 & \colorbox{blue}0 \\ \hline \colorbox{green}2 & \colorbox{green}1 \\ \hline \end{array} $$
Input: isWater = [[0,1],[0,0]]
Output: [[1,0],[2,1]]
Explanation: The image shows the assigned heights of each cell.
The blue cell is the water cell, and the green cells are the land cells.
Example 2:
$$ \begin{array}{|c|c|c|} \hline \colorbox{green}0 & \colorbox{green}0 & \colorbox{blue}1 \\ \hline \colorbox{blue}1 & \colorbox{green}0 & \colorbox{green}0 \\ \hline \colorbox{green}0 & \colorbox{green}0 & \colorbox{green}0 \\ \hline \end{array} \longrightarrow \begin{array}{|c|c|c|} \hline \colorbox{green}1 & \colorbox{green}1 & \colorbox{blue}0 \\ \hline \colorbox{blue}0 & \colorbox{green}1 & \colorbox{green}1 \\ \hline \colorbox{green}1 & \colorbox{green}2 & \colorbox{green}2 \\ \hline \end{array} $$
Input: isWater = [[0,0,1],[1,0,0],[0,0,0]]
Output: [[1,1,0],[0,1,1],[1,2,2]]
Explanation: A height of 2 is the maximum possible height of any assignment.
Any height assignment that has a maximum height of 2 while still meeting the rules will also be accepted.
Constraints:
m == isWater.length
n == isWater[i].length
1 <= m, n <= 1000
isWater[i][j]
is0
or1
.- There is at least one water cell.
Solution
Method 1 - Using BFS
Here is the approach:
- Initial Setup: First, we’ll create an output matrix
height
with the same dimensions asisWater
, initializing all cells to -1 (indicating unvisited). - Queue Initialization: We’ll use a queue to perform a multi-source Breadth-First Search (BFS). We start by adding all water cells (cells with value 1) to the queue and setting their heights to 0.
- Breadth-First Search (BFS): We’ll process each cell in the queue, and for each cell, we check its four adjacent cells (north, east, south, and west). If an adjacent cell can be assigned a height (i.e., it hasn’t been visited yet), we set its height to the current cell’s height plus one and add this new cell to the queue.
- Termination: The BFS naturally terminates when all reachable locations are processed.
Video explanation
Here is the video explaining this method in detail. Please check it out:
Code
Java
class Solution {
public int[][] highestPeak(int[][] isWater) {
int m = isWater.length;
int n = isWater[0].length;
int[][] ans = new int[m][n];
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (isWater[i][j] == 1) {
ans[i][j] = 0;
queue.offer(new int[]{i, j});
} else {
ans[i][j] = -1;
}
}
}
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int i = cell[0];
int j = cell[1];
for (int[] dir : dirs) {
int ni = i + dir[0];
int nj = j + dir[1];
if (ni >= 0 && ni < m && nj >= 0 && nj < n && ans[ni][nj] == -1) {
ans[ni][nj] = ans[i][j] + 1;
queue.offer(new int[]{ni, nj});
}
}
}
return ans;
}
}
Python
class Solution:
def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
m, n = len(isWater), len(isWater[0])
ans: List[List[int]] = [[-1] * n for _ in range(m)]
queue: deque[Tuple[int, int]] = deque()
# Enqueue all water cells
for i in range(m):
for j in range(n):
if isWater[i][j] == 1:
ans[i][j] = 0
queue.append((i, j))
# Directions list for north, east, south, west
dirs: List[Tuple[int, int]] = [(-1, 0), (1, 0), (0, -1), (0, 1)]
# BFS
while queue:
i, j = queue.popleft()
for di, dj in dirs:
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n and ans[ni][nj] == -1:
ans[ni][nj] = ans[i][j] + 1
queue.append((ni, nj))
return ans
Complexity
- ⏰ Time complexity:
O(m * n)
- 🧺 Space complexity:
O(m * n)