#### Problem Description:

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`

^{4}`0 <= height[i] <= 10`

^{5}

##### Problem Link :Trapping Rain Water – LeetCode

##### Solution(s):

##### Approach 1: Brute Force Solution

##### Java Code:

```
public int trap(int[] height) {
int maxWater=0;
int leftMax=0,rightMax=0;
for(int i=1;i<height.length-1;i++) {
//find max from left of height[i]
leftMax=height[i];
for(int j=0;j<i;j++) {
leftMax = Math.max(leftMax, height[j]);
}
//find max from right of height[i]
rightMax=height[i];
for(int j=i+1;j<height.length;j++) {
rightMax = Math.max(rightMax, height[j]);
}
// Update maximum water value
maxWater += Math.min(leftMax, rightMax) - height[i];
}
return maxWater;
}
```

## Explanation:

### 1.**Initialization**:

`maxWater`

: This accumulates the total amount of water trapped between the heights.`leftMax`

,`rightMax`

: These variables store the maximum height values to the left and right of each current index`i`

.

### 2.**Main Loop**:

- The loop starts from
`i = 1`

to`height.length - 2`

, skipping the first and last bars (since no water can be trapped outside the array).

### 3.**Finding Maximum Height to the Left**:

- For each
`i`

, a nested loop runs from`0`

to`i - 1`

to find the maximum height (`leftMax`

) among all heights left of`height[i]`

.

### 4.**Finding Maximum Height to the Right**:

- Similarly, another nested loop runs from
`i + 1`

to the end of the array to find the maximum height (`rightMax`

) among all heights right of`height[i]`

.

### 5.**Calculating Water at Index **`i`

:

`i`

- For each index
`i`

, the trapped water is determined by the difference between the smaller of the two maximum heights (`leftMax`

and`rightMax`

) and the current height (`height[i]`

). - This difference is added to
`maxWater`

.

### 6.**Final Result**:

- After the loop completes, the total amount of trapped water is stored in
`maxWater`

and returned as the result.

##### Complexity:

- Time-Complexity: O(n²) because for each element
`i`

, two nested loops are used to find`leftMax`

and`rightMax`

, both running in**O(n)**. Hence, the total time complexity is**O(n) * O(n) = O(n²)**. - Space-Complexity: O(1)

## Optimization Opportunity:

This brute-force approach can be optimized by using dynamic programming or the two-pointer technique, reducing the time complexity to **O(n)**. The version I shared earlier using the two-pointer technique is one such optimization.

##### Approach 2: Using Two Pointers

- Create two pointers leftPtr and rightPtr and two other variables maxLeft and maxRight
- Loop until leftPtr and rightPtr meet.
- If hight[leftPtr] is smaller or equal to height[rightPtr],
- then if height[leftPtr] is less than equal to maxLeft, update maxLeft to height[leftPtr] else add the difference between maxLeft and height[leftPtr] to result. and move leftPtr to right.
- else, if height[leftPtr] is greater than height[rightPtr],
- then if height[rightPtr] is greater than equal to maxRight, update maxRight to height[rightPtr] else add the difference between maxRight and height[rightPtr] to result. and move rightPtr to left.
- return the result

##### Java Code:

```
public int trap(int[] height) {
int n = height.length;
//left and right pointers
int leftPtr = 0;
int rightPtr = n-1;
int result = 0;
int maxleft = 0;
int maxright = 0;
// loop until left and right pointers meet
while(leftPtr <= rightPtr){
// if height[left] is smaller or equal to height[right]
if(height[leftPtr] <= height[rightPtr]){
if(height[leftPtr] >= maxleft){
maxleft = height[leftPtr];
}
else{
result += maxleft - height[leftPtr];
}
leftPtr++;
}
// if height[left] is greater than height[right]
else{
if(height[rightPtr] >= maxright){
maxright = height[rightPtr];
}
else{
result += maxright - height[rightPtr];
}
rightPtr--;
}
}
return result;
}
```

##### Complexity:

- Time-Complexity: O(n)
- Space-Complexity:O(1)