To solve the problem, I used the Breadth-First Search (BFS) approach. I started by initializing a height matrix of the same size as the input, with all cells set to (-1) to represent unvisited cells. All water cells (where isWater[i][j] == 1) were set to a height of 0 and added to a queue, serving as the starting points for height propagation.
Using BFS, I processed each cell in the queue, exploring its four neighbors (north, south, east, west). For each neighbor, if it was within bounds and unvisited, I set its height to the current cell's height plus 1 and added it to the queue. This ensured that the height differences between adjacent cells never exceeded 1. The BFS continued until all reachable cells had been assigned a height.
By starting from water cells and propagating outward, the algorithm naturally maximized the heights of the land cells while satisfying the constraints. Once the BFS completed, the height matrix contained the desired heights, with the maximum height achieved.
from collections import deque
class Solution:
def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
m, n = len(isWater), len(isWater[0])
height = [[-1 for _ in range(n)] for _ in range(m)]
queue = deque()
for i in range(m):
for j in range(n):
if isWater[i][j] == 1:
height[i][j] = 0
queue.append((i, j))
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
# bfs
while queue:
x, y = queue.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
queue.append((nx, ny))
return height- Time: O(m * n)
- Space: O(m * n)
