Map of Highest Peak

medium bfs matrix

Problem

Given a grid with 1 = water and 0 = land, assign each cell a height. Water cells must be 0; neighbouring heights differ by at most 1. Maximize the highest peak.

InputisWater = [[0,1],[0,0]]

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

BFS from the one water cell — each step away in 4-connectivity costs 1.

isWater (rows ';' csv 0/1)

from collections import deque
def highest_peak(is_water):
    m, n = len(is_water), len(is_water[0])
    h = [[-1] * n for _ in range(m)]
    q = deque()
    for r in range(m):
        for c in range(n):
            if is_water[r][c] == 1:
                h[r][c] = 0
                q.append((r, c))
    while q:
        r, c = q.popleft()
        for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and h[nr][nc] == -1:
                h[nr][nc] = h[r][c] + 1
                q.append((nr, nc))
    return h

function highestPeak(isWater) {
  const m = isWater.length, n = isWater[0].length;
  const h = Array.from({length: m}, () => new Array(n).fill(-1));
  const q = [];
  for (let r = 0; r < m; r++) for (let c = 0; c < n; c++) if (isWater[r][c] === 1) { h[r][c] = 0; q.push([r, c]); }
  let head = 0;
  while (head < q.length) {
    const [r, c] = q[head++];
    for (const [dr, dc] of [[1,0],[-1,0],[0,1],[0,-1]]) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < m && nc >= 0 && nc < n && h[nr][nc] === -1) { h[nr][nc] = h[r][c] + 1; q.push([nr, nc]); }
    }
  }
  return h;
}

class Solution {
    public int[][] highestPeak(int[][] isWater) {
        int m = isWater.length, n = isWater[0].length;
        int[][] h = new int[m][n]; for (int[] r : h) Arrays.fill(r, -1);
        Deque<int[]> q = new ArrayDeque<>();
        for (int r = 0; r < m; r++) for (int c = 0; c < n; c++) if (isWater[r][c] == 1) { h[r][c] = 0; q.add(new int[]{r, c}); }
        int[][] D = {{1,0},{-1,0},{0,1},{0,-1}};
        while (!q.isEmpty()) {
            int[] x = q.poll();
            for (int[] d : D) {
                int nr = x[0] + d[0], nc = x[1] + d[1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && h[nr][nc] == -1) { h[nr][nc] = h[x[0]][x[1]] + 1; q.add(new int[]{nr, nc}); }
            }
        }
        return h;
    }
}

vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
    int m = isWater.size(), n = isWater[0].size();
    vector<vector<int>> h(m, vector<int>(n, -1));
    queue<pair<int,int>> q;
    for (int r = 0; r < m; r++) for (int c = 0; c < n; c++) if (isWater[r][c] == 1) { h[r][c] = 0; q.push({r, c}); }
    int D[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        for (auto& d : D) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && h[nr][nc] == -1) { h[nr][nc] = h[r][c] + 1; q.push({nr, nc}); }
        }
    }
    return h;
}

Explanation

To make the highest possible peaks while keeping neighbors within 1 of each other, each cell's height should be its distance to the nearest water. Water itself is 0, and every step away can rise by exactly one.

The trick is multi-source BFS. Instead of running BFS from one start, we put all water cells into the queue at distance 0 at the same time. BFS then expands them in lockstep, so each land cell is reached first by its closest water source.

We keep a height grid h filled with -1 (unvisited). When we pop a cell and look at a neighbor with h == -1, we set h[neighbor] = h[current] + 1 and enqueue it. Because BFS visits in increasing distance order, that first value is the correct shortest distance.

This guarantees neighboring heights never differ by more than 1, since each cell is exactly one more than the cell that reached it.

Example: isWater = [[0,1],[0,0]]. The single water cell at (0,1) is 0; its neighbors become 1, and the far corner becomes 2, giving [[1,0],[2,1]].

Time: O(m·n) Space: O(m·n)