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/
This approach uses a multi-source BFS starting from all water cells. We initialize the height of all water cells to 0 and enqueue them. For each dequeued cell, we assign heights to unvisited adjacent cells by increasing the height by 1, and continue the BFS until all cells are visited. This ensures that adjacent height differences are at most 1.
The C solution initializes a queue data structure and begins the BFS from all water cells. Heights are adjusted as the BFS progresses, ensuring all cells maintain the required height difference constraint of at most 1 unit between adjacent cells. The solution handles all edge cases such as different matrix boundaries. The solution uses a single while loop to expand from each cell, ensuring optimal resource usage.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m * n), where m and n are dimensions of the matrix, as each cell is dequeued and enqueued at most once.
Space Complexity: O(m * n) for the height matrix and BFS queue.
Find Peak Element - Leetcode 162 - Python • NeetCodeIO • 63,861 views views
Watch 9 more video solutions →Practice Map of Highest Peak with our built-in code editor and test cases.
Practice on FleetCode