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

Examples:

Input: arr[]   = {2, 0, 2}
Output: 2
Explanation:
The structure is like below

We can trap 2 units of water in the middle gap.

METHOD 1

import org.junit.Test;

import static org.junit.Assert.assertEquals;

/**
 * Question   : Trapping rain water
 * Complexity : Time: O(n) ; Space: O(1)
 * Time       : 2020/06/10
 * Author     : Max
 */
public class TrappingRainWater {
    static int maxWater(int[] arr) {
        if (arr.length == 0) {
            return 0;
        }

        int n = arr.length;

        int leftMax = Integer.MIN_VALUE, rightMax = Integer.MIN_VALUE;
        int l = 0, h = n - 1;
        int trap = 0;

        while (l < h) {
            if (arr[l] < arr[h]) {
                if (arr[l] > leftMax) {
                    leftMax = arr[l];
                } else {
                    trap += leftMax - arr[l];
                }
                l++;
            } else {
                if (arr[h] > rightMax) {
                    rightMax = arr[l];
                } else {
                    trap += rightMax - arr[h];
                }
                h--;
            }
        }

        return trap;
    }

    @Test
    public void test() {
        assertEquals(2, maxWater(new int[]{2, 0, 2}));
        assertEquals(7, maxWater(new int[]{3, 0, 2, 0, 4}));
        assertEquals(6, maxWater(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
    }
}