1765. Map of Highest Peak - Solution & Code

Q: Is Map of Highest Peak easy or hard?

Map of Highest Peak is classified as a Medium problem. The challenge lies in recognizing that the height equals the shortest distance to water and that multi-source BFS computes this efficiently. Once the BFS pattern is identified, the implementation is straightforward.

Q: Map of Highest Peak Python/Java solution

Implement multi-source BFS using a queue. Push all water cells into the queue with height 0, then expand in four directions. When visiting an unassigned neighbor, set its height to the current height plus one and enqueue it. The same logic works in Python, Java, C++, C#, and JavaScript.

Q: How to solve Map of Highest Peak in O(n)?

Treat the grid as an unweighted graph and run multi-source BFS starting from all water cells. Initialize their heights to 0 and push them into a queue. For every BFS expansion, assign neighbor height = current height + 1 if it hasn't been visited. Each cell is processed once, resulting in O(m*n) time.

Q: What is the best approach for Map of Highest Peak?

Multi-source Breadth-First Search (BFS) is the optimal approach. Start BFS from all water cells simultaneously and expand outward to assign heights to land cells. Each cell's height equals its shortest distance to any water cell. This guarantees correctness in O(m*n) time.

Q: Is Map of Highest Peak asked at Google/Amazon/Meta?

Grid BFS and shortest-distance matrix problems frequently appear in interviews at companies like Google, Amazon, and Meta. While the exact problem may vary, the multi-source BFS pattern used in Map of Highest Peak is a common interview technique.

Q: What data structure is used in Map of Highest Peak?

The core data structure is a queue used for Breadth-First Search. The algorithm also uses a 2D array (matrix) to store the assigned heights and track visited cells. BFS ensures distances from water cells propagate outward correctly.

Q: What is the time complexity of Map of Highest Peak?

The optimal multi-source BFS solution runs in O(m*n) time where m and n are the grid dimensions. Each cell is inserted into the queue at most once and each edge is processed a constant number of times. The space complexity is also O(m*n) for the queue and height matrix.

The problem

You are given an integer matrix isWater of size m x n that represents a map of land and water cells.

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

You must assign each cell a height in a way that follows these rules:

The height of each cell must be non-negative.
If the cell is a water cell, its height must be 0.
Any two adjacent cells must have an absolute height difference of at most 1. A cell is adjacent to another cell if the former is directly north, east, south, or west of the latter (i.e., their sides are touching).

Find an assignment of heights such that the maximum height in the matrix is maximized.

Return an integer matrix height of size m x n where height[i][j] is cell (i, j)'s height. If there are multiple solutions, return any of them.

Example 1:

Input: isWater = [[0,1],[0,0]]
Output: [[1,0],[2,1]]
Explanation: The image shows the assigned heights of each cell.
The blue cell is the water cell, and the green cells are the land cells.

Example 2:

Input: isWater = [[0,0,1],[1,0,0],[0,0,0]]
Output: [[1,1,0],[0,1,1],[1,2,2]]
Explanation: A height of 2 is the maximum possible height of any assignment.
Any height assignment that has a maximum height of 2 while still meeting the rules will also be accepted.

Constraints:

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

Note: This question is the same as 542: https://leetcode.com/problems/01-matrix/

Approach overview

Problem Overview: You receive a grid where 1 represents water and 0 represents land. Water cells must have height 0. Assign heights to land so adjacent cells differ by at most 1, while maximizing the overall peak height in the grid.

Approach 1: Brute Force BFS from Each Land Cell (O((m*n)^2) time, O(m*n) space)

A direct idea is to compute the distance from every land cell to the nearest water cell. For each land cell, run a BFS over the matrix until you encounter water. The distance to the closest water cell becomes the height of that land cell. This works because the maximum valid height is exactly the shortest distance to water under the "adjacent difference ≤ 1" constraint. However, running BFS for every cell leads to repeated exploration of the same grid regions, resulting in O((m*n)^2) time complexity. This approach demonstrates the core insight (distance from water) but is inefficient for large grids.

Approach 2: Multi-source Breadth-First Search (BFS) (O(m*n) time, O(m*n) space)

The key observation: a cell's height equals its shortest distance to any water cell. Instead of running BFS from every land cell, start BFS simultaneously from all water cells. Initialize a queue with every water position and assign them height 0. Then expand outward layer by layer using Breadth-First Search. Each time you visit an unassigned neighbor, set its height to the current cell's height plus one and push it into the queue.

This multi-source BFS naturally computes the shortest distance from water for every cell. BFS guarantees the first time you reach a cell is through the shortest path, so the assigned height is optimal. You traverse each cell at most once, giving O(m*n) time. The queue and height grid require O(m*n) space. The approach works well because grid movement forms an unweighted graph where BFS directly produces minimum distances.

The implementation uses a queue, four-direction traversal, and a result grid initialized to -1 for unvisited cells. Water cells start in the queue with height 0. As BFS expands, neighboring cells receive increasing heights that represent their distance from water. This pattern frequently appears in array grid problems involving distance propagation or wave expansion.

Recommended for interviews: Multi-source BFS is the expected solution. Interviewers want to see recognition that the height equals the shortest distance to water and that BFS can compute distances from multiple sources simultaneously. Mentioning the brute-force per-cell BFS first shows understanding of the distance relationship, while transitioning to multi-source BFS demonstrates optimization skills.

Approach 1: Approach 1: Multi-source Breadth-First Search (BFS)

This approach uses a multi-source BFS starting from all water cells. We initialize the height of all water cells to 0 and enqueue them. For each dequeued cell, we assign heights to unvisited adjacent cells by increasing the height by 1, and continue the BFS until all cells are visited. This ensures that adjacent height differences are at most 1.

Python

from collections import deque

def highestPeak(isWater):
    m, n = len(isWater), len(isWater[0])
    height = [[-1] * n for _ in range(m)]
    q = deque()
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

    for i in range(m):
        for j in range(n):
            if isWater[i][j] == 1:
                height[i][j] = 0
                q.append((i, j))

    while q:
        x, y = q.popleft()
        for dx, dy in directions:
            newX, newY = x + dx, y + dy
            if 0 <= newX < m and 0 <= newY < n and height[newX][newY] == -1:
                height[newX][newY] = height[x][y] + 1
                q.append((newX, newY))

    return height

Java

import java.util.*;

public 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<>();
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

        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});
                }
            }
        }

        while (!q.isEmpty()) {
            int[] point = q.poll();
            for (int[] dir : directions) {
                int newX = point[0] + dir[0];
                int newY = point[1] + dir[1];
                if (newX >= 0 && newX < m && newY >= 0 && newY < n && height[newX][newY] == -1) {
                    height[newX][newY] = height[point[0]][point[1]] + 1;
                    q.offer(new int[]{newX, newY});
                }
            }
        }
        return height;
    }
}

C++

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

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;
    vector<vector<int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (isWater[i][j] == 1) {
                height[i][j] = 0;
                q.push({i, j});
            }
        }
    }

    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (auto& dir : directions) {
            int newX = x + dir[0], newY = y + dir[1];
            if (newX >= 0 && newX < m && newY >= 0 && newY < n && height[newX][newY] == -1) {
                height[newX][newY] = height[x][y] + 1;
                q.push({newX, newY});
            }
        }
    }
    return height;
}

JavaScript

var highestPeak = function(isWater) {
    const m = isWater.length, n = isWater[0].length;
    const height = Array.from({ length: m }, () => Array(n).fill(-1));
    const q = [];
    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (isWater[i][j] === 1) {
                height[i][j] = 0;
                q.push([i, j]);
            }
        }
    }

    while (q.length > 0) {
        const [x, y] = q.shift();
        for (const [dx, dy] of directions) {
            const newX = x + dx, newY = y + dy;
            if (newX >= 0 && newX < m && newY >= 0 && newY < n && height[newX][newY] === -1) {
                height[newX][newY] = height[x][y] + 1;
                q.push([newX, newY]);
            }
        }
    }

    return height;
};

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX 1000

int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

typedef struct {
    int x, y;
} Point;

int** highestPeak(int** isWater, int isWaterSize, int* isWaterColSize, int* returnSize, int** returnColumnSizes) {
    int m = isWaterSize;
    int n = *isWaterColSize;
    int** height = (int**)malloc(m * sizeof(int*));
    for (int i = 0; i < m; i++) {
        height[i] = (int*)malloc(n * sizeof(int));
        for (int j = 0; j < n; j++) {
            height[i][j] = -1;
        }
    }

    Point queue[MAX * MAX];
    int front = 0, rear = 0;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (isWater[i][j] == 1) {
                height[i][j] = 0;
                queue[rear++] = (Point){i, j};
            }
        }
    }

    while (front < rear) {
        Point curr = queue[front++];
        for (int d = 0; d < 4; d++) {
            int newX = curr.x + directions[d][0];
            int newY = curr.y + directions[d][1];
            if (newX >= 0 && newX < m && newY >= 0 && newY < n && height[newX][newY] == -1) {
                height[newX][newY] = height[curr.x][curr.y] + 1;
                queue[rear++] = (Point){newX, newY};
            }
        }
    }

    *returnSize = m;
    *returnColumnSizes = (int*)malloc(m * sizeof(int));
    for (int i = 0; i < m; i++) {
        (*returnColumnSizes)[i] = n;
    }
    return height;
}

using System;
using System.Collections.Generic;

public class Solution {
    public int[][] HighestPeak(int[][] isWater) {
        int m = isWater.Length, n = isWater[0].Length;
        int[][] height = new int[m][];
        for (int i = 0; i < m; i++) {
            height[i] = new int[n];
            Array.Fill(height[i], -1);
        }
        Queue<(int, int)> q = new Queue<(int, int)>();
        int[][] directions = new int[][] { new int[] { 0, 1 }, new int[] { 1, 0 }, new int[] { 0, -1 }, new int[] { -1, 0 } };

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (isWater[i][j] == 1) {
                    height[i][j] = 0;
                    q.Enqueue((i, j));
                }
            }
        }

        while (q.Count > 0) {
            var (x, y) = q.Dequeue();
            foreach (var dir in directions) {
                int newX = x + dir[0];
                int newY = y + dir[1];
                if (newX >= 0 && newX < m && newY >= 0 && newY < n && height[newX][newY] == -1) {
                    height[newX][newY] = height[x][y] + 1;
                    q.Enqueue((newX, newY));
                }
            }
        }

        return height;
    }
}

The Python solution employs deque from the collections module to efficiently handle the BFS queue operations. Heights are calculated by expanding from all water cells simultaneously, updating unvisited neighbors incrementally. This ensures the BFS property of minimal state expansion, meeting all constraints given in the problem.

Complexity

Time Complexity: O(m * n), with each cell processed once in BFS.
Space Complexity: O(m * n) for the height matrix and queue.

Try this approach in the editor

Approach 2: Default Approach

TypeScript

function highestPeak(isWater: number[][]): number[][] {
    const m = isWater.length;
    const n = isWater[0].length;
    let ans: number[][] = [];
    let q: number[][] = [];
    for (let i = 0; i < m; ++i) {
        ans.push(new Array(n).fill(-1));
        for (let j = 0; j < n; ++j) {
            if (isWater[i][j]) {
                q.push([i, j]);
                ans[i][j] = 0;
            }
        }
    }
    const dirs = [-1, 0, 1, 0, -1];
    while (q.length) {
        let tq: number[][] = [];
        for (const [i, j] of q) {
            for (let k = 0; k < 4; k++) {
                const [x, y] = [i + dirs[k], j + dirs[k + 1]];
                if (x >= 0 && x < m && y >= 0 && y < n && ans[x][y] == -1) {
                    tq.push([x, y]);
                    ans[x][y] = ans[i][j] + 1;
                }
            }
        }
        q = tq;
    }
    return ans;
}

func highestPeak(isWater [][]int) [][]int {
	m, n := len(isWater), len(isWater[0])
	ans := make([][]int, m)
	type pair struct{ i, j int }
	q := []pair{}
	for i, row := range isWater {
		ans[i] = make([]int, n)
		for j, v := range row {
			ans[i][j] = v - 1
			if v == 1 {
				q = append(q, pair{i, j})
			}
		}
	}
	dirs := []int{-1, 0, 1, 0, -1}
	for len(q) > 0 {
		p := q[0]
		q = q[1:]
		i, j := p.i, p.j
		for k := 0; k < 4; k++ {
			x, y := i+dirs[k], j+dirs[k+1]
			if x >= 0 && x < m && y >= 0 && y < n && ans[x][y] == -1 {
				ans[x][y] = ans[i][j] + 1
				q = append(q, pair{x, y})
			}
		}
	}
	return ans
}

Rust

use std::collections::VecDeque;

impl Solution {
    #[allow(dead_code)]
    pub fn highest_peak(is_water: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let n = is_water.len();
        let m = is_water[0].len();
        let mut ret_vec = vec![vec![-1; m]; n];
        let mut q: VecDeque<(usize, usize)> = VecDeque::new();
        let vis_pair: Vec<(i32, i32)> = vec![(-1, 0), (1, 0), (0, -1), (0, 1)];

        // Initialize the return vector
        for i in 0..n {
            for j in 0..m {
                if is_water[i][j] == 1 {
                    // This cell is water, the height of which must be 0
                    ret_vec[i][j] = 0;
                    q.push_back((i, j));
                }
            }
        }

        while !q.is_empty() {
            // Get the front X-Y Coordinates
            let (x, y) = q.front().unwrap().clone();
            q.pop_front();
            // Traverse through the vis pair
            for d in &vis_pair {
                let (dx, dy) = *d;
                if Self::check_bounds((x as i32) + dx, (y as i32) + dy, n as i32, m as i32) {
                    if ret_vec[((x as i32) + dx) as usize][((y as i32) + dy) as usize] == -1 {
                        // This cell hasn't been visited, update its height
                        ret_vec[((x as i32) + dx) as usize][((y as i32) + dy) as usize] =
                            ret_vec[x][y] + 1;
                        // Enqueue the current cell
                        q.push_back((((x as i32) + dx) as usize, ((y as i32) + dy) as usize));
                    }
                }
            }
        }

        ret_vec
    }

    #[allow(dead_code)]
    fn check_bounds(i: i32, j: i32, n: i32, m: i32) -> bool {
        i >= 0 && i < n && j >= 0 && j < m
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Multi-source Breadth-First Search (BFS)	Time Complexity: O(m * n), with each cell processed once in BFS. Space Complexity: O(m * n) for the height matrix and queue.
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
BFS from Each Land Cell	O((m*n)^2)	O(m*n)	Conceptual starting point to understand that height equals distance to nearest water
Multi-source BFS	O(m*n)	O(m*n)	Optimal solution for computing minimum distance from multiple sources in a grid

Frequently asked questions

Is Map of Highest Peak easy or hard?

Map of Highest Peak is classified as a Medium problem. The challenge lies in recognizing that the height equals the shortest distance to water and that multi-source BFS computes this efficiently. Once the BFS pattern is identified, the implementation is straightforward.

Map of Highest Peak Python/Java solution

Implement multi-source BFS using a queue. Push all water cells into the queue with height 0, then expand in four directions. When visiting an unassigned neighbor, set its height to the current height plus one and enqueue it. The same logic works in Python, Java, C++, C#, and JavaScript.

How to solve Map of Highest Peak in O(n)?

Treat the grid as an unweighted graph and run multi-source BFS starting from all water cells. Initialize their heights to 0 and push them into a queue. For every BFS expansion, assign neighbor height = current height + 1 if it hasn't been visited. Each cell is processed once, resulting in O(m*n) time.

What is the best approach for Map of Highest Peak?

Multi-source Breadth-First Search (BFS) is the optimal approach. Start BFS from all water cells simultaneously and expand outward to assign heights to land cells. Each cell's height equals its shortest distance to any water cell. This guarantees correctness in O(m*n) time.

Is Map of Highest Peak asked at Google/Amazon/Meta?

Grid BFS and shortest-distance matrix problems frequently appear in interviews at companies like Google, Amazon, and Meta. While the exact problem may vary, the multi-source BFS pattern used in Map of Highest Peak is a common interview technique.

What data structure is used in Map of Highest Peak?

The core data structure is a queue used for Breadth-First Search. The algorithm also uses a 2D array (matrix) to store the assigned heights and track visited cells. BFS ensures distances from water cells propagate outward correctly.

What is the time complexity of Map of Highest Peak?

The optimal multi-source BFS solution runs in O(m*n) time where m and n are the grid dimensions. Each cell is inserted into the queue at most once and each edge is processed a constant number of times. The space complexity is also O(m*n) for the queue and height matrix.

Map of Highest Peak solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Multi-source Breadth-First Search (BFS)

Approach 2: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Map of Highest Peak solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Multi-source Breadth-First Search (BFS)

Approach 2: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems