Scale Engineer

Map of Highest Peak

Med
#1616Time: O((m*n)^2). For each of the `O(m*n)` cells, we might perform a BFS that, in the worst case, visits all `O(m*n)` cells.Space: O(m*n). The space is dominated by the `visited` matrix and the queue used within each BFS call. The `height` matrix also takes O(m*n) space.
Algorithms
Breadth-First Search
Data structures
ArrayMatrix

Prompt

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.

 

Example 1:

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:

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.

 

Note: This question is the same as 542: https://leetcode.com/problems/01-matrix/

Approaches

3 approaches with complexity analysis and trade-offs.

This approach iterates through every single cell in the grid. If a cell is a land cell, we perform a Breadth-First Search (BFS) starting from that cell to find the shortest distance to any water cell. The height of the land cell is then set to this shortest distance. This is a straightforward but highly inefficient method.

Algorithm

  • Initialize an m x n result matrix height.
  • Iterate through each cell (i, j) of the isWater matrix.
  • If isWater[i][j] == 1, height[i][j] is already 0 (due to default initialization).
  • If isWater[i][j] == 0, perform a separate BFS starting from (i, j):
    • Create a queue and a visited matrix for this specific BFS.
    • Add (i, j) to the queue with distance 0.
    • While the queue is not empty, dequeue a cell.
    • If the dequeued cell is a water cell, its distance from (i, j) is the shortest distance. Set height[i][j] to this distance and terminate the current BFS.
    • Otherwise, enqueue its unvisited neighbors with an incremented distance.
  • Return the height matrix.

Walkthrough

The core idea is to treat the problem as finding the shortest path from each land cell to the nearest water cell. The length of this path will be the height of the land cell.

  • We initialize a height matrix of the same dimensions as isWater.
  • We iterate through each cell (r, c) from (0, 0) to (m-1, n-1).
  • If isWater[r][c] is 1 (water), we set height[r][c] = 0.
  • If isWater[r][c] is 0 (land), we need to find its height. We do this by starting a BFS from (r, c).
    • A queue is used for the BFS, and we also need a visited matrix for the current BFS search to avoid cycles.
    • We start the BFS by adding (r, c) to the queue with a distance of 0.
    • In each step of the BFS, we dequeue a cell. If it's a water cell, we've found the shortest path. The distance to this water cell is the height for our starting land cell (r, c). We then stop this particular BFS.
    • If the dequeued cell is not a water cell, we add all its unvisited neighbors to the queue with an incremented distance.
  • This process is repeated for all land cells.
import java.util.LinkedList;import java.util.Queue; class Solution {    public int[][] highestPeak(int[][] isWater) {        int m = isWater.length;        int n = isWater[0].length;        int[][] height = new int[m][n];        int[] dr = {-1, 1, 0, 0};        int[] dc = {0, 0, -1, 1};         for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                if (isWater[i][j] == 0) {                    // For each land cell, find the shortest distance to a water cell                    height[i][j] = findShortestDistanceToWater(i, j, m, n, isWater, dr, dc);                }                // Water cells have height 0, which is the default for a new int array            }        }        return height;    }     private int findShortestDistanceToWater(int r, int c, int m, int n, int[][] isWater, int[] dr, int[] dc) {        Queue<int[]> queue = new LinkedList<>();        queue.offer(new int[]{r, c, 0}); // {row, col, distance}        boolean[][] visited = new boolean[m][n];        visited[r][c] = true;         while (!queue.isEmpty()) {            int[] current = queue.poll();            int currR = current[0];            int currC = current[1];            int dist = current[2];             // Check if the current cell is a water cell            if (isWater[currR][currC] == 1) {                return dist;            }             for (int i = 0; i < 4; i++) {                int newR = currR + dr[i];                int newC = currC + dc[i];                 if (newR >= 0 && newR < m && newC >= 0 && newC < n && !visited[newR][newC]) {                    visited[newR][newC] = true;                    queue.offer(new int[]{newR, newC, dist + 1});                }            }        }        return -1; // Should not be reached given problem constraints    }}

Complexity

Time

O((m*n)^2). For each of the `O(m*n)` cells, we might perform a BFS that, in the worst case, visits all `O(m*n)` cells.

Space

O(m*n). The space is dominated by the `visited` matrix and the queue used within each BFS call. The `height` matrix also takes O(m*n) space.

Trade-offs

Pros

  • Conceptually simple and directly models the definition of the height as the shortest distance from a land cell to a water cell.

Cons

  • Extremely inefficient due to a massive amount of redundant computation. The BFS from each land cell re-explores many of the same cells over and over.

  • Guaranteed to result in a "Time Limit Exceeded" error on any reasonably sized input grid.

Solutions

class Solution {public  int[][] highestPeak(int[][] isWater) {    int m = isWater.length, n = isWater[0].length;    int[][] ans = new int[m][n];    Deque<int[]> q = new ArrayDeque<>();    for (int i = 0; i < m; ++i) {      for (int j = 0; j < n; ++j) {        ans[i][j] = isWater[i][j] - 1;        if (ans[i][j] == 0) {          q.offer(new int[]{i, j});        }      }    }    int[] dirs = {-1, 0, 1, 0, -1};    while (!q.isEmpty()) {      var p = q.poll();      int i = p[0], j = p[1];      for (int k = 0; k < 4; ++k) {        int x = i + dirs[k], y = j + dirs[k + 1];        if (x >= 0 && x < m && y >= 0 && y < n && ans[x][y] == -1) {          ans[x][y] = ans[i][j] + 1;          q.offer(new int[]{x, y});        }      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem