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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Map of Highest Peak

Difficulty: Medium

Problem Description

You are given an integer matrix isWater of size m x n that represents a map of land and water cells. The goal is to assign each cell a height such that the maximum height in the matrix is maximized, following specific rules regarding water and land cells.

Key Insights

  • Water cells must have a height of 0.
  • Heights of adjacent cells must differ by at most 1.
  • The task is to maximize the maximum height of land cells while adhering to the above constraints.
  • BFS (Breadth-First Search) can be utilized to propagate heights from water cells to adjacent land cells.

Space and Time Complexity

Time Complexity: O(m * n)
Space Complexity: O(m * n)

Solution

To solve this problem, we can use a Breadth-First Search (BFS) approach. We start by initializing a height matrix where water cells are set to 0. From each water cell, we explore its adjacent land cells, assigning them heights based on the height of the water cell plus one. We continue this process, ensuring that heights do not exceed the maximum allowed difference of 1 between adjacent cells. This approach guarantees that heights are assigned optimally, maximizing the maximum height achievable.

Code Solutions

from collections import deque

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

    # Initialize the height of water cells and enqueue them
    for i in range(m):
        for j in range(n):
            if isWater[i][j] == 1:
                height[i][j] = 0
                queue.append((i, j))
    
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    # BFS to assign heights to land cells
    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
← Back to All Questions