Solving Trapping Rain Water Problem (with C++ & Java code)

1. Traverse the array from beginning to end:
2. For every element: 
       -Traverse the array from start to that index and find the maximum height (h1)
       -Traverse the array from the present index to the end, and find the maximum height (h2).
3. The volume of water that will be stored in this column is min(h1,h2) – array[i], add the value to total water stored.
4. Print the answer.

1. Create two arrays left[] and right[] of size n. 
2. Create a variable (say maximum) to store the maximum water till a certain index during traversing the array.
3. Run one loop from beginning to end: 
       -In each iteration update maximum and also assign left[i] = maximum.
4. Run another loop from end to beginning: 
       -In each iteration update maximum found till now and also assign right[i] = maximum.
5. Traverse the array from beginning to end.
6. The total amount of water that will be stored in this column is min(left[i], right[i]) – array[i]
7. The value that came will be added to the total water amount.
8. Print the answer.

1. Loop through the indices of the bar array.
2. For each bar, do the following steps:
       -Loop while the Stack is not empty and the current bar has a height greater than the top bar of the stack,
       -Store the index of the top bar in pop_height and pop it from the Stack.
       -Find the distance between the left bar(current top) of the popped bar and the current bar.
       -Find the minimum height between the top bar and the current bar.
       -The maximum water that can be trapped is distance * min_height.
       -The water trapped, including the popped bar, is (distance * min_height) – height[pop_height].
       -Add that to the answer.
3. Return the amount received as the total amount of water

1. Find the total number of blocks, i.e., the sum of the heights array, num_blocks
2. Find the maximum height, max_height
3. Store total water in a variable, total = 0
4. Keep two pointers, left = 0 and right = N -1, to store the leftmost and the rightmost boundaries for each unit of height
5. For each height, i from 1 to max_height, do the following
6. Find the leftmost and the rightmost boundary for the current height.
7. As mentioned earlier we can consider all the blocks in between these to have at least i unit of water.
8. Add this amount of water to the total trapped water.
9. After the iteration is over, subtract num_blocks from total as we have considered them as water height during calculation.

1. Take two pointers l and r. 
2. Initialize l to the starting index 0 and r to the last index N-1.
3. Since l is the first element, left_max would be 0, and right_max for r would be 0.
While l ≤ r, iterate the array. 
4. We have two possible conditions
Condition1 : left_max <= right max
    -Consider Element at index l
    -Since we have traversed all elements to the left of l, left_max is known 
    -For the right max of l, We can say that the right max would  always be >= current r_max here
    -So, min(left_max,right_max) would always equal to left_max in this case
    -Increment l.

Condition2 : left_max > right max
    -Consider Element at index r
    -Since we have traversed all elements to the right of r, right_max is known
    -For the left max of l, We can say that the left max would  always be >= current l_max here
    -So, min(left_max,right_max) would always equal to right_max in this case
    -Decrement r.

1. Loop from index 0 to the end of the given array.
    -If a bar greater than or equal to the previous bar is encountered, then store the index of that bar (say prev_index).
    -Keep adding the previous bar’s height minus the current (ith) bar to the final answer.
    -Have a temporary variable to store the amount of water in the current segment.
    -If no bar greater than or equal to the previous bar is found, then quit.
2. If prev_index < size of the input array, then subtract the temporary variable from the answer, because we have considered the last segment that has no higher right bound.
    -Loop from the end of the input array to prev_index.
    -Find a bar greater than or equal to the previous bar (in this case, the last bar from backward).

#include <bits/stdc++.h>
using namespace std;

int maximumWater(int arr[], int n)
{
	int size = n - 1;
	int prev = arr[0];

	int prev_index = 0;
	int wat = 0;
	int temp = 0;

	for (int i = 1; i <= size; i++) {

		if (arr[i] >= prev) {
			prev = arr[i];
			prev_index = i;
			temp = 0;
		}
		else {
			wat += prev - arr[i];
			temp += prev - arr[i];
		}
	}

	if (prev_index < size) {

		wat -= temp;
		prev = arr[size];
		for (int i = size; i >= prev_index; i--) {
			if (arr[i] >= prev) {
				prev = arr[i];
			}
			else {
				wat += prev - arr[i];
			}
		}
	}
	return wat;
}

int main()
{
	int arr[] = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
	int n = sizeof(arr) / sizeof(arr[0]);
	cout << maximumWater(arr, n);
	return 0;
}

class Solution {
	public static int maximumWater(int arr[], int n)
	{
		int size = n - 1;
		int prev = arr[0];
		int prev_index = 0;
		int water = 0;
		int temp = 0;
		for (int i = 1; i <= size; i++) {
			if (arr[i] >= prev) {
				prev = arr[i];
				prev_index = i;
				temp = 0;
			}
			else {
				water += prev - arr[i];
				temp += prev - arr[i];
			}
		}
		if (prev_index < size) {
			water -= temp;
			prev = arr[size];
			for (int i = size; i >= prev_index; i--) {
				if (arr[i] >= prev) {
					prev = arr[i];
				}
				else {
					water += prev - arr[i];
				}
			}
		}
		return water;
	}

	public static void main(String[] args)
	{
		int arr[] = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
		int n = arr.length;
		System.out.print(maximumWater(arr, n));
	}
}

6