We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Map of Highest Peak

Number: 1876

Difficulty: Medium

Paid? No

Companies: Amazon, Google

Problem Description

Given an m x n matrix isWater where each cell is either land (0) or water (1), assign non-negative heights to all cells such that water cells have height 0 and any two adjacent cells differ in height by at most 1. The goal is to maximize the maximum height in the matrix. This problem is equivalent to finding the minimum distance from each cell to a water cell.

Key Insights

  • Water cells are fixed with height 0 and act as BFS sources.
  • A multi-source BFS calculates the minimum distance from any land cell to its nearest water cell.
  • Each cell’s height will be its distance from the nearest water cell, ensuring the adjacent difference is at most 1.
  • This approach guarantees the maximum height in the matrix is maximized.

Space and Time Complexity

Time Complexity: O(m * n) – each cell is processed once in the BFS. Space Complexity: O(m * n) – space needed for the queue and the result matrix.

Solution

We use a multi-source Breadth-First Search (BFS) starting from all water cells (cells with value 1 in isWater). Initially, all water cells are enqueued with height 0. As we pop a cell from the queue, we update its adjacent land neighbors with height = current height + 1 if they have not been visited yet. This BFS guarantees that each cell gets the minimum distance to a water cell, which satisfies the height assignment rules.

Code Solutions

from collections import deque

def highestPeak(isWater):
    # Dimensions of the matrix
    m, n = len(isWater), len(isWater[0])
    # Initialize the resulting height matrix with -1 (unvisited)
    height = [[-1] * n for _ in range(m)]
    # Queue for BFS
    queue = deque()
    
    # Enqueue all water cells with height 0.
    for i in range(m):
        for j in range(n):
            if isWater[i][j] == 1:
                height[i][j] = 0  # water cells have height 0
                queue.append((i, j))
    
    # Directions for up, down, left, right movement.
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    
    # Process the BFS queue
    while queue:
        i, j = queue.popleft()
        # Check all neighboring cells.
        for di, dj in directions:
            ni, nj = i + di, j + dj
            # Check if new coordinates are within bounds and not yet visited.
            if 0 <= ni < m and 0 <= nj < n and height[ni][nj] == -1:
                height[ni][nj] = height[i][j] + 1  # update height based on current cell
                queue.append((ni, nj))
    
    return height

# Example usage:
isWater = [[0,1],[0,0]]
print(highestPeak(isWater))
← Back to All Questions