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] is 0 or 1.
  • There is at least one water cell.

Solution

Method 1 - Using BFS

Here is the approach:

  1. Initial Setup: First, we’ll create an output matrix height with the same dimensions as isWater, initializing all cells to -1 (indicating unvisited).
  2. 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.
  3. 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.
  4. 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)