Problem Description

You are given a 2D integer matrix isWater of size m x n that represents a map of land and water cells. In this map:

• isWater[i][j] == 1 means cell (i, j) is water.
• isWater[i][j] == 0 means cell (i, j) is land.

• Each water cell is assigned a height of 0.
• Each land cell's height is the minimum possible, such that the difference in height between any two adjacent cells (up, down, left, right) is at most 1.

• There is at least one water cell.
• Each cell is either land or water (no overlap).
• One valid solution is guaranteed.

Thought Process

At first glance, you might think about assigning heights to each land cell by checking all possible paths to the nearest water cell, but this would be inefficient. The brute-force approach would involve, for each land cell, searching for the closest water cell, which could be very slow for large grids.

However, let's notice an important property: since the height difference between adjacent cells can be at most 1, the optimal way is to assign height 0 to all water cells and then incrementally assign heights to neighboring land cells. This is similar to how we compute the shortest path or distance from multiple sources in a grid.

The problem is a classic "multi-source BFS" (Breadth-First Search), where all water cells are starting points (sources), and we expand outward, assigning heights in increasing order.

Solution Approach

We'll use a BFS (Breadth-First Search) algorithm starting from all water cells at once. Here's the step-by-step approach:

1. Initialize the Output Matrix: Create a height matrix of the same size as isWater, initializing all cells to -1 (unassigned).
2. Enqueue All Water Cells: For every cell where isWater[i][j] == 1, set height[i][j] = 0 and add (i, j) to the BFS queue.
3. BFS Expansion: While the queue is not empty:
   • Pop the front cell (x, y) from the queue.
   • For each of its 4 neighbors (up, down, left, right):
   • If the neighbor is within bounds and height[nx][ny] == -1 (not assigned):
   • Set height[nx][ny] = height[x][y] + 1.
   • Enqueue (nx, ny) for further expansion.
4. Finish: Once all cells have been assigned, return the height matrix.

Example Walkthrough

Let's walk through a sample input:
Input: isWater = [[0,1],[0,0]]
This is a 2x2 grid:

• (0,0): land
• (0,1): water
• (1,0): land
• (1,1): land

1. Initialize height = [[-1,0],[-1,-1]] and queue with (0,1).
2. Pop (0,1), neighbors:
   • (0,0): assign height[0][0] = 1, enqueue (0,0).
   • (1,1): assign height[1][1] = 1, enqueue (1,1).
3. Pop (0,0), neighbor (1,0): assign height[1][0] = 2, enqueue (1,0).
4. Pop (1,1), its neighbors are already assigned or out of bounds.
5. Pop (1,0), all neighbors already assigned.

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

Time and Space Complexity

Brute-force Approach: For each land cell, search for the nearest water cell. This takes O((mn)²) time, where m and n are the grid dimensions.
Optimized BFS Approach:

• Time Complexity: O(mn), since each cell is visited exactly once by BFS.
• Space Complexity: O(mn) for the output matrix and the queue (in the worst case, all cells could be in the queue).

Summary

The problem asks us to assign minimal heights to land cells such that the difference between neighbors is at most 1, starting from water cells at height 0. By recognizing this as a multi-source BFS, we efficiently propagate heights outward from all water cells, guaranteeing correctness and optimality. This approach is both elegant and efficient, leveraging BFS's natural expansion property to solve the problem in linear time.

Code Implementation

from collections import deque

class Solution:
    def highestPeak(self, isWater):
        m, n = len(isWater), len(isWater[0])
        height = [[-1 for _ in range(n)] for _ in range(m)]
        queue = deque()
        for i in range(m):
            for j in range(n):
                if isWater[i][j]:
                    height[i][j] = 0
                    queue.append((i, j))
        dirs = [(-1,0),(1,0),(0,-1),(0,1)]
        while queue:
            x, y = queue.popleft()
            for dx, dy in dirs:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and height[nx][ny] == -1:
                    height[nx][ny] = height[x][y] + 1
                    queue.append((nx, ny))
        return height
      

#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
        int m = isWater.size(), n = isWater[0].size();
        vector<vector<int>> height(m, vector<int>(n, -1));
        queue<pair<int, int>> q;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (isWater[i][j]) {
                    height[i][j] = 0;
                    q.push({i, j});
                }
            }
        }
        int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
        while (!q.empty()) {
            auto [x, y] = q.front(); q.pop();
            for (auto& d : dirs) {
                int nx = x + d[0], ny = y + d[1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && height[nx][ny] == -1) {
                    height[nx][ny] = height[x][y] + 1;
                    q.push({nx, ny});
                }
            }
        }
        return height;
    }
};
      

import java.util.*;

class Solution {
    public int[][] highestPeak(int[][] isWater) {
        int m = isWater.length, n = isWater[0].length;
        int[][] height = new int[m][n];
        for (int[] row : height) Arrays.fill(row, -1);
        Queue<int[]> q = new LinkedList<>();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (isWater[i][j] == 1) {
                    height[i][j] = 0;
                    q.offer(new int[]{i, j});
                }
            }
        }
        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        while (!q.isEmpty()) {
            int[] cell = q.poll();
            int x = cell[0], y = cell[1];
            for (int[] d : dirs) {
                int nx = x + d[0], ny = y + d[1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && height[nx][ny] == -1) {
                    height[nx][ny] = height[x][y] + 1;
                    q.offer(new int[]{nx, ny});
                }
            }
        }
        return height;
    }
}
      

/**
 * @param {number[][]} isWater
 * @return {number[][]}
 */
var highestPeak = function(isWater) {
    const m = isWater.length, n = isWater[0].length;
    const height = Array.from({length: m}, () => Array(n).fill(-1));
    const queue = [];
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (isWater[i][j] === 1) {
                height[i][j] = 0;
                queue.push([i, j]);
            }
        }
    }
    const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
    let idx = 0;
    while (idx < queue.length) {
        const [x, y] = queue[idx++];
        for (const [dx, dy] of dirs) {
            const nx = x + dx, ny = y + dy;
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && height[nx][ny] === -1) {
                height[nx][ny] = height[x][y] + 1;
                queue.push([nx, ny]);
            }
        }
    }
    return height;
};