Trapping Rain Water

This page explains Java solution to problem Trapping Rain Water using Array data structure.

Problem Statement

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.

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Solution

package com.vc.hard;

class TrappingRainWater {
    public int trap(int[] arr) {
        int n = arr.length;
        int left = 0;
        int right = n - 1;
        int res = 0;
        int maxLeft = 0;
        int maxRight = 0;
        while(left <= right) {
            if(arr[left] <= arr[right]) {
                if(maxLeft < arr[left]) maxLeft = arr[left];
                else res += maxLeft - arr[left];
                left++;
            }
            else {
                if(maxRight < arr[right]) maxRight = arr[right];
                else res += maxRight - arr[right];
                right--;
            }
        }
        return res;
    }
}

Time Complexity

O(N)
Where N is total number of elements in an input array

Space Complexity

O(1)