Map of Highest Peak — Medium Problem & Solution

isWater[i][j] == 1 marks a water cell and 0 a land cell. Assign every cell a height so that: every water cell has height 0, the heights of two cells sharing…

Difficulty: Medium
Topics: Arrays, Matrix, Breadth-First Search
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

isWater[i][j] == 1 marks a water cell and 0 a land cell. Assign every cell a height so that:

every water cell has height 0,
the heights of two cells sharing an edge differ by at most 1,
the maximum height in the grid is as large as possible.

Exactly one assignment satisfies all three, so return that height matrix.

Example 1

Input: isWater = [[0,1],[0,0]]
Output: [[1,0],[2,1]]
Explanation: The one water cell is the only source.

Example 2

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

Example 3

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

Constraints

m == isWater.length
n == isWater[i].length
1 <= m, n <= 1000
isWater[i][j] is 0 or 1
At least one water cell is present.

How to solve Map of Highest Peak

The answer is the grid of distances to the nearest water cell, measured in edge steps. A multi-source BFS computes all of them in one sweep.

Approach

Put every water cell in the queue with height 0.
Pop a cell and give each unvisited neighbour its height plus one.
Continue until the queue empties; every cell has been assigned.

Why it works

Walking from a cell to the nearest water cell, the heights may drop by at most 1 per step and must reach 0, so the height is bounded by that distance. The distance grid itself satisfies both rules — neighbours' distances differ by at most one — so it is feasible, and it attains the bound at every cell simultaneously. That makes the maximum as large as possible and the answer unique.

Complexity

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

Pitfalls

Seeding the BFS with one water cell is wrong; all of them start at level 0.
Mark a cell as visited when it is enqueued, not when it is popped, or cells are queued repeatedly.
Depth-first search does not give shortest distances here.

Reference solution

Python

from typing import List
from collections import deque

def highestPeak(isWater: List[List[int]]) -> List[List[int]]:
    m, n = len(isWater), len(isWater[0])
    h = [[-1] * n for _ in range(m)]
    q = deque()
    for i in range(m):
        for j in range(n):
            if isWater[i][j] == 1:
                h[i][j] = 0
                q.append((i, j))
    while q:
        r, c = q.popleft()
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < m and 0 <= nc < n and h[nr][nc] < 0:
                h[nr][nc] = h[r][c] + 1
                q.append((nr, nc))
    return h

JavaScript

var highestPeak = function(isWater) {
    var m = isWater.length, n = isWater[0].length, i, j;
    var h = [];
    for (i = 0; i < m; i++) {
        var row = [];
        for (j = 0; j < n; j++) row.push(-1);
        h.push(row);
    }
    var q = [];
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++) {
            if (isWater[i][j] === 1) { h[i][j] = 0; q.push(i * n + j); }
        }
    }
    var dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
    var head = 0;
    while (head < q.length) {
        var cur = q[head++];
        var r = Math.floor(cur / n), c = cur % n;
        for (var d = 0; d < 4; d++) {
            var nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n || h[nr][nc] >= 0) continue;
            h[nr][nc] = h[r][c] + 1;
            q.push(nr * n + nc);
        }
    }
    return h;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue