Arrays - Trapping Rainwater - Optimal Solution using 2 Pointer Approach

Question: Given an array of integers representing an elevation map (bar chart) where width of each bar is 1, return how much rain water can be trapped in empty space after raining?

input [0,1,0,2,1,0,3,1,0,1,2]
output 8

Constraints need to ask because solution may change according to given constraints

Question: Sides of graph can be count as wall?
Answer: No

Question: Will there be negative integers?
Answer: No

Question: What will be output for empty array?
Answer: 0

Question: What will be output when only 1 value in array?
Answer: 0

Question: What will be output when input array like [3,4,3]?
Answer: 0, no empty space to store water because walls cannot be used and water also fells from right side.

Note: Max water can go to the mark is minimum height of bar between 2 bars and if there is a small bar present in between it will reduce the water quantity as shown in above image with black color.

Solution in JAVA language - 2 Pointer Approach with Linear Time Complexity

* 1. Identify Pointer with lesser value.
* 2. Is the pointer value greater than or equal to max on that side YES -> update max on that side NO -> Get the water and update on total water
* 3. Move the pointer inwards
* 4. Repeat for other side

* formula: currentWater = maxSideValue - currentHeight
* currentWater - water present at integer which we want to calculate
* maxSideValue = maxValue of respective side either left or right
* currentHeight - Height of currentWater

public class TrappingRainwaterOptimal {
    
    public static int getTrappedRainwater(int[] arr) {

        int length = arr.length;
        int maxLeft = 0, maxRight = 0, totalWater = 0, pL = 0, pR = length - 1;
        while (pL < pR) {
            int leftPointerValue = arr[pL];
            int rightPointerValue = arr[pR];
            if (leftPointerValue <= rightPointerValue) {
                if (leftPointerValue >= maxLeft) {
                    maxLeft = leftPointerValue;
                } else {
                    totalWater += maxLeft - leftPointerValue;
                }
                pL++;
            } else {
                if (rightPointerValue >= maxRight) {
                    maxRight = rightPointerValue;
                } else {
                    totalWater += maxRight - rightPointerValue;
                }
                pR--;
            }
        }
        return totalWater;
    }

    public static void main(String[] args) {
        int[] input = new int[]{0,1,0,2,1,0,3,1,0,1,2};
        int trappedRainwater = TrappingRainwaterOptimal.getTrappedRainwater(input);
        System.out.println("Total Trapped water is: " + trappedRainwater);
    }
}           

Output: 8

Time Complexity: O(N)

Space Complexity: O(1)

Runtime: 0ms, 100% faster than other Java Online Submissions for Trapping rainwater

problem, as per leetcode.

For easy brute force solution click here

Note: Find question at Leetcode