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
Solution:
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

Implementation:
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

2 comments:

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

    ReplyDelete
  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

    ReplyDelete