#1765

Medium

auto_awesomeArray plus Breadth-First Search

LeetCode Problem Workspace

Map of Highest Peak

Solve the Map of Highest Peak problem using breadth-first search to assign heights based on proximity to water cells.

Problem Statement

You are given a matrix isWater of size m x n where each cell is either a land cell (0) or a water cell (1). Your task is to assign heights to each cell such that each water cell has height 0, and the height of each land cell is the Manhattan distance to the nearest water cell. The heights must satisfy the condition that the maximum height is as large as possible.

For example, in a grid where water cells are represented by 1 and land cells by 0, the goal is to propagate the water heights to adjacent land cells while maintaining the maximum height. The challenge is to ensure that the heights of land cells are only constrained by the nearest water cell, resulting in a valid height assignment across the entire matrix.

Examples

Example 1

Input: isWater = [[0,1],[0,0]]

Output: [[1,0],[2,1]]

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]]

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 Approach

Breadth-First Search (BFS)

To solve this problem, perform a breadth-first search starting from all the water cells simultaneously. Each water cell is initialized with a height of 0, and as BFS expands, it assigns heights to adjacent land cells based on the Manhattan distance to the nearest water cell. This guarantees the correct propagation of heights.

Matrix Traversal

The matrix is traversed in all four directions (up, down, left, right) for each water cell during BFS. For each unvisited land cell, the height is updated based on the nearest water cell. This ensures that the height assignment is optimal and maximized.

Queue Management

The BFS is implemented using a queue, where water cells are enqueued first. As BFS progresses, the queue processes neighboring cells and updates their heights. By maintaining the BFS queue and processing cells layer by layer, we ensure that the minimum possible height is assigned to each land cell.

Complexity Analysis

Metric	Value
Time	O(m \times n)
Space	O(m \times n)

The time complexity is O(m * n) since each cell is visited once during BFS. The space complexity is also O(m * n) due to the storage required for the BFS queue and the matrix.

What Interviewers Usually Probe

Check if the candidate properly utilizes BFS to traverse the matrix and propagate height values from water cells.
Look for a clear explanation of how the BFS approach ensures that the maximum height is achieved.
Verify that the candidate discusses the queue management and how it helps to efficiently process the matrix.

Common Pitfalls or Variants

Common pitfalls

Incorrectly updating the heights of land cells, leading to invalid height propagation.
Not using BFS to propagate the heights from all water cells simultaneously, which may result in suboptimal solutions.
Overcomplicating the solution by using unnecessary algorithms or operations instead of focusing on BFS.

Follow-up variants

Vary the size of the matrix to test the efficiency of the BFS approach.
Introduce more complex terrain with varying water distributions, requiring careful height propagation.
Add constraints such as larger grid sizes or specific height boundaries to test edge cases and algorithm efficiency.

FAQ

How do I apply breadth-first search in the Map of Highest Peak problem?

You start BFS from all water cells, and as you propagate outward, each neighboring land cell gets its height updated based on the Manhattan distance to the nearest water cell.

What is the time complexity of the Map of Highest Peak problem?

The time complexity is O(m * n), where m and n are the number of rows and columns in the matrix, as every cell is processed once during BFS.

What is the significance of the water cells in this problem?

Water cells are initialized with a height of 0, and all land cells' heights are determined by their closest water cell. This constraint is crucial for ensuring the heights are maximized correctly.

How does BFS help in this problem?

BFS allows the height values to propagate from all water cells simultaneously, ensuring that the heights are assigned in the shortest possible distance to each land cell.

What happens if BFS is not used in the Map of Highest Peak problem?

Without BFS, the heights would not propagate correctly, leading to incorrect or suboptimal height assignments. BFS ensures that each land cell gets the minimum height based on proximity to water.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

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

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

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

Continue Practicing

#1631 path with minimum effort #1905 count sub islands #1926 nearest exit from entrance in maze