# 1. Introduction

In this post, we explore a solution to the "Trapping Rain Water" problem, which is a fascinating question in the realm of array and two-pointer techniques. The problem involves calculating the total amount of rainwater that can be trapped between bars of varying heights, represented as an array.

## Problem

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

# 2. Solution Steps

1. Initialize two pointers *left* and *right* at the beginning and end of the array, respectively.

2. Maintain two variables *leftMax* and *rightMax* to keep track of the maximum height seen so far from the left and right.

3. Iterate through the array using the two pointers:

a. Update *leftMax* and *rightMax* as the maximum height seen so far from each side.

b. If *height[left] < height[right]*, water trapped on the current bar is *leftMax - height[left]*. Add this to the total water trapped and move *left* pointer forward.

c. Else, water trapped on the current bar is *rightMax - height[right]*. Add this to the total water trapped and move *right* pointer backward.

4. Continue this process until *left* and *right* pointers meet.

5. Return the total amount of water trapped.

# 3. Code Program

```
public class TrappingRainWater {
public static void main(String[] args) {
int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
System.out.println(trap(height)); // Test the function
}
// Function to calculate the total water trapped
public static int trap(int[] height) {
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
int trappedWater = 0;
while (left < right) {
if (height[left] < height[right]) {
leftMax = Math.max(leftMax, height[left]);
trappedWater += leftMax - height[left];
left++;
} else {
rightMax = Math.max(rightMax, height[right]);
trappedWater += rightMax - height[right];
right--;
}
}
return trappedWater;
}
}
```

### Output:

6

### Explanation:

1. *trap*: This function computes the total amount of rainwater that can be trapped.

2. Two-pointer technique is used, with *left* and *right* pointers starting from the beginning and end of the array, respectively.

3. *leftMax* and *rightMax* keep track of the maximum heights encountered so far from the left and right.

4. The function calculates water trapped at each bar based on the minimum of *leftMax* and *rightMax* and the current height.

5. The pointers are moved inward, updating *leftMax* and *rightMax* and accumulating trapped water.

6. The process continues until the *left* and *right* pointers meet, covering all possible locations for trapping water.

7. This method effectively computes the trapped water with O(n) time complexity and O(1) space complexity, making it an optimal solution.

## Comments

## Post a Comment