# Map of Highest Peak
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/map-of-highest-peak)
Canonical: https://scaleengineer.com/dsa/problems/map-of-highest-peak
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array, Matrix
---
## 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_.

**Example 1:**

**![](https://assets.glich.co/dsa/map-of-highest-peak/image0.png)**

**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:**

**![](https://assets.glich.co/dsa/map-of-highest-peak/image1.png)**

**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/](https://leetcode.com/problems/01-matrix/description/)

# Approaches
## Brute Force: BFS from each Land Cell
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.
**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.
**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.
### Explanation
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.

```java
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
    }
}
```
### 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.

## Dynamic Programming
This approach uses dynamic programming to solve the problem efficiently. It calculates the shortest distance from each cell to a water cell in two passes over the grid. The first pass goes from top-left to bottom-right, and the second pass goes from bottom-right to top-left. This ensures that distance information is propagated correctly from all directions.
**Time:** O(m*n). We iterate through the `m x n` grid twice, which is linear in the number of cells. · **Space:** O(m*n). This space is required for the `height` matrix which we must return. If the space for the output is not counted, the space complexity is O(1).
**Pros:** Very efficient with a linear time complexity.; Does not require complex data structures like a queue.; Easy to implement with two nested loops for each pass.
**Cons:** The logic might be less intuitive than the BFS approach, which directly models graph traversal.; Requires two full passes over the grid.
### Explanation
The problem can be rephrased as finding, for each cell, the minimum Manhattan distance to a water cell. Let `height[i][j]` be this distance. The recurrence relation is `height[i][j] = 1 + min(height of neighbors)`. This dependency on all four neighbors makes a single DP pass tricky. We can solve this by splitting the dependencies into two passes.

- **Step 1: Initialization**
    - Create a `height` matrix. Initialize `height[i][j] = 0` if `isWater[i][j] == 1`, and to a very large value for all land cells.

- **Step 2: First Pass (Top-Left to Bottom-Right)**
    - Iterate through the grid from `(0, 0)` to `(m-1, n-1)`. For each cell `(i, j)`, update its height based on the already computed heights of its top and left neighbors: `height[i][j] = min(height[i][j], 1 + min(height[i-1][j], height[i][j-1]))`. After this pass, `height[i][j]` stores the shortest distance to a water cell considering only paths from the top or left.

- **Step 3: Second Pass (Bottom-Right to Top-Left)**
    - Iterate through the grid in reverse, from `(m-1, n-1)` to `(0, 0)`. For each cell `(i, j)`, update its height based on its bottom and right neighbors: `height[i][j] = min(height[i][j], 1 + min(height[i+1][j], height[i][j+1]))`. This pass considers paths from the bottom and right. By taking the minimum with the value from the first pass, we find the true shortest distance.

```java
import java.util.Arrays;

class Solution {
    public int[][] highestPeak(int[][] isWater) {
        int m = isWater.length;
        int n = isWater[0].length;
        int[][] height = new int[m][n];
        int maxPossibleDist = m * n; // A value larger than any possible distance

        // First pass: top-left to bottom-right
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (isWater[i][j] == 1) {
                    height[i][j] = 0;
                } else {
                    height[i][j] = maxPossibleDist;
                    if (i > 0) {
                        height[i][j] = Math.min(height[i][j], height[i - 1][j] + 1);
                    }
                    if (j > 0) {
                        height[i][j] = Math.min(height[i][j], height[i][j - 1] + 1);
                    }
                }
            }
        }

        // Second pass: bottom-right to top-left
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (i < m - 1) {
                    height[i][j] = Math.min(height[i][j], height[i + 1][j] + 1);
                }
                if (j < n - 1) {
                    height[i][j] = Math.min(height[i][j], height[i][j + 1] + 1);
                }
            }
        }

        return height;
    }
}
```
### Algorithm
- Create a result matrix `height` of size `m x n`.
- Initialize `height[i][j]` to 0 for water cells and a very large value for land cells.
- **Pass 1 (Top-Left to Bottom-Right):** Iterate from `i = 0 to m-1` and `j = 0 to n-1`. For each cell `(i, j)`, update `height[i][j]` using `min(height[i][j], height[i-1][j] + 1)` and `min(height[i][j], height[i][j-1] + 1)`.
- **Pass 2 (Bottom-Right to Top-Left):** Iterate from `i = m-1 to 0` and `j = n-1 to 0`. For each cell `(i, j)`, update `height[i][j]` using `min(height[i][j], height[i+1][j] + 1)` and `min(height[i][j], height[i][j+1] + 1)`.
- Return the `height` matrix.

## Multi-Source Breadth-First Search (BFS)
This is the most standard and intuitive approach for finding the shortest distance from multiple sources in an unweighted graph. We can view the grid as a graph where cells are nodes and adjacent cells have edges. The water cells are the "source" nodes. We start a single BFS simultaneously from all water cells to find the shortest distance (height) for all other (land) cells.
**Time:** O(m*n). Each cell is enqueued and dequeued exactly once, and we do constant work for each cell. · **Space:** O(m*n). In the worst case, the queue can hold up to `O(m*n)` cells. The `height` matrix also requires `O(m*n)` space.
**Pros:** Highly efficient, visiting each cell only once.; It's a very natural and intuitive way to model the problem of finding the shortest distance from a set of source nodes.; Guarantees finding the optimal solution.
**Cons:** Requires extra space for the queue, which in the worst case (e.g., a checkerboard pattern of water and land) can be large.
### Explanation
The problem is equivalent to finding the shortest distance from every cell to its nearest water cell. Since all edge weights are 1 (moving between adjacent cells), BFS is the perfect algorithm. Instead of starting a separate BFS from each land cell, we can reverse the thinking: start a single BFS from all water cells at once.

- **Step 1: Initialization**
    - Create a `height` matrix of size `m x n` to store the results. Initialize it with a value indicating that cells have not been visited yet (e.g., -1).
    - Create a queue for the BFS.
    - Iterate through the `isWater` grid. For every water cell `(r, c)`, set `height[r][c] = 0` and add the cell `(r, c)` to the queue. All other cells in `height` remain as -1.

- **Step 2: BFS Traversal**
    - While the queue is not empty, perform the standard BFS procedure.
    - Dequeue a cell `(r, c)`. For each of its four neighbors `(nr, nc)`:
        - Check if the neighbor is valid (within bounds) and unvisited (`height[nr][nc] == -1`).
        - If so, its height will be the height of the current cell plus one: `height[nr][nc] = height[r][c] + 1`.
        - Mark the neighbor as visited by setting its height and enqueue it.

Since BFS explores the grid layer by layer, we are guaranteed that when we first reach a land cell, it will be via the shortest path from a water source.

```java
import java.util.LinkedList;
import java.util.Queue;
import java.util.Arrays;

class Solution {
    public int[][] highestPeak(int[][] isWater) {
        int m = isWater.length;
        int n = isWater[0].length;
        int[][] height = new int[m][n];
        Queue<int[]> queue = new LinkedList<>();

        // Initialize height matrix and queue with water cells
        for (int i = 0; i < m; i++) {
            Arrays.fill(height[i], -1); // -1 indicates unvisited
            for (int j = 0; j < n; j++) {
                if (isWater[i][j] == 1) {
                    height[i][j] = 0;
                    queue.offer(new int[]{i, j});
                }
            }
        }

        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        // Start multi-source BFS
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int r = current[0];
            int c = current[1];

            for (int i = 0; i < 4; i++) {
                int newR = r + dr[i];
                int newC = c + dc[i];

                // Check boundaries and if the cell has been visited
                if (newR >= 0 && newR < m && newC >= 0 && newC < n && height[newR][newC] == -1) {
                    height[newR][newC] = height[r][c] + 1;
                    queue.offer(new int[]{newR, newC});
                }
            }
        }

        return height;
    }
}
```
### Algorithm
- Create a result matrix `height` and initialize all its cells to -1 (or another marker for unvisited).
- Create a queue.
- Iterate through the input `isWater` matrix. If `isWater[i][j] == 1`, set `height[i][j] = 0` and add the coordinates `(i, j)` to the queue.
- While the queue is not empty:
    - Dequeue a cell `(r, c)`.
    - For each of its four neighbors `(nr, nc)`:
        - If the neighbor is within bounds and is unvisited (`height[nr][nc] == -1`):
            - Set its height: `height[nr][nc] = height[r][c] + 1`.
            - Enqueue the neighbor `(nr, nc)`.
- Return the `height` matrix.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  const int dirs[5] = {-1, 0, 1, 0, -1};
  vector<vector<int>> highestPeak(vector<vector<int>> &isWater) {
    int m = isWater.size(), n = isWater[0].size();
    vector<vector<int>> ans(m, vector<int>(n));
    queue<pair<int, int>> q;
    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.emplace(i, j);
        }
      }
    }
    while (!q.empty()) {
      auto [i, j] = q.front();
      q.pop();
      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.emplace(x, y);
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]: m, n = len(isWater), len(isWater[0]) ans = [[- 1] * n for _ in range(m)] q = deque() for i, row in enumerate(isWater): for j, v in enumerate(row): if v: q . append((i, j)) ans[i][j] = 0 while q: i, j = q . popleft() for a, b in pairwise((- 1, 0, 1, 0, - 1)): x, y = i + a, j + b if 0 <= x < m and 0 <= y < n and ans[x][y] == - 1: ans[x][y] = ans[i][j] + 1 q . append((x, y)) return ans

```