Skip to main content
Talentd

Map of Highest Peak - Solution & Explanation

MediumArrayBreadth-First SearchMatrix13 min readAsked at: Amazon, Google, Bloomberg
Practice this problem

Problem Statement

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.

The C solution initializes a queue data structure and begins the BFS from all water cells. Heights are adjusted as the BFS progresses, ensuring all cells maintain the required height difference constraint of at most 1 unit between adjacent cells. The solution handles all edge cases such as different matrix boundaries. The solution uses a single while loop to expand from each cell, ensuring optimal resource usage.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * n), where m and n are dimensions of the matrix, as each cell is dequeued and enqueued at most once.
Space Complexity: O(m * n) for the height matrix and BFS queue.

Try this approach in the editor →

Approach 2: Default Approach

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

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

Time Complexity: O(m * n), where m and n are dimensions of the matrix, as each cell is dequeued and enqueued at most once.
Space Complexity: O(m * n) for the height matrix and BFS queue.

Default Approach—

Detailed Complexity Analysis

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

Video Solution

Map of Highest Peak | Multi-Source BFS | Leetcode 1765 | Graph Concepts & Qns- 48 | codestorywithMIK • codestorywithMIK • 11,889 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Map of Highest Peak with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays