Map of Highest Peak

Medium
911.

Map of Highest Peak

Map of Highest Peak is a medium coding problem on arrays, matrix and breadth-first search, asked in Amazon, Google and Microsoft interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} isWater
 * @return {number[][]}
 */
var highestPeak = function(isWater) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Map of Highest Peak — Solution in Python, Java & C++

Map of Highest Peak solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on arrays and matrix.

Map of Highest Peak is a medium coding problem on arrays, matrix and breadth-first search, asked in Amazon, Google and Microsoft interviews.

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.

Hints for Map of Highest Peak

  1. Hint 1

    The second rule means a cell's height is at most one more than any neighbour's.

  2. Hint 2

    So a cell's height can never exceed its distance to the nearest water cell.

  3. Hint 3

    Run a breadth-first search starting from all water cells at once.

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

  1. Put every water cell in the queue with height 0.
  2. Pop a cell and give each unvisited neighbour its height plus one.
  3. 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

Java

public static int[][] highestPeak(int[][] isWater) {
    int m = isWater.length, n = isWater[0].length;
    int[][] h = new int[m][n];
    int[] q = new int[m * n];
    int tail = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (isWater[i][j] == 1) { h[i][j] = 0; q[tail++] = i * n + j; }
            else h[i][j] = -1;
        }
    }
    int[] dr = { 1, -1, 0, 0 };
    int[] dc = { 0, 0, 1, -1 };
    for (int head = 0; head < tail; head++) {
        int r = q[head] / n, c = q[head] % n;
        for (int d = 0; d < 4; d++) {
            int 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[tail++] = nr * n + nc;
        }
    }
    return h;
}

C++

vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
    int m = (int) isWater.size(), n = (int) isWater[0].size();
    vector<vector<int>> h(m, vector<int>(n, -1));
    vector<int> q;
    q.reserve((size_t) (m * n));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (isWater[i][j] == 1) { h[i][j] = 0; q.push_back(i * n + j); }
        }
    }
    int dr[4] = { 1, -1, 0, 0 };
    int dc[4] = { 0, 0, 1, -1 };
    for (size_t head = 0; head < q.size(); head++) {
        int r = q[head] / n, c = q[head] % n;
        for (int d = 0; d < 4; d++) {
            int 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_back(nr * n + 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Matrix and Grid Traversal