Watch 10 video solutions for Map of Highest Peak, a medium level problem involving Array, Breadth-First Search, Matrix. This walkthrough by codestorywithMIK has 10,558 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer matrix isWater of size m x n that represents a map of land and water cells.
isWater[i][j] == 0, cell (i, j) is a land cell.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:
0.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.lengthn == isWater[i].length1 <= m, n <= 1000isWater[i][j] is 0 or 1.
Note: This question is the same as 542: https://leetcode.com/problems/01-matrix/
Problem Overview: You receive a grid where 1 represents water and 0 represents land. Water cells must have height 0. Assign heights to land so adjacent cells differ by at most 1, while maximizing the overall peak height in the grid.
Approach 1: Brute Force BFS from Each Land Cell (O((m*n)^2) time, O(m*n) space)
A direct idea is to compute the distance from every land cell to the nearest water cell. For each land cell, run a BFS over the matrix until you encounter water. The distance to the closest water cell becomes the height of that land cell. This works because the maximum valid height is exactly the shortest distance to water under the "adjacent difference ≤ 1" constraint. However, running BFS for every cell leads to repeated exploration of the same grid regions, resulting in O((m*n)^2) time complexity. This approach demonstrates the core insight (distance from water) but is inefficient for large grids.
Approach 2: Multi-source Breadth-First Search (BFS) (O(m*n) time, O(m*n) space)
The key observation: a cell's height equals its shortest distance to any water cell. Instead of running BFS from every land cell, start BFS simultaneously from all water cells. Initialize a queue with every water position and assign them height 0. Then expand outward layer by layer using Breadth-First Search. Each time you visit an unassigned neighbor, set its height to the current cell's height plus one and push it into the queue.
This multi-source BFS naturally computes the shortest distance from water for every cell. BFS guarantees the first time you reach a cell is through the shortest path, so the assigned height is optimal. You traverse each cell at most once, giving O(m*n) time. The queue and height grid require O(m*n) space. The approach works well because grid movement forms an unweighted graph where BFS directly produces minimum distances.
The implementation uses a queue, four-direction traversal, and a result grid initialized to -1 for unvisited cells. Water cells start in the queue with height 0. As BFS expands, neighboring cells receive increasing heights that represent their distance from water. This pattern frequently appears in array grid problems involving distance propagation or wave expansion.
Recommended for interviews: Multi-source BFS is the expected solution. Interviewers want to see recognition that the height equals the shortest distance to water and that BFS can compute distances from multiple sources simultaneously. Mentioning the brute-force per-cell BFS first shows understanding of the distance relationship, while transitioning to multi-source BFS demonstrates optimization skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| BFS from Each Land Cell | O((m*n)^2) | O(m*n) | Conceptual starting point to understand that height equals distance to nearest water |
| Multi-source BFS | O(m*n) | O(m*n) | Optimal solution for computing minimum distance from multiple sources in a grid |