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.

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
💪
Level Up Your
Algo Skills

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]
  1. 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)]
  1. BFS Process: Dequeue (0, 1) from q and look for adjacent land cells.

  2. 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)]
  1. 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)]
  1. 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.
  1. 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.

Python Solution

1from collections import deque
2
3class Solution:
4    def highestPeak(self, is_water: List[List[int]]) -> List[List[int]]:
5        # Retrive the number of rows (m) and columns (n)
6        num_rows, num_cols = len(is_water), len(is_water[0])
7      
8        # Initialize answer grid with -1s indicating unvisited cells
9        answer_grid = [[-1] * num_cols for _ in range(num_rows)]
10        # Queue to hold the cells to visit in Breadth-First Search (BFS)
11        queue = deque()
12      
13        # Populate the queue with water cells and set their height to 0 in answer_grid
14        for row_index, row in enumerate(is_water):
15            for col_index, value in enumerate(row):
16                if value:
17                    queue.append((row_index, col_index))
18                    answer_grid[row_index][col_index] = 0
19      
20        # Directons for exploring neighboring cells (up, right, down, left)
21        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
22      
23        # Perform BFS to populate the answer grid
24        while queue:
25            # Dequeue the first cell
26            current_row, current_col = queue.popleft()
27          
28            # Explore all neighboring cells
29            for delta_row, delta_col in directions:
30                # Calculate neighbor coordinates
31                neighbor_row, neighbor_col = current_row + delta_row, current_col + delta_col
32                # Check if neighbor is within the grid and is unvisited
33                if (0 <= neighbor_row < num_rows and
34                        0 <= neighbor_col < num_cols and
35                        answer_grid[neighbor_row][neighbor_col] == -1):
36                    # Update the height of the neighbor cell
37                    answer_grid[neighbor_row][neighbor_col] = answer_grid[current_row][current_col] + 1
38                    # Enqueue the neighbor cell for visiting
39                    queue.append((neighbor_row, neighbor_col))
40      
41        # Return the populated answer grid
42        return answer_grid
43

Java Solution

1class Solution {
2    public int[][] highestPeak(int[][] isWater) {
3        // Obtain dimensions of the input matrix.
4        int rows = isWater.length;
5        int cols = isWater[0].length;
6      
7        // Initialize the answer matrix with the same dimensions.
8        int[][] highestPeaks = new int[rows][cols];
9      
10        // Queue for BFS (Breadth-first search).
11        Deque<int[]> queue = new ArrayDeque<>();
12      
13        // Initialize answer matrix and enqueue all water cells.
14        for (int i = 0; i < rows; ++i) {
15            for (int j = 0; j < cols; ++j) {
16                // Mark water cells with 0 and land cells with -1
17                highestPeaks[i][j] = isWater[i][j] - 1;
18              
19                // Add water cell coordinates to the queue.
20                if (highestPeaks[i][j] == 0) {
21                    queue.offer(new int[] {i, j});
22                }
23            }
24        }
25      
26        // Directions for exploring adjacent cells (up, right, down, left).
27        int[] directions = {-1, 0, 1, 0, -1};
28      
29        // Perform BFS to find the highest peak values.
30        while (!queue.isEmpty()) {
31            // Poll a cell from the queue.
32            int[] position = queue.poll();
33            int row = position[0];
34            int col = position[1];
35          
36            // Explore all adjacent cells.
37            for (int k = 0; k < 4; ++k) {
38                // Calculate coordinates of the adjacent cell.
39                int x = row + directions[k];
40                int y = col + directions[k + 1];
41              
42                // Check if the adjacent cell is within bounds and if it is land.
43                if (x >= 0 && x < rows && y >= 0 && y < cols && highestPeaks[x][y] == -1) {
44                    // Set the height of the land cell to be one more than the current cell.
45                    highestPeaks[x][y] = highestPeaks[row][col] + 1;
46                  
47                    // Enqueue the position of the land cell.
48                    queue.offer(new int[] {x, y});
49                }
50            }
51        }
52      
53        // Return the filled highestPeaks matrix.
54        return highestPeaks;
55    }
56}
57

C++ Solution

1#include <vector>
2#include <queue>
3using namespace std;
4
5class Solution {
6public:
7    // Define directions for exploring adjacent cells: up, right, down, left.
8    const vector<int> dirs{-1, 0, 1, 0, -1};
9
10    // Function to calculate the highest peak elevation for each cell.
11    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
12        int m = isWater.size();      // Number of rows.
13        int n = isWater[0].size();   // Number of columns.
14        vector<vector<int>> ans(m, vector<int>(n));
15        queue<pair<int, int>> q;     // Queue to perform a breadth-first search.
16      
17        // Initialize the answer matrix and enqueue all water cells.
18        for (int i = 0; i < m; ++i) {
19            for (int j = 0; j < n; ++j) {
20                ans[i][j] = isWater[i][j] - 1; // Water cells become 0, land cells -1.
21                if (ans[i][j] == 0) {
22                    // If the cell is water, add it to the queue for BFS.
23                    q.emplace(i, j);
24                }
25            }
26        }
27      
28        // Perform breadth-first search to determine elevation of each cell.
29        while (!q.empty()) {
30            auto [i, j] = q.front(); // Get the front cell from the queue.
31            q.pop();
32            for (int k = 0; k < 4; ++k) { // Explore all 4 adjacent cells.
33                int x = i + dirs[k];    // Calculate the new x-coordinate.
34                int y = j + dirs[k + 1];// Calculate the new y-coordinate.
35                // Check if the new coordinates are in bounds and the cell is not yet visited.
36                if (x >= 0 && x < m && y >= 0 && y < n && ans[x][y] == -1) {
37                    // Set the elevation of the cell to be one more than current cell's elevation.
38                    ans[x][y] = ans[i][j] + 1;
39                    // Add this cell to the queue to continue BFS from here.
40                    q.emplace(x, y);
41                }
42            }
43        }
44        return ans; // Return the elevation matrix.
45    }
46};
47

Typescript Solution

1function highestPeak(isWater: number[][]): number[][] {
2    const rows = isWater.length;    // Number of rows
3    const cols = isWater[0].length; // Number of columns
4    let answer: number[][] = [];    // Matrix to store the final height map
5    let queue: number[][] = [];     // Queue to perform Breadth-First Search (BFS)
6
7    // Initialize the answer matrix with -1 and queue with the water cells (0 elevation)
8    for (let i = 0; i < rows; i++) {
9        answer.push(new Array(cols).fill(-1));
10        for (let j = 0; j < cols; j++) {
11            if (isWater[i][j] === 1) {
12                queue.push([i, j]);
13                answer[i][j] = 0;
14            }
15        }
16    }
17
18    // Directions for exploring the neighbors of a cell (up, right, down, left)
19    const directions = [-1, 0, 1, 0, -1];
20
21    // Perform BFS to populate the answer matrix with height/elevation levels
22    while (queue.length) {
23        let tempQueue: number[][] = [];
24        for (const [currentRow, currentCol] of queue) {
25            for (let k = 0; k < 4; k++) { // Explore the 4 neighbors of the current cell
26                const newRow = currentRow + directions[k];
27                const newCol = currentCol + directions[k + 1];
28                // If the new cell is within bounds and not yet visited (elevation -1)
29                if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && answer[newRow][newCol] === -1) {
30                    tempQueue.push([newRow, newCol]);
31                    answer[newRow][newCol] = answer[currentRow][currentCol] + 1;
32                }
33            }
34        }
35        queue = tempQueue; // Update the queue with the next level of cells to be visited
36    }
37
38    return answer; // Return the populated height map
39}
40

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.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫