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.
- 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.lengthn == isWater[i].length1 <= m, n <= 1000isWater[i][j] is 0 or 1At least one water cell is present.
Hints for Map of Highest Peak
Hint 1
The second rule means a cell's height is at most one more than any neighbour's.
Hint 2
So a cell's height can never exceed its distance to the nearest water cell.
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
- 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 hJava
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