Jobs

Interviews

Discussions

Trapping Rain Water

Hard

Amazon

14 views

Topics:

ArraysDynamic ProgrammingTwo Pointers

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

For example, consider the elevation map represented by the array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water are being trapped. The black section represents the elevation map, and the blue section represents the trapped water.

As another example, consider the elevation map represented by the array [4,2,0,3,2,5]. In this case, 9 units of rain water are being trapped.

How would you approach this problem? What is the time and space complexity of your solution? Can you identify any edge cases?

Trapping Rain Water

Hard

Amazon

14 views

Topics:

ArraysDynamic ProgrammingTwo Pointers

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

As another example, consider the elevation map represented by the array [4,2,0,3,2,5]. In this case, 9 units of rain water are being trapped.

How would you approach this problem? What is the time and space complexity of your solution? Can you identify any edge cases?

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 is the maximum size of the `heights` array?
Can the values in the `heights` array be zero or negative?
What should I return if the `heights` array is null or empty?
If no water can be trapped, should I return 0?
Are there any constraints on the range of values within the `heights` array?

Brute Force Solution

Approach

The goal is to figure out how much water can be trapped between different height levels. The brute force approach systematically checks every possible location to see how much water it can hold by considering the surrounding heights.

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

For each height level, find the tallest height to the left of it.
Next, find the tallest height to the right of it.
Determine the smaller of these two surrounding tallest heights. This is the maximum water level that location can hold.
If the current height level is shorter than the maximum water level, calculate the difference. This difference represents the amount of water that can be trapped at that location.
If the current height level is taller than the maximum water level, no water can be trapped at that location.
Repeat these steps for every single height level.
Finally, add up the amount of water trapped at each location to find the total amount of trapped water.

Code Implementation

def trapping_rain_water_brute_force(heights):
    total_water_trapped = 0
    number_of_heights = len(heights)

    for current_height_index in range(number_of_heights):
        maximum_height_left = 0
        # Find the maximum height to the left
        for i in range(current_height_index):
            maximum_height_left = max(maximum_height_left, heights[i])

        maximum_height_right = 0
        # Find the maximum height to the right
        for i in range(current_height_index + 1, number_of_heights):
            maximum_height_right = max(maximum_height_right, heights[i])

        # Determine the lower of the max left and right heights
        minimum_of_maximums = min(maximum_height_left, maximum_height_right)

        # Water can only be trapped if the current height is lower
        if heights[current_height_index] < minimum_of_maximums:
            total_water_trapped += minimum_of_maximums - heights[current_height_index]

    return total_water_trapped

Big(O) Analysis

Time Complexity

O(n²) – The provided brute force approach iterates through each of the n height levels. For each height level, it searches for the maximum height to the left and the maximum height to the right. These searches involve iterating through the elements to the left and to the right of the current position, which, in the worst case, could involve examining all other elements. Therefore, for each of the n elements, we potentially perform another n operations. This results in approximately n * n operations, which simplifies to O(n²).

Space Complexity

O(N) – The algorithm calculates the tallest height to the left and right for each height level. This requires storing the maximum heights to the left in a list of size N and the maximum heights to the right in another list of size N, where N is the number of height levels. The space used is thus proportional to the input size N. Therefore, the auxiliary space complexity is O(N).

Optimal Solution

Approach

The key to efficiently calculating trapped rainwater is to avoid recalculating the maximum height on each side for every position. Instead, we pre-compute and store the maximum height to the left and right of each position, then use these values to quickly determine the water level and amount of trapped water.

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

First, think about how much water can be held at any one place: it's limited by the tallest bar on its left AND the tallest bar on its right.
Next, imagine sweeping through all the bars from left to right. For each bar, find the tallest bar to its left.
Do the same thing, but this time sweep from right to left. For each bar, find the tallest bar to its right.
Now, at each bar, you know the tallest bar on its left and the tallest bar on its right. The water level at that bar is the *smaller* of those two heights. If that water level is higher than the height of the current bar, then water is trapped there.
The amount of water trapped at a location is just the difference between the water level at that location and the height of the bar. Add up all these differences to find the total trapped water.

Code Implementation

def trapping_rain_water(heights):
    number_of_bars = len(heights)
    if number_of_bars == 0:
        return 0

    max_height_left = [0] * number_of_bars
    max_height_right = [0] * number_of_bars

    # Calculate max height to the left for each bar
    max_height_left[0] = heights[0]
    for i in range(1, number_of_bars):
        max_height_left[i] = max(heights[i], max_height_left[i - 1])

    # Calculate max height to the right for each bar
    max_height_right[number_of_bars - 1] = heights[number_of_bars - 1]
    for i in range(number_of_bars - 2, -1, -1):
        max_height_right[i] = max(heights[i], max_height_right[i + 1])

    total_water = 0
    # Water level is limited by the smaller of the two max heights
    for i in range(0, number_of_bars):
        water_level = min(max_height_left[i], max_height_right[i])

        # Add trapped water only if water level exceeds bar height
        if water_level > heights[i]:
            total_water += water_level - heights[i]

    return total_water

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n three times. The first iteration calculates the maximum height to the left for each position. The second calculates the maximum height to the right. The final iteration calculates the trapped water by comparing the height at each position with the precomputed left and right maximums. Therefore, the time complexity is O(n).

Space Complexity

O(N) – The algorithm pre-computes the maximum height to the left and right of each position and stores them in two separate arrays. Therefore, the algorithm utilizes two auxiliary arrays, left_max and right_max, each having the same size as the input array. If N is the length of the input array representing the height of each bar, the space occupied by these two arrays is 2N, which simplifies to O(N).

Edge Cases

Case	How to Handle
Empty array	Return 0 immediately since no water can be trapped.
Array with only one element	Return 0 immediately since there are no boundaries to trap water.
Array with two elements	Return 0 since two bars cannot trap water; water needs a minimum of 3 to form a container.
Array with all elements equal to zero	Return 0 as there are no walls to trap water.
Array with monotonically increasing or decreasing elements	Return 0 since water will always flow away.
Array with very large height values that could cause integer overflow	Use a data type (like long) capable of storing potentially large sums to prevent overflow.
Array with a single very high peak and the rest are very small	Ensure the algorithm correctly calculates the water trapped on both sides of the peak.
Maximum-sized input array with maximum height values, leading to large calculations.	The solution's time complexity (O(n) for two-pointer or dynamic programming) must remain efficient to avoid timeouts.

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 is the maximum size of the `heights` array?
Can the values in the `heights` array be zero or negative?
What should I return if the `heights` array is null or empty?
If no water can be trapped, should I return 0?
Are there any constraints on the range of values within the `heights` array?

Brute Force Solution

Approach

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

For each height level, find the tallest height to the left of it.
Next, find the tallest height to the right of it.
Determine the smaller of these two surrounding tallest heights. This is the maximum water level that location can hold.
If the current height level is shorter than the maximum water level, calculate the difference. This difference represents the amount of water that can be trapped at that location.
If the current height level is taller than the maximum water level, no water can be trapped at that location.
Repeat these steps for every single height level.
Finally, add up the amount of water trapped at each location to find the total amount of trapped water.

Code Implementation

def trapping_rain_water_brute_force(heights):
    total_water_trapped = 0
    number_of_heights = len(heights)

    for current_height_index in range(number_of_heights):
        maximum_height_left = 0
        # Find the maximum height to the left
        for i in range(current_height_index):
            maximum_height_left = max(maximum_height_left, heights[i])

        maximum_height_right = 0
        # Find the maximum height to the right
        for i in range(current_height_index + 1, number_of_heights):
            maximum_height_right = max(maximum_height_right, heights[i])

        # Determine the lower of the max left and right heights
        minimum_of_maximums = min(maximum_height_left, maximum_height_right)

        # Water can only be trapped if the current height is lower
        if heights[current_height_index] < minimum_of_maximums:
            total_water_trapped += minimum_of_maximums - heights[current_height_index]

    return total_water_trapped

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, think about how much water can be held at any one place: it's limited by the tallest bar on its left AND the tallest bar on its right.
Next, imagine sweeping through all the bars from left to right. For each bar, find the tallest bar to its left.
Do the same thing, but this time sweep from right to left. For each bar, find the tallest bar to its right.
Now, at each bar, you know the tallest bar on its left and the tallest bar on its right. The water level at that bar is the *smaller* of those two heights. If that water level is higher than the height of the current bar, then water is trapped there.
The amount of water trapped at a location is just the difference between the water level at that location and the height of the bar. Add up all these differences to find the total trapped water.

Code Implementation

def trapping_rain_water(heights):
    number_of_bars = len(heights)
    if number_of_bars == 0:
        return 0

    max_height_left = [0] * number_of_bars
    max_height_right = [0] * number_of_bars

    # Calculate max height to the left for each bar
    max_height_left[0] = heights[0]
    for i in range(1, number_of_bars):
        max_height_left[i] = max(heights[i], max_height_left[i - 1])

    # Calculate max height to the right for each bar
    max_height_right[number_of_bars - 1] = heights[number_of_bars - 1]
    for i in range(number_of_bars - 2, -1, -1):
        max_height_right[i] = max(heights[i], max_height_right[i + 1])

    total_water = 0
    # Water level is limited by the smaller of the two max heights
    for i in range(0, number_of_bars):
        water_level = min(max_height_left[i], max_height_right[i])

        # Add trapped water only if water level exceeds bar height
        if water_level > heights[i]:
            total_water += water_level - heights[i]

    return total_water

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty array	Return 0 immediately since no water can be trapped.
Array with only one element	Return 0 immediately since there are no boundaries to trap water.
Array with two elements	Return 0 since two bars cannot trap water; water needs a minimum of 3 to form a container.
Array with all elements equal to zero	Return 0 as there are no walls to trap water.
Array with monotonically increasing or decreasing elements	Return 0 since water will always flow away.
Array with very large height values that could cause integer overflow	Use a data type (like long) capable of storing potentially large sums to prevent overflow.
Array with a single very high peak and the rest are very small	Ensure the algorithm correctly calculates the water trapped on both sides of the peak.
Maximum-sized input array with maximum height values, leading to large calculations.	The solution's time complexity (O(n) for two-pointer or dynamic programming) must remain efficient to avoid timeouts.