Tuesday, August 18, 2015

Trapping Rain Water

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.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
The above elevation map 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
Simple approach is to find rightmax and leftmax of every element and determine the excess water, it can be calculated by formula:
trap_water_on_current_bar = min(leftmax, rightmax) - current_value

int findWater(int arr[], int n)
    int *max_left = new int[n] ;
    int *max_right = new int[n];
    int water = 0;
    // Fill left array
    left[0] = arr[0];
    for (int i = 1; i < n; i++)
       left[i] = max(left[i-1], arr[i]);
    // Fill right array
    right[n-1] = arr[n-1];
    for (int i = n-2; i >= 0; i--)
       right[i] = max(right[i+1], arr[i]);
    // Calculate the accumulated water element by element
    // consider the amount of water on i'th bar, the
    // amount of water accumulated on this particular
    // bar will be equal to min(left[i], right[i]) - arr[i] .
    for (int i = 0; i < n; i++)
       water += min(left[i],right[i]) - arr[i];
    return water;

Source:- LeetCode, GeeksForGeeks


  1. can u post some Tic-tac-toe related interview Question???

  2. I prefer to read this kind of stuff. The quality of content is fine and the conclusion is good. Thanks for the post

    windows blinds suppliers in india