Taro Logo

Map of Highest Peak

#1040 Most AskedMedium
23 views
Topics:
ArraysGraphs

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/

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What data type represents the elevation? Can it be a floating-point number or is it always an integer, and can it be negative?
  2. What are the dimensions of the map? Can either dimension be zero, resulting in an empty map?
  3. If there are multiple cells that could be considered the 'highest peak' based on the initial zero elevations provided, is any valid assignment acceptable?
  4. Are the coordinates provided valid coordinates within the bounds of the initially zeroed map?
  5. What should be the elevation of a cell that is not reachable from any of the coordinates?

Brute Force Solution

Approach

We need to figure out the height of each location in a map based on the heights of some known locations. The brute force approach will try setting a height for every location one by one, considering all possible height values. We will check if this height assignment is valid given the constraints.

Here's how the algorithm would work step-by-step:

  1. Start with the first unknown location on the map.
  2. Assign it a possible height value (starting, say, from zero and incrementing upwards).
  3. Check if the height assigned to this location conflicts with the height differences of its known and already-determined neighbors. If it does, try a different height.
  4. If the height works for the first location, move to the next unknown location and repeat the process of assigning and checking heights.
  5. Continue until heights have been assigned to all unknown locations.
  6. After assigning heights to all locations, verify if the map as a whole fulfills the constraints regarding height differences between adjacent locations. If it does not, backtrack and change a previous height assignment to explore a different possibility.
  7. Repeat this process, trying different height assignments until a valid map is found, or until all possibilities are exhausted.

Code Implementation

def solve_map_brute_force(height_map, known_heights):
    rows = len(height_map)
    cols = len(height_map[0])
    unknown_locations = []
    for row_index in range(rows):
        for col_index in range(cols):
            if height_map[row_index][col_index] is None:
                unknown_locations.append((row_index, col_index))

    def is_valid(current_map):
        for row_index in range(rows):
            for col_index in range(cols):
                if row_index > 0:
                    if current_map[row_index][col_index] is not None and current_map[row_index - 1][col_index] is not None and abs(current_map[row_index][col_index] - current_map[row_index - 1][col_index]) > 1:
                        return False
                if col_index > 0:
                    if current_map[row_index][col_index] is not None and current_map[row_index][col_index - 1] is not None and abs(current_map[row_index][col_index] - current_map[row_index][col_index - 1]) > 1:
                        return False
        return True

    def solve(index, current_map):
        if index == len(unknown_locations):
            # All locations assigned, check if map is valid
            if is_valid(current_map):
                return current_map
            else:
                return None

        row_index, col_index = unknown_locations[index]
        for height in range(10):
            # Trying every possible height at this location.
            current_map[row_index][col_index] = height

            valid_height = True
            if row_index > 0 and current_map[row_index-1][col_index] is not None and abs(current_map[row_index][col_index] - current_map[row_index-1][col_index]) > 1:
                valid_height = False
            if col_index > 0 and current_map[row_index][col_index-1] is not None and abs(current_map[row_index][col_index] - current_map[row_index][col_index-1]) > 1:
                valid_height = False

            if valid_height:
                result_map = solve(index + 1, current_map)
                if result_map:
                    return result_map

            # Reset the height for backtracking.
            current_map[row_index][col_index] = None

        return None

    # Create a copy of the height map.
    initial_map = [row[:] for row in height_map]

    # Pre-fill known heights
    for row_index in range(rows):
        for col_index in range(cols):
            if (row_index, col_index) in known_heights:
                initial_map[row_index][col_index] = known_heights[(row_index, col_index)]
            else:
                initial_map[row_index][col_index] = None

    # Recursively solve the map.
    solution = solve(0, initial_map)
    return solution

Big(O) Analysis

Time Complexity
O(Infinity) – The provided algorithm describes a brute-force approach that attempts to assign heights to unknown locations and then backtracks when a conflict arises. In the worst-case scenario, if the constraints are very restrictive or even contradictory, the algorithm might explore an infinite number of height assignments without ever finding a valid solution. The number of possible height values for each location could be theoretically infinite, or simply extremely large, thus making the brute force algorithm highly inefficient and its runtime unbounded. Since we have no bounds on the search space for heights and the algorithm backtracks without guaranteed progress, the time complexity can be considered effectively infinite.
Space Complexity
O(N) – The described brute force approach uses recursion implicitly through backtracking. In the worst-case scenario, the algorithm may explore a depth equal to the number of unknown locations, which is related to the size of the map, N. Each recursive call will add a new frame to the call stack to store local variables and the return address. Thus the recursion stack can grow up to a size proportional to N, resulting in O(N) space complexity.

Optimal Solution

Approach

We need to figure out the height of each location on a map based on given clues about differences in height between neighboring locations. The clever approach starts from a location we know the height of, and then figures out the heights of other locations by spreading out the height information from there.

Here's how the algorithm would work step-by-step:

  1. Find a starting point; if a starting height isn't given, choose any location on the map and give it a height of 0.
  2. Imagine water spreading out from that starting location. As the water spreads, it figures out the height of each place it reaches.
  3. When the water reaches a new place, use the given height difference information to calculate the height of that new place. The clues tell you if the new place is higher or lower than the current place.
  4. Keep spreading out the water until you have visited every location on the map and figured out its height.
  5. Once every location has a height, shift all the heights so that the smallest height is 0. This ensures that there are no negative heights.

Code Implementation

def map_of_highest_peak(height_differences):
    if not height_differences:
        return []

    rows = len(height_differences)
    cols = len(height_differences[0])
    heights = [[None] * cols for _ in range(rows)]

    # Choose a starting point and assign it a height of 0.
    start_row = 0
    start_col = 0
    heights[start_row][start_col] = 0

    queue = [(start_row, start_col)]

    while queue:
        current_row, current_col = queue.pop(0)

        # Iterate through neighbors to determine heights.
        neighbors = [
            # Up
            (current_row - 1, current_col),
            # Down
            (current_row + 1, current_col),
            # Left
            (current_row, current_col - 1),
            # Right
            (current_row, current_col + 1)
        ]

        for neighbor_row, neighbor_col in neighbors:
            if 0 <= neighbor_row < rows and 0 <= neighbor_col < cols and heights[neighbor_row][neighbor_col] is None:
                # Determine height of neighboring cell
                if neighbor_row < current_row:
                    heights[neighbor_row][neighbor_col] = heights[current_row][current_col] - height_differences[neighbor_row][current_col]
                elif neighbor_row > current_row:
                    heights[neighbor_row][neighbor_col] = heights[current_row][current_col] + height_differences[current_row][current_col]
                elif neighbor_col < current_col:
                    heights[neighbor_row][neighbor_col] = heights[current_row][current_col] - height_differences[current_row][neighbor_col]
                else:
                    heights[neighbor_row][neighbor_col] = heights[current_row][current_col] + height_differences[current_row][current_col - 1]
                queue.append((neighbor_row, neighbor_col))

    # Shift all heights to ensure the smallest height is 0.
    min_height = min(min(row) for row in heights)

    # Ensure no negative heights exist
    for row in range(rows):
        for col in range(cols):
            heights[row][col] -= min_height

    return heights

Big(O) Analysis

Time Complexity
O(m*n) – The algorithm visits each location in the map at least once. Let m be the number of clues (height differences between neighbors) and n be the number of locations on the map. In the worst-case scenario, we process each clue once as the water spreads, and in order to visit all the locations, the number of clues we check could approach the number of the locations. Thus, each clue could be processed and applied across most or all of the locations. Hence, the time complexity is driven by processing at most every clue for every location which approximates to O(m*n).
Space Complexity
O(N) – The algorithm utilizes a queue to simulate the spreading of water, where N is the number of locations on the map. In the worst-case scenario, all locations could be added to the queue simultaneously, resulting in a queue size proportional to N. Additionally, a data structure to keep track of visited locations is implicitly used, which in the worst case, could also store all the locations (N). Therefore, the auxiliary space is O(N) due to the queue and visited locations storage.

Edge Cases

Null or empty height map
How to Handle:
Return an empty matrix or throw an IllegalArgumentException as no valid peak map can be constructed.
Height map with only one cell
How to Handle:
Return a 1x1 matrix with value 0, as it's the only possible solution.
Height map with all zero heights specified
How to Handle:
Start the BFS from cells with specified height zero and proceed outwards.
Integer overflow during height calculation (if heights are derived from coordinates)
How to Handle:
Use a data type that can accommodate larger values, such as long, or perform modular arithmetic to prevent overflow.
Large map dimensions that may cause memory issues
How to Handle:
Ensure the data structures used (queue, result matrix) are memory-efficient, potentially processing in chunks if needed for extremely large maps.
Negative initial heights are provided.
How to Handle:
Ensure initial height values are handled correctly, treating them as minimum heights in the water flow simulation.
Cells with the same initial height are adjacent to each other.
How to Handle:
The algorithm should correctly handle areas with the same known height, expanding outwards in a consistent manner.
The provided input grid is not rectangular.
How to Handle:
The algorithm should either throw an exception, or gracefully handle by considering only rectangular portions when determining neighbors.
0/1916 completed