Trapping Rain Water

                                            
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        if (n == 0) {
            return 0;
        }
        
        vector<int> leftMax(n), rightMax(n);
        leftMax[0] = height[0];
        rightMax[n - 1] = height[n - 1];
        
        for (int i = 1; i < n; i++) {
            leftMax[i] = max(leftMax[i - 1], height[i]);
        }
        
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = max(rightMax[i + 1], height[i]);
        }
        
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += min(leftMax[i], rightMax[i]) - height[i];
        }
        
        return ans;
    }
};

                                            
class Solution {
    public int trap(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        
        int n = height.length;
        int left = 0, right = n - 1;
        int leftMax = 0, rightMax = 0;
        int res = 0;
        
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    res += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    res += rightMax - height[right];
                }
                right--;
            }
        }
        
        return res;
    }
}

                                            
class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if not height:
            return 0
        
        left_max = [0] * len(height)
        right_max = [0] * len(height)
        left_max[0] = height[0]
        right_max[-1] = height[-1]
        
        for i in range(1, len(height)):
            left_max[i] = max(left_max[i-1], height[i])
        
        for i in range(len(height) - 2, -1, -1):
            right_max[i] = max(right_max[i+1], height[i])
            
        total_water = 0
        for i in range(1, len(height) - 1):
            water_level = min(left_max[i], right_max[i])
            if water_level > height[i]:
                total_water += water_level - height[i]
        
        return total_water

                                            
int trap(int* height, int heightSize) {
    int left = 0, right = heightSize - 1;
    int leftMax = 0, rightMax = 0;
    int totalWater = 0;
    
    while (left < right) {
        if (height[left] <= height[right]) {
            if (height[left] >= leftMax) {
                leftMax = height[left];
            } else {
                totalWater += leftMax - height[left];
            }
            left++;
        } else {
            if (height[right] >= rightMax) {
                rightMax = height[right];
            } else {
                totalWater += rightMax - height[right];
            }
            right--;
        }
    }
    
    return totalWater;
}

                                            
public class Solution {
    public int Trap(int[] height) {
        int n = height.Length;
        if (n == 0) {
            return 0;
        }
        
        int left = 0;
        int right = n - 1;
        int leftMax = 0;
        int rightMax = 0;
        int result = 0;
        
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    result += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    result += rightMax - height[right];
                }
                right--;
            }
        }
        
        return result;
    }
}

                                            
/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    let left = 0;
    let right = height.length - 1;
    let leftMax = 0;
    let rightMax = 0;
    let result = 0;

    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= leftMax) {
                leftMax = height[left];
            } else {
                result += leftMax - height[left];
            }
            left++;
        } else {
            if (height[right] >= rightMax) {
                rightMax = height[right];
            } else {
                result += rightMax - height[right];
            }
            right--;
        }
    }

    return result;
};

                                            
function trap(height: number[]): number {
    let left = 0;
    let right = height.length - 1;
    let leftMax = 0;
    let rightMax = 0;
    let result = 0;

    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= leftMax) {
                leftMax = height[left];
            } else {
                result += leftMax - height[left];
            }
            left++;
        } else {
            if (height[right] >= rightMax) {
                rightMax = height[right];
            } else {
                result += rightMax - height[right];
            }
            right--;
        }
    }

    return result;
};

                                            
class Solution {
    /**
     * @param Integer[] $height
     * @return Integer
     */
    function trap($height) {
        $n = count($height);
        if ($n == 0) return 0;
        
        $left = 0;
        $right = $n - 1;
        $leftMax = 0;
        $rightMax = 0;
        $result = 0;
        
        while ($left < $right) {
            if ($height[$left] < $height[$right]) {
                if ($height[$left] >= $leftMax) {
                    $leftMax = $height[$left];
                } else {
                    $result += $leftMax - $height[$left];
                }
                $left++;
            } else {
                if ($height[$right] >= $rightMax) {
                    $rightMax = $height[$right];
                } else {
                    $result += $rightMax - $height[$right];
                }
                $right--;
            }
        }
        
        return $result;
    }
}

                                            
class Solution {
    func trap(_ height: [Int]) -> Int {
        var left = 0
        var right = height.count - 1
        var leftMax = 0
        var rightMax = 0
        var result = 0
        
        while left < right {
            if height[left] < height[right] {
                if height[left] >= leftMax {
                    leftMax = height[left]
                } else {
                    result += leftMax - height[left]
                }
                left += 1
            } else {
                if height[right] >= rightMax {
                    rightMax = height[right]
                } else {
                    result += rightMax - height[right]
                }
                right -= 1
            }
        }
        
        return result
    }
}

                                            
class Solution {
    fun trap(height: IntArray): Int {
        var left = 0
        var right = height.size - 1
        var leftMax = 0
        var rightMax = 0
        var result = 0
        
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left]
                } else {
                    result += leftMax - height[left]
                }
                left++
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right]
                } else {
                    result += rightMax - height[right]
                }
                right--
            }
        }
        
        return result
    }
}

                                            
class Solution {
  int trap(List<int> height) {
    if (height.isEmpty) return 0;
    
    int left = 0;
    int right = height.length - 1;
    int leftMax = 0;
    int rightMax = 0;
    int trappedWater = 0;
    
    while (left < right) {
      if (height[left] < height[right]) {
        if (height[left] >= leftMax) {
          leftMax = height[left];
        } else {
          trappedWater += leftMax - height[left];
        }
        left++;
      } else {
        if (height[right] >= rightMax) {
          rightMax = height[right];
        } else {
          trappedWater += rightMax - height[right];
        }
        right--;
      }
    }
    
    return trappedWater;
  }
}

                                            
func trap(height []int) int {
    if len(height) == 0 {
        return 0
    }

    leftMax := make([]int, len(height))
    rightMax := make([]int, len(height))
    trappedWater := 0

    leftMax[0] = height[0]
    for i := 1; i < len(height); i++ {
        leftMax[i] = max(leftMax[i-1], height[i])
    }

    rightMax[len(height)-1] = height[len(height)-1]
    for i := len(height) - 2; i >= 0; i-- {
        rightMax[i] = max(rightMax[i+1], height[i])
    }

    for i := 0; i < len(height); i++ {
        trappedWater += min(leftMax[i], rightMax[i]) - height[i]
    }

    return trappedWater
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

                                            
# @param {Integer[]} height
# @return {Integer}
def trap(height)
    return 0 if height.nil? || height.length == 0
    
    left = 0
    right = height.length - 1
    left_max = 0
    right_max = 0
    result = 0
    
    while left < right
        if height[left] < height[right]
            if height[left] >= left_max
                left_max = height[left]
            else
                result += left_max - height[left]
            end
            left += 1
        else
            if height[right] >= right_max
                right_max = height[right]
            else
                result += right_max - height[right]
            end
            right -= 1
        end
    end
    
    return result
end

                                            
object Solution {
    def trap(height: Array[Int]): Int = {
        var left = 0
        var right = height.length - 1
        var leftMax = 0
        var rightMax = 0
        var result = 0
        
        while (left < right) {
            if (height(left) < height(right)) {
                if (height(left) >= leftMax) {
                    leftMax = height(left)
                } else {
                    result += leftMax - height(left)
                }
                left += 1
            } else {
                if (height(right) >= rightMax) {
                    rightMax = height(right)
                } else {
                    result += rightMax - height(right)
                }
                right -= 1
            }
        }
        
        result
    }
}

                                            
impl Solution {
    pub fn trap(height: Vec<i32>) -> i32 {
        let mut left = 0;
        let mut right = height.len() - 1;
        let mut left_max = 0;
        let mut right_max = 0;
        let mut result = 0;

        while left < right {
            if height[left] < height[right] {
                if height[left] >= left_max {
                    left_max = height[left];
                } else {
                    result += left_max - height[left];
                }
                left += 1;
            } else {
                if height[right] >= right_max {
                    right_max = height[right];
                } else {
                    result += right_max - height[right];
                }
                right -= 1;
            }
        }

        result
    }
}

To solve this coding challenge of calculating the amount of trapped rainwater in a given elevation map, we can utilize the concept of finding the maximum heights to the left and right of each element in the array. By comparing these maximum heights, we can determine the water level at each position. Below is a # Explanation section that thoroughly elaborates on the solution along with detailed pseudocode with comments.

Explanation:

Understanding the Problem : The input is an array where each element’s value represents the height of bars at each index. Our task is to calculate how much water can be trapped between these bars after it rains. The water trapped at a position depends on the heights of bars to its left and right.
Calculate Maximum Heights From Left and Right :

For each position in the array, you need to know the highest bar on its left and the highest bar on its right.
Left_max

: Create an array where each position will store the maximum height observed from the left side up to that position.
Right_max

: Similarly, create another array where each position will store the maximum height observed from the right side up to that position.

Water Level Calculation :

For each position, the water level is determined by the minimum of the maximum heights from the left and right.
If this water level is higher than the height of the bar at that position, the difference (water level minus bar height) is the amount of water that can be stored at that position.

Summing Up the Water Trapped :

Sum up the water trapped at each position to get the total amount of trapped water.

Detailed Steps with Pseudocode:

Early Exit :

If the array is empty, immediately return 0, because no water can be trapped in an empty array.

                                            
# Check if the height array is empty
if height array is empty:
return 0

Initialize Arrays :

Create two arrays,
left_max

and
right_max

, each of the same length as the input array.
Initialize the first element of
left_max

to the first element of the input array.
Initialize the last element of
right_max

to the last element of the input array.

                                            
# Initialize left_max and right_max arrays
set left_max to an array of zeros of the same length as the height array
set right_max to an array of zeros of the same length as the height array

# Initialize the first element of left_max and the last element of right_max
left_max[0] = height[0]
right_max[-1] = height[-1]

Fill Left_max Array :

Iterate through the height array from the second element to the last.
For each position, set
left_max[i]

to the maximum of
left_max[i-1]

and
height[i]

.

                                            
# Fill the left_max array
for each element in height array starting from the second element:
left_max[i] = maximum of left_max[i-1] and height[i]

Fill Right_max Array :

Iterate through the height array from the second last element to the first.
For each position, set
right_max[i]

to the maximum of
right_max[i+1]

and
height[i]

.

                                            
# Fill the right_max array
for each element in height array starting from the second last element to the first:
right_max[i] = maximum of right_max[i+1] and height[i]

Calculate Total Trapped Water :

Initialize
total_water

to 0.
Iterate through the height array excluding the first and last elements (since water cannot be trapped at the edges).
For each position, calculate the water level as the minimum of
left_max[i]

and
right_max[i]

.
If this water level is greater than the height at that position, add the difference to
total_water

.

                                            
# Initialize total trapped water to 0
total_water = 0

# Calculate water trapped at each position
for each element in height array excluding the first and last elements:
water_level = minimum of left_max[i] and right_max[i]
if water_level > height[i]:
total_water += water_level - height[i]

Return Result :

Return the
total_water

which is the sum of water trapped at all positions.

                                            
# Return the total trapped water
return total_water

This algorithm ensures that by making two passes through the height array to fill the

left_max

and

right_max

arrays, and one more pass to calculate the trapped water, we run efficiently even for large arrays. With this detailed explanation and pseudocode, you can clearly understand the logic and easily implement it in any programming language.