LeetCode 1765 - Map of Highest Peak

Difficulty: 🟡 Medium
Topics: Array, Breadth-First Search, Matrix

Solution

Problem Understanding

The problem presents a matrix isWater of size m x n where each cell is either water (1) or land (0). We are asked to assign heights to every cell in a way that satisfies three rules. First, all heights must be non-negative integers. Second, water cells must have a height of 0. Third, the absolute difference in height between any two adjacent cells (north, south, east, or west) must be at most 1. The goal is to assign heights so that the maximum height in the matrix is as large as possible.

Effectively, this is asking us to “grow” heights outward from the water cells, increasing by 1 with each step away from water, while ensuring adjacency constraints are met. Multiple solutions may exist because there can be several ways to propagate heights outward from multiple water sources.

The input constraints tell us the matrix can be as large as 1000x1000, so algorithms with time complexity worse than O(m * n) may be too slow. There is at least one water cell, which guarantees a starting point for any propagation-based approach.

Important edge cases include matrices where water cells are clustered, where the matrix has only one row or one column, and where the water cell is at a corner or the edge.

Approaches

A brute-force approach would involve iteratively increasing the height of land cells based on the adjacent cells until all adjacency constraints are satisfied. For example, one could scan the matrix repeatedly, updating a land cell to min(neighbor heights + 1) until no more changes occur. While this eventually converges to a valid solution, it can take O((m * n)^2) in the worst case for large matrices, which is unacceptable given the constraints.

The key insight for an optimal approach is that the problem is equivalent to a multi-source Breadth-First Search (BFS) starting from all water cells simultaneously. Since each cell’s height can increase by at most 1 per step away from water, BFS ensures that each land cell receives the minimum possible distance from water, which directly translates to its height. BFS naturally propagates the correct height while respecting the adjacency difference constraint.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O((m * n)^2)	O(m * n)	Repeatedly scan matrix until all adjacency constraints are satisfied
Optimal (Multi-source BFS)	O(m * n)	O(m * n)	Start BFS from all water cells, assign height as distance from nearest water

Algorithm Walkthrough

Initialize a matrix height of size m x n with -1 to denote unvisited cells. Water cells will later be set to 0.
Initialize a queue q and add all water cells (i, j) to the queue, simultaneously setting height[i][j] = 0.
While the queue is not empty, remove a cell (i, j) from the front.
For each of the four adjacent directions (north, east, south, west), calculate the neighbor cell (ni, nj).
If the neighbor is within bounds and height[ni][nj] == -1 (not yet assigned), set height[ni][nj] = height[i][j] + 1 and enqueue (ni, nj).
Continue until the queue is empty. At this point, all cells have been assigned heights according to their distance from the nearest water.

Why it works: BFS guarantees that the first time a land cell is visited, it is at its minimum distance from any water cell. Assigning the height as this distance ensures that the adjacency difference rule is respected, since BFS propagates level by level. The maximum height in the matrix corresponds to the farthest land cell from water, which maximizes the height assignment.

Python Solution

from collections import deque
from typing import List

class Solution:
    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
        m, n = len(isWater), len(isWater[0])
        height = [[-1] * n for _ in range(m)]
        q = deque()
        
        # Initialize water cells
        for i in range(m):
            for j in range(n):
                if isWater[i][j] == 1:
                    height[i][j] = 0
                    q.append((i, j))
        
        # Directions: north, south, east, west
        directions = [(-1,0),(1,0),(0,-1),(0,1)]
        
        # BFS to assign heights
        while q:
            x, y = q.popleft()
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and height[nx][ny] == -1:
                    height[nx][ny] = height[x][y] + 1
                    q.append((nx, ny))
        
        return height

The implementation begins by marking all water cells as height 0 and adding them to the queue. BFS ensures that every land cell receives a height equal to its minimum distance from a water cell. By using -1 as a sentinel for unvisited cells, we avoid revisiting any cell. The queue propagates the heights in waves, ensuring adjacency constraints are satisfied.

Go Solution

package main

func highestPeak(isWater [][]int) [][]int {
    m, n := len(isWater), len(isWater[0])
    height := make([][]int, m)
    for i := 0; i < m; i++ {
        height[i] = make([]int, n)
        for j := 0; j < n; j++ {
            height[i][j] = -1
        }
    }

    type pair struct{ x, y int }
    queue := []pair{}

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if isWater[i][j] == 1 {
                height[i][j] = 0
                queue = append(queue, pair{i, j})
            }
        }
    }

    directions := []pair{{-1,0},{1,0},{0,-1},{0,1}}

    for len(queue) > 0 {
        curr := queue[0]
        queue = queue[1:]
        for _, d := range directions {
            nx, ny := curr.x + d.x, curr.y + d.y
            if nx >= 0 && nx < m && ny >= 0 && ny < n && height[nx][ny] == -1 {
                height[nx][ny] = height[curr.x][curr.y] + 1
                queue = append(queue, pair{nx, ny})
            }
        }
    }

    return height
}

In Go, we use slices for the matrix and a simple struct pair for coordinates. The BFS logic is identical. Care is taken to initialize slices with -1 for unvisited cells, similar to the Python sentinel value.

Worked Examples

Example 1: isWater = [[0,1],[0,0]]

Step by step BFS:

Water cells queue: [(0,1)], height [[ -1,0], [-1,-1]]
Process (0,1): assign (0,0)=1, (1,1)=1 → queue [(0,0),(1,1)], height [[1,0],[-1,1]]
Process (0,0): assign (1,0)=2 → queue [(1,1),(1,0)], height [[1,0],[2,1]]
Process remaining cells: no new assignments needed
Final height: [[1,0],[2,1]]

Example 2: isWater = [[0,0,1],[1,0,0],[0,0,0]]

Water cells queue: [(0,2),(1,0)], height initialized with 0 at these positions
BFS propagates heights level by level, assigning each land cell the distance from nearest water
Final height matrix: [[1,1,0],[0,1,1],[1,2,2]]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m * n)	Each cell is visited exactly once in BFS
Space	O(m * n)	Queue may contain all cells in the worst case, plus height matrix

Since BFS propagates from all water cells simultaneously, we efficiently assign heights without repeated scanning.

Test Cases

# Provided examples
assert Solution().highestPeak([[0,1],[0,0]]) == [[1,0],[2,1]]  # BFS propagation
assert Solution().highestPeak([[0,0,1],[1,0,0],[0,0,0]]) == [[1,1,0],[0,1,1],[1,2,2]]  # Multiple water sources

# Single water cell in a corner
assert Solution().highestPeak([[1,0],[0,0]]) == [[0,1],[1,2]]

# All land except one water
assert Solution().highestPeak([[0,0,0],[0,1,0],[0,0,0]]) == [[2,1,