1765. Map of Highest Peak

Problem Description

Given a matrix isWater representing a map with land and water cells, the task is to assign each cell a height based on certain rules. Cells with isWater[i][j] == 0 are land, and cells with isWater[i][j] == 1 are water. Water cells must have a height of 0, while land cells must be assigned a non-negative height. The key requirement is that any pair of adjacent cells must differ in height by at most 1. The goal is to maximize the highest height in the matrix while following the aforementioned conditions. The solution should return a new matrix, height, where height[i][j] represents the height of cell (i, j).

Intuition

The problem is similar to filling a terrain with water and watching the water rise, respecting the rule that water doesn't spill over to neighboring cells if the height difference is greater than 1. A good way to approach this problem is by using Multi-Source Breadth-First Search (BFS), which starts from all the water cells simultaneously since we know their height is 0. We consider each water cell as a source and begin to explore outward to adjacent land cells, increasing the height step by step.

As multiple water sources spread out, the "wavefront" of land cells being assigned heights grows. Each step from a water cell is assigning a height of 1 to adjacent land cells, and as we continue BFS, we move from these land cells to their adjacent cells, incrementing height by 1 each time. This process naturally ensures that land cells near water are lower, and as we move away, the height increases up to the point where the maximum height that follows the rules is achieved.

The key to BFS is to visit each cell only once and assign the correct height the first time it is visited, which avoids the need for recalculation. The BFS process continues until there are no more cells to update, meaning every cell has been assigned a height as per the rule.

Learn more about Breadth-First Search patterns.

Solution Approach

The solution utilizes the Multi-Source Breadth-First Search (BFS) algorithm to iterate through the matrix. Let's walk through the key components and the algorithm's implementation:

1. Initialization: We create a new matrix ans with the same dimensions as isWater, initializing all cells with -1. This will eventually store the final heights of all cells. Then, we declare a queue q to manage the BFS process.

2. Discovering Water Sources: We iterate through isWater, and for each cell that contains water, we set the corresponding cell in ans to 0 (since the height of water cells is always 0) and add the cell coordinates to q.

3. BFS Process: We start the BFS by popping elements from the queue q. For each cell (i, j), we consider its adjacent cells in the four cardinal directions (north, south, east, west) - these are the potential "next steps" in the BFS. To check for valid adjacent cells, we ensure they are within the matrix bounds and that their height has not been set yet (indicated by -1).

4. Updating Heights: If an adjacent cell is a valid next step, we set its height to be one more than the current cell's (i, j) height. This step ensures that the height difference condition is satisfied. Doing this for all water source cells gradually propagates through the matrix.

5. Queueing Next Cells: After updating the height of an adjacent cell, we add the cell coordinates to the queue q. Placing the cell in the queue ensures that its adjacent cells will be visited in subsequent iterations of BFS.

6. Repeating Process: The BFS continues until current passes through the entire matrix, visiting each cell and assigning the correct height. When the queue is empty, every cell has been reached, and their heights satisfy the rules provided.

7. Returning Results: When there are no more cells to update, the BFS is completed, and we return the ans matrix, which now contains the heights of all cells.

By converging from multiple sources and using a queue for BFS, the solution efficiently spreads out to maximize the heights in the matrix. It solely relies on simple iterations and checks, ensuring it meets the problem constraints effectively.

Here is the code snippet that embodies the approach:

1class Solution:
2    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
3        m, n = len(isWater), len(isWater[0])
4        ans = [[-1] * n for _ in range(m)]
5        q = deque()
6        for i, row in enumerate(isWater):
7            for j, v in enumerate(row):
8                if v:
9                    q.append((i, j))
10                    ans[i][j] = 0
11        while q:
12            i, j = q.popleft()
13            for a, b in pairwise((-1, 0, 1, 0, -1)):
14                x, y = i + a, j + b
15                if 0 <= x < m and 0 <= y < n and ans[x][y] == -1:
16                    ans[x][y] = ans[i][j] + 1
17                    q.append((x, y))
18        return ans

Example Walkthrough

Let's consider a small example of the isWater matrix to see how the solution works step by step:

1Given 'isWater' matrix:
2[0, 1]
3[0, 0]

We have a 2x2 matrix where the top right cell represents water (1) and the rest are land (0).

1. Initialization: We initialize the ans matrix with all -1 to represent unset heights.

1'ans' matrix after initialization:
2[-1, -1]
3[-1, -1]

2. Discovering Water Sources: We find that isWater[0][1] is a water source, so we set the corresponding cell in ans to 0 and add this cell to our BFS queue q.

1'ans' matrix after discovering water sources:
2[-1,  0]
3[-1, -1]
4
5Queue 'q' contains:
6[(0, 1)]

3. BFS Process: Dequeue (0, 1) from q and look for adjacent land cells.

4. Updating Heights: We find two adjacent cells to (0, 1) that are [0][0] and [1][1]. They are both valid moves, so we set their heights to 1. Then we enqueue these cells.

1'ans' matrix after the first BFS iteration:
2[ 1,  0]
3[-1, -1]
4
5Queue 'q' contains:
6[(0, 0), (1, 1)]

5. Queueing Next Cells: We remove (0, 0) from the queue. The adjacent land cells [1][0] can be updated to 2. Now we enqueue (1, 0).

1'ans' matrix after updating (0, 0):
2[ 1,  0]
3[ 2, -1]
4
5Queue 'q' contains:
6[(1, 1), (1, 0)]

6. Repeating Process: We dequeue (1, 1). Since it is already at the boundary, there are no new cells to consider.

Then we dequeue (1, 0) and check its adjacents but there are no -1 values in ans meaning all land cells have been reached and heights assigned.

1'ans' matrix after BFS is completed:
2[ 1,  0]
3[ 2,  1]
4
5Queue 'q' is empty.

7. Returning Results: Since the BFS queue is empty, we completed the BFS of all cells, and the ans matrix is returned with heights satisfying the rule that adjacent cells differ by at most 1.

The final ans matrix is:

1[ 1,  0]
2[ 2,  1]

This walkthrough demonstrates how the process of Multi-Source Breadth-First Search works to assign heights to cells while adhering to the provided constraints and maximizing the heights of land cells.

Solution Implementation

Time and Space Complexity

The time complexity of the code is O(m * n), where m is the number of rows and n is the number of columns in the matrix isWater. This is because the algorithm must visit every cell at least once to determine its height in the final output matrix, and in the worst case, each cell is enqueued and dequeued exactly once in the BFS process.

The space complexity of the code is also O(m * n) because it requires a queue to store at least one entire level of the grid's cells, and each cell is stored once. Also, the ans matrix of size m * n is maintained to store the heights of each cell in the final output.

Learn more about how to find time and space complexity quickly using problem constraints.