Jobs

Interviews

Discussions

Trapping Rain Water II

Hard

Amazon

3 views

Topics:

ArraysGraphsDynamic ProgrammingGreedy Algorithms

Trapping Rain Water II

You are given an m x n integer matrix heightMap representing the height of each unit cell in a 2D elevation map. Your task is to implement an algorithm to calculate the volume of water it can trap after raining.

Example 1:

Consider the following heightMap:

[ [1, 4, 3, 1, 3, 2],
  [3, 2, 1, 3, 2, 4],
  [2, 3, 3, 2, 3, 1] ]

In this example, the algorithm should return 4 because water is trapped in two small ponds of sizes 1 and 3.

Example 2:

Consider the following heightMap:

[ [3, 3, 3, 3, 3],
  [3, 2, 2, 2, 3],
  [3, 2, 1, 2, 3],
  [3, 2, 2, 2, 3],
  [3, 3, 3, 3, 3] ]

In this example, the algorithm should return 10.

Clarifications:

What should be returned if the input heightMap is invalid (e.g., null or empty)?
What are the constraints on the dimensions of the heightMap and the values of the heights?

Can you provide an efficient solution for this problem, considering both time and space complexity?

Trapping Rain Water II

Hard

Amazon

3 views

Topics:

ArraysGraphsDynamic ProgrammingGreedy Algorithms

Trapping Rain Water II

Example 1:

Consider the following heightMap:

[ [1, 4, 3, 1, 3, 2],
  [3, 2, 1, 3, 2, 4],
  [2, 3, 3, 2, 3, 1] ]

In this example, the algorithm should return 4 because water is trapped in two small ponds of sizes 1 and 3.

Example 2:

Consider the following heightMap:

[ [3, 3, 3, 3, 3],
  [3, 2, 2, 2, 3],
  [3, 2, 1, 2, 3],
  [3, 2, 2, 2, 3],
  [3, 3, 3, 3, 3] ]

In this example, the algorithm should return 10.

Clarifications:

What should be returned if the input heightMap is invalid (e.g., null or empty)?
What are the constraints on the dimensions of the heightMap and the values of the heights?

Can you provide an efficient solution for this problem, considering both time and space complexity?

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:

What are the dimensions of the height map matrix, and what is the maximum size of each dimension?
Can the height values in the matrix be negative, zero, or floating-point numbers?
If the input height map is null or has dimensions that don't allow for trapping water (e.g., 0x0, 1xN, or Nx1), what should the function return?
In the case of multiple possible trapped water configurations, does the problem require returning the *maximum* possible trapped water, or is *any* valid trapped water volume sufficient?
Is there a maximum height value that the matrix elements can hold, and will the total trapped water ever exceed the maximum integer value?

Brute Force Solution

Approach

The brute force approach to finding trapped rain water involves checking every single possible location to see how much water it can hold. We consider each spot as a potential water-holding location and see what the water level would be. We then add up all of the water held at each location to get the total trapped water.

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

For each position in the landscape, imagine filling it with water.
Determine the maximum water level this location can hold. This is limited by the surrounding walls; the water level can only rise to the height of the lowest wall surrounding it.
If the height of the landscape at this position is lower than the maximum water level possible, then this position can hold water.
Calculate the amount of water held at this position by subtracting the height of the land from the water level.
Repeat this calculation for every position in the landscape.
Finally, add up the amount of water that can be held at each position to get the total trapped water.

Code Implementation

def trapping_rain_water_ii_brute_force(heights):
    if not heights or not heights[0]:
        return 0

    rows = len(heights)
    cols = len(heights[0])
    total_water = 0

    for row_index in range(rows):
        for col_index in range(cols):
            # Iterate through each cell to calculate trapped water.

            left_max_height = 0
            for k in range(col_index):
                left_max_height = max(left_max_height, heights[row_index][k])

            right_max_height = 0
            for k in range(col_index + 1, cols):
                right_max_height = max(right_max_height, heights[row_index][k])

            top_max_height = 0
            for k in range(row_index):
                top_max_height = max(top_max_height, heights[k][col_index])

            bottom_max_height = 0
            for k in range(row_index + 1, rows):
                bottom_max_height = max(bottom_max_height, heights[k][col_index])

            # Determine the maximum water level.
            max_water_level = min(left_max_height, right_max_height,\
                                  top_max_height, bottom_max_height)

            # Check if current cell can hold water.
            if max_water_level > heights[row_index][col_index]:
                # Calculate water held and add to the total.
                total_water += max_water_level - heights[row_index][col_index]

    return total_water

Big(O) Analysis

Time Complexity

O(m*n*max(m,n)) – The brute force approach iterates through each cell (m*n) in the 2D height map. For each cell, it finds the maximum height of the surrounding walls in all four directions (up, down, left, right). The cost of finding the maximum height in each direction can be, at worst, proportional to the dimensions of the height map (max(m,n)). Therefore, the overall time complexity is O(m*n*max(m,n)), representing the nested iterations over cells and potential scans along rows or columns.

Space Complexity

O(1) – The brute force approach iterates through each cell of the input landscape (height map) to determine the trapped rain water. The provided description does not explicitly state the use of any auxiliary data structures such as lists, queues, or hash maps. It only involves calculating the water level for each position and accumulating the trapped water, utilizing a few variables for temporary calculations. Therefore, the space complexity is constant because it does not scale with the input size N (where N is the number of cells in the landscape).

Optimal Solution

Approach

The key idea is to think of the water level rising gradually. We focus on the outer edges and slowly work our way inwards, filling the low spots with water along the way. The lowest boundary always determines how much water can be trapped.

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

Imagine the whole structure is surrounded by a boundary, like the edges of a pool.
Find the lowest point on this boundary. This point limits how much water can be held in its immediate area.
Check the neighbors around this lowest point. If any neighbor is lower than the current water level (determined by the lowest boundary point), fill the space with water up to the current water level.
After filling the space, mark the neighbor as 'visited' and make sure to remember its new height (either its original height or the increased water level).
Add these neighbors to our boundary to consider for the next lowest point.
Repeat this process of finding the lowest boundary point, filling water, and updating the boundary until we've visited every spot in the structure.
The amount of water we've added in each step sums up to the total trapped rain water.

Code Implementation

import heapq

def trapping_rain_water_ii(heights):
    if not heights or not heights[0]:
        return 0

    rows, columns = len(heights), len(heights[0])
    visited = [[False] * columns for _ in range(rows)]
    priority_queue = []

    # Add all boundary cells to the priority queue.
    for row_index in range(rows):
        for column_index in range(columns):
            if row_index == 0 or row_index == rows - 1 or column_index == 0 or column_index == columns - 1:
                heapq.heappush(priority_queue, (heights[row_index][column_index], row_index, column_index))
                visited[row_index][column_index] = True

    total_water = 0
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    while priority_queue:
        current_height, current_row, current_column = heapq.heappop(priority_queue)

        # Explore each neighbor.
        for direction_row, direction_column in directions:
            new_row = current_row + direction_row
            new_column = current_column + direction_column

            if 0 <= new_row < rows and 0 <= new_column < columns and not visited[new_row][new_column]:
                # Calculate trapped water if neighbor is lower.
                total_water += max(0, current_height - heights[new_row][new_column])

                # The height of the new cell is the maximum of its original
                # height and the current height, ensuring water is kept.
                heapq.heappush(priority_queue, (max(heights[new_row][new_column], current_height), new_row, new_column))
                visited[new_row][new_column] = True

    return total_water

Big(O) Analysis

Time Complexity

O(m*n*log(m*n)) – The algorithm uses a min-heap to repeatedly find the cell with the minimum height among the boundary cells. In the worst case, all m*n cells are added to the heap. Each heap operation (insertion or removal) takes O(log(m*n)) time. We visit each cell at most once, and for each visited cell, we perform a heap operation and check its at most 4 neighbors. Therefore, the overall time complexity is dominated by the heap operations, resulting in O(m*n*log(m*n)), where m and n are the dimensions of the height map.

Space Complexity

O(M*N) – The primary space usage comes from the priority queue (or heap) which stores boundary cells. In the worst case, all cells of the input matrix could be on the boundary. Additionally, we need a visited matrix to keep track of visited locations which is the same size as the input matrix. Thus, the auxiliary space is proportional to the number of cells in the input matrix, where M is the number of rows and N is the number of columns. This leads to a space complexity of O(M*N).

Edge Cases

Case	How to Handle
Null or empty height map	Return 0 immediately as no water can be trapped in an empty or null map.
Height map with dimensions 1xN or Nx1	Return 0 immediately because at least two rows and two columns are needed to trap water.
Height map with all cells having the same height	Return 0 as there's no height difference to trap any water.
Height map with very large dimensions (e.g., 1000x1000)	Ensure the priority queue and visited set do not cause memory issues and that the algorithm's time complexity remains efficient (O(MNlog(M+N)) when M and N are dimensions).
Height map with extremely large height values that could cause integer overflow during calculations.	Use long data type to store height values and water levels to avoid integer overflow.
Height map with negative height values	Treat negative height values as valid input and the algorithm should still compute trapped water correctly as it relies on relative height differences.
Height map where the boundary is lower than the internal cells.	The algorithm correctly uses the boundary cells as the starting point for the priority queue and propagates inward.
Height map contains zero height cells scattered throughout the map.	The algorithm should correctly handle zero-height cells as potential water-holding areas or paths for water to escape.

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:

What are the dimensions of the height map matrix, and what is the maximum size of each dimension?
Can the height values in the matrix be negative, zero, or floating-point numbers?
If the input height map is null or has dimensions that don't allow for trapping water (e.g., 0x0, 1xN, or Nx1), what should the function return?
In the case of multiple possible trapped water configurations, does the problem require returning the *maximum* possible trapped water, or is *any* valid trapped water volume sufficient?
Is there a maximum height value that the matrix elements can hold, and will the total trapped water ever exceed the maximum integer value?

Brute Force Solution

Approach

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

For each position in the landscape, imagine filling it with water.
Determine the maximum water level this location can hold. This is limited by the surrounding walls; the water level can only rise to the height of the lowest wall surrounding it.
If the height of the landscape at this position is lower than the maximum water level possible, then this position can hold water.
Calculate the amount of water held at this position by subtracting the height of the land from the water level.
Repeat this calculation for every position in the landscape.
Finally, add up the amount of water that can be held at each position to get the total trapped water.

Code Implementation

def trapping_rain_water_ii_brute_force(heights):
    if not heights or not heights[0]:
        return 0

    rows = len(heights)
    cols = len(heights[0])
    total_water = 0

    for row_index in range(rows):
        for col_index in range(cols):
            # Iterate through each cell to calculate trapped water.

            left_max_height = 0
            for k in range(col_index):
                left_max_height = max(left_max_height, heights[row_index][k])

            right_max_height = 0
            for k in range(col_index + 1, cols):
                right_max_height = max(right_max_height, heights[row_index][k])

            top_max_height = 0
            for k in range(row_index):
                top_max_height = max(top_max_height, heights[k][col_index])

            bottom_max_height = 0
            for k in range(row_index + 1, rows):
                bottom_max_height = max(bottom_max_height, heights[k][col_index])

            # Determine the maximum water level.
            max_water_level = min(left_max_height, right_max_height,\
                                  top_max_height, bottom_max_height)

            # Check if current cell can hold water.
            if max_water_level > heights[row_index][col_index]:
                # Calculate water held and add to the total.
                total_water += max_water_level - heights[row_index][col_index]

    return total_water

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine the whole structure is surrounded by a boundary, like the edges of a pool.
Find the lowest point on this boundary. This point limits how much water can be held in its immediate area.
Check the neighbors around this lowest point. If any neighbor is lower than the current water level (determined by the lowest boundary point), fill the space with water up to the current water level.
After filling the space, mark the neighbor as 'visited' and make sure to remember its new height (either its original height or the increased water level).
Add these neighbors to our boundary to consider for the next lowest point.
Repeat this process of finding the lowest boundary point, filling water, and updating the boundary until we've visited every spot in the structure.
The amount of water we've added in each step sums up to the total trapped rain water.

Code Implementation

import heapq

def trapping_rain_water_ii(heights):
    if not heights or not heights[0]:
        return 0

    rows, columns = len(heights), len(heights[0])
    visited = [[False] * columns for _ in range(rows)]
    priority_queue = []

    # Add all boundary cells to the priority queue.
    for row_index in range(rows):
        for column_index in range(columns):
            if row_index == 0 or row_index == rows - 1 or column_index == 0 or column_index == columns - 1:
                heapq.heappush(priority_queue, (heights[row_index][column_index], row_index, column_index))
                visited[row_index][column_index] = True

    total_water = 0
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    while priority_queue:
        current_height, current_row, current_column = heapq.heappop(priority_queue)

        # Explore each neighbor.
        for direction_row, direction_column in directions:
            new_row = current_row + direction_row
            new_column = current_column + direction_column

            if 0 <= new_row < rows and 0 <= new_column < columns and not visited[new_row][new_column]:
                # Calculate trapped water if neighbor is lower.
                total_water += max(0, current_height - heights[new_row][new_column])

                # The height of the new cell is the maximum of its original
                # height and the current height, ensuring water is kept.
                heapq.heappush(priority_queue, (max(heights[new_row][new_column], current_height), new_row, new_column))
                visited[new_row][new_column] = True

    return total_water

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty height map	Return 0 immediately as no water can be trapped in an empty or null map.
Height map with dimensions 1xN or Nx1	Return 0 immediately because at least two rows and two columns are needed to trap water.
Height map with all cells having the same height	Return 0 as there's no height difference to trap any water.
Height map with very large dimensions (e.g., 1000x1000)	Ensure the priority queue and visited set do not cause memory issues and that the algorithm's time complexity remains efficient (O(MNlog(M+N)) when M and N are dimensions).
Height map with extremely large height values that could cause integer overflow during calculations.	Use long data type to store height values and water levels to avoid integer overflow.
Height map with negative height values	Treat negative height values as valid input and the algorithm should still compute trapped water correctly as it relies on relative height differences.
Height map where the boundary is lower than the internal cells.	The algorithm correctly uses the boundary cells as the starting point for the priority queue and propagates inward.
Height map contains zero height cells scattered throughout the map.	The algorithm should correctly handle zero-height cells as potential water-holding areas or paths for water to escape.