Jobs

Interviews

Discussions

Trapping Rain Water

Hard

Walmart

2 views

Topics:

ArraysDynamic ProgrammingTwo PointersStacks

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.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

n == height.length
1 <= n <= 2 * 10⁴
0 <= height[i] <= 10⁵

Trapping Rain Water

Hard

Walmart

2 views

Topics:

ArraysDynamic ProgrammingTwo PointersStacks

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.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

n == height.length
1 <= n <= 2 * 10⁴
0 <= height[i] <= 10⁵

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 height of the bars in the `height` array? Are there any upper bounds on the integer values?
Can the input array `height` be empty or null? If so, what should I return in those cases?
Is it possible for the input array `height` to contain only one or two elements? How should I handle such edge cases?
Are all values in the `height` array non-negative as stated, or is it possible to encounter negative values, and if so, how should I handle them?
If no water can be trapped, should I return 0?

Brute Force Solution

Approach

The brute force approach to calculate trapped rainwater involves examining each location individually. For each location, we'll determine how much water it can hold by looking at the highest boundaries around it. After assessing each location, we sum the water from all the locations to get the total trapped rainwater.

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

For every location, find the tallest wall to its left.
Also, for the same location, find the tallest wall to its right.
Determine the shorter of these two tallest walls; this will limit how much water can be held at that location.
If the height of the wall at the location is less than the height of the shorter tallest wall, then water can be trapped.
Calculate the amount of trapped water at that location by subtracting the wall's height from the height of the shorter tallest wall.
If the wall is taller than the shorter tallest wall, then no water can be trapped at that location.
Repeat these steps for every location.
Finally, add up the amount of trapped water from all the locations to get the total trapped water.

Code Implementation

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

    for current_location in range(number_of_locations):
        max_height_left = 0
        # Find the tallest wall to the left of the current location
        for left_location in range(current_location):
            max_height_left = max(max_height_left, heights[left_location])

        max_height_right = 0
        # Find the tallest wall to the right of the current location
        for right_location in range(current_location + 1, number_of_locations):
            max_height_right = max(max_height_right, heights[right_location])

        # The shorter wall determines the water level
        shorter_wall = min(max_height_left, max_height_right)

        # Calculate trapped water if possible
        if heights[current_location] < shorter_wall:
            total_water_trapped += shorter_wall - heights[current_location]

    return total_water_trapped

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n locations in the input array. For each location, it finds the maximum height to the left and the maximum height to the right by iterating through the array again. Finding the maximum height to the left and right of each location takes O(n) time each. Since this is done for each of the n locations, the overall time complexity is O(n * n), which simplifies to O(n²).

Space Complexity

O(1) – The brute force approach calculates trapped rainwater by iterating through each location and finding the tallest wall to its left and right. It does not use any auxiliary data structures that scale with the input size N (where N is the number of locations or the length of the height array). Temporary variables are used to store the maximum left and right heights, but the number of such variables is constant regardless of N. Therefore, the space complexity is constant.

Optimal Solution

Approach

The core idea is to calculate how much water can be trapped at each position. This is done by figuring out the highest bar to the left and the highest bar to the right of each position, then using the lower of these two heights to determine the water level that can be held.

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

For each position, determine the maximum height of a bar to the left of that position.
Similarly, for each position, determine the maximum height of a bar to the right of that position.
For each position, compare the maximum height to the left and the maximum height to the right. The smaller of these two heights dictates the water level.
If the water level at a position is higher than the height of the bar at that position, then that position can trap water. The amount of water trapped is the difference between the water level and the bar's height.
Add up the amount of water trapped at each position to get the total amount of trapped rain 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 position
    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 position
    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_trapped = 0
    for i in range(number_of_bars):
        # Water level is dictated by the shorter of the max heights
        water_level = min(max_height_left[i], max_height_right[i])

        # Only trap water if water level is higher than current height
        if water_level > heights[i]:

            total_water_trapped += water_level - heights[i]

    return total_water_trapped

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the array of size n to find the maximum height to the left for each position. It then iterates through the array of size n again to find the maximum height to the right for each position. Finally, it iterates through the array of size n one more time to calculate the trapped water. Because these iterations are sequential (not nested) the time complexity is O(n) + O(n) + O(n), which simplifies to O(n).

Space Complexity

O(N) – The algorithm creates two arrays, left_max and right_max, to store the maximum height to the left and right of each position, respectively. Both arrays have the same size as the input array, denoted as N. Therefore, the auxiliary space used is proportional to the input size N. This results in a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty or null input array	Return 0 immediately, as no water can be trapped.
Array with only one or two elements	Return 0 immediately, as no water can be trapped between bars with fewer than 3 columns.
Array with all elements equal to 0	Return 0, as there are no bars to trap any water.
Array with all elements having the same non-zero value	Return 0, as there is no variation in height to trap water.
Array with only one peak element (all other elements are lower)	The algorithm should correctly calculate water trapped on either side of the peak.
Monotonically increasing or decreasing array	Return 0, as there are no dips to hold water.
Large height values leading to potential integer overflow	Use a data type (e.g., long) that can accommodate larger values to prevent overflow during calculations.
Array with very large size impacting performance	The solution should have a time complexity of O(n) to scale efficiently with larger inputs; space complexity considerations are also important.

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 height of the bars in the `height` array? Are there any upper bounds on the integer values?
Can the input array `height` be empty or null? If so, what should I return in those cases?
Is it possible for the input array `height` to contain only one or two elements? How should I handle such edge cases?
Are all values in the `height` array non-negative as stated, or is it possible to encounter negative values, and if so, how should I handle them?
If no water can be trapped, should I return 0?

Brute Force Solution

Approach

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

For every location, find the tallest wall to its left.
Also, for the same location, find the tallest wall to its right.
Determine the shorter of these two tallest walls; this will limit how much water can be held at that location.
If the height of the wall at the location is less than the height of the shorter tallest wall, then water can be trapped.
Calculate the amount of trapped water at that location by subtracting the wall's height from the height of the shorter tallest wall.
If the wall is taller than the shorter tallest wall, then no water can be trapped at that location.
Repeat these steps for every location.
Finally, add up the amount of trapped water from all the locations to get the total trapped water.

Code Implementation

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

    for current_location in range(number_of_locations):
        max_height_left = 0
        # Find the tallest wall to the left of the current location
        for left_location in range(current_location):
            max_height_left = max(max_height_left, heights[left_location])

        max_height_right = 0
        # Find the tallest wall to the right of the current location
        for right_location in range(current_location + 1, number_of_locations):
            max_height_right = max(max_height_right, heights[right_location])

        # The shorter wall determines the water level
        shorter_wall = min(max_height_left, max_height_right)

        # Calculate trapped water if possible
        if heights[current_location] < shorter_wall:
            total_water_trapped += shorter_wall - heights[current_location]

    return total_water_trapped

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

For each position, determine the maximum height of a bar to the left of that position.
Similarly, for each position, determine the maximum height of a bar to the right of that position.
For each position, compare the maximum height to the left and the maximum height to the right. The smaller of these two heights dictates the water level.
If the water level at a position is higher than the height of the bar at that position, then that position can trap water. The amount of water trapped is the difference between the water level and the bar's height.
Add up the amount of water trapped at each position to get the total amount of trapped rain 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 position
    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 position
    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_trapped = 0
    for i in range(number_of_bars):
        # Water level is dictated by the shorter of the max heights
        water_level = min(max_height_left[i], max_height_right[i])

        # Only trap water if water level is higher than current height
        if water_level > heights[i]:

            total_water_trapped += water_level - heights[i]

    return total_water_trapped

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null input array	Return 0 immediately, as no water can be trapped.
Array with only one or two elements	Return 0 immediately, as no water can be trapped between bars with fewer than 3 columns.
Array with all elements equal to 0	Return 0, as there are no bars to trap any water.
Array with all elements having the same non-zero value	Return 0, as there is no variation in height to trap water.
Array with only one peak element (all other elements are lower)	The algorithm should correctly calculate water trapped on either side of the peak.
Monotonically increasing or decreasing array	Return 0, as there are no dips to hold water.
Large height values leading to potential integer overflow	Use a data type (e.g., long) that can accommodate larger values to prevent overflow during calculations.
Array with very large size impacting performance	The solution should have a time complexity of O(n) to scale efficiently with larger inputs; space complexity considerations are also important.