CareerCup

For each index, calculate what the tallest point in the histogram preceding that index is. This is easy and O(n) because max_before[n] = max (max_before[n-1], histogram[n]). Now, also for each index, calculate a similar max_after array (calculate from the back using max_after[n] = max (histogram[n], max_after[n+1])). Now, for each index n, water_height[n] = min (max_before[n], max_after[n]). At this point, loop over the indices i = 0...n-2 and do:

if (water_level[i].floatingPointEquals(water_level[i+1]))
{    area += (water_level[i] - (histogram[i] + histogram[i+1]) / 2);    }
//on a water level transition we have to be careful about where a water level ends
else {
    //this all makes sense if you draw it out
    double lowerWaterHeight = min (waterLevel[i], waterLevel[i+1]);
    double lowerLandHeight = min (histogram[i], histogram[i+1]);
    double waterHeightFromBase = lowerWaterHeight - lowerLandHeight;
    double fractionOfTile = waterHeightFromBase  / abs(histogram[i+1] - histogram[i]);
    area += (fractionOfTile * waterHeightFromBase  / 2);
}

Edit: This calculation is for the case when the histogram is represented as a line graph, not a bar graph. In the case of a bar graph, you can use the same technique and the logic will be very similar (the formula will actually be simpler).

The algorithm is linear time overall.

The first solution takes O(n) space as well as O(n) time. By doubling the time (the time complexity will still be O(n)), we can also find out the volume.
For the sake of simplicity, let us assume that the area of cross-section of each histogram is 1 square unit. Then, the volume of water = Total height of water above all the towers cubic units. The height of water above any given tower is determined by the following formula:
heightOfWater[i] = max(min(LeftMax[i],RightMax[i]) - height[i], 0).

Now, we can look at it as follows. Move from left to right. Start from the left most maximum (the first tower), and move right. All the towers that have lesser height than that will have some amount of water above it, provided there is another tower of height >= it. Consider two towers this way, i and j, such that i < j, and height[i] < height[j] and for all k < j and k > i, height [k] < height[j]. Then, the height of water above each tower is calculated using the formula:
heightOfWater[k] = height[i] - height[k].
totalHeightOfWater += height[i] - height[k].
Then set i = j and find the next j. If there is no j, then stop.

Now, start moving from the right to the left and do the same, with i > j, and height[i] < height[j] and for all k < i and k > j, height [k] < height[j]. Then, the height of water above each tower is calculated using the formula:
heightOfWater[k] = height[i] - height[k].
totalHeightOfWater += height[i] - height[k].
Then set i = j and find the next j. If there is no j, then stop.

We can calculate the total height of water, while we are calculating individual heights.

Here is a solution which I believe should be more readable

Credits to Tristan (Tristan's collection of Interview Question) for his approach

int FillWater(int* histogram, int length)
{
    int waterCollected = 0;
    int *maxLeft = new int [length];
    int *maxRight = new int [length];

    //For each values, calculate the maximum value to its left
    maxLeft[0] = 0;
    for(int i = 1; i < length; i++)
    {
        maxLeft[i] = max(histogram[i-1], maxLeft[i-1]);
    }

    //For each values, calculate the maximum value to its right
    maxRight[length-1] = 0;
    for(int i = length - 2; i >= 0; i--)
    {
        maxRight[i] = max(histogram[i+1], maxRight[i+1]);
    }

    //At each index, water collected will be collected, if it is a dip
    //Amount of water collected will be [min(maxLeft[i], maxRight[i]) - value at that index]
    for(int i = 0; i < length; i++)
    {
        if(maxLeft[i] > histogram[i] && maxRight[i] > histogram[i])
        {
            waterCollected += (min(maxLeft[i], maxRight[i]) - histogram[i]);
        }
    }
    delete[] maxLeft;
    delete[] maxRight;
    return waterCollected;
}

The above solution takes constant space, if we don't store the intermediate values of height[k]. However, it requires 2 passes of the array, and hence double the time.

Time complexity: O(N)

int findTrappedWater(int* H,int size)
{
        int i,j,water=0,temp;
        for(i=0;i<size;)
        {
                j=i+1;
                temp=0;
                while(j<size && H[i]>H[j])
                {
                        temp+=H[j];
                        j++;
                }
                if(j!=size) // decreasing length histogram
                        water+=(j-i-1)*H[i]-temp;
                i=j;
        }
        return water;
}

Complete code here: ideone.com/xCsHn

On similar lines, this should work

/* Set previous and next values for all buildings */
void SetPrevNext()
{
    int i, max_height = -1;
    prev[0] = -1;
    next[n-1] = -1;
    /* Set previous values */
    for (i=1;i<n;i++)
    {
        if(h[i-1]>h[i])            /* If height of prvious building is more */
        {
            prev[i] = i-1;
        }
        else if(h[i]<h[prev[i-1]]) /*Check previous height */
        {
            prev[i]=prev[i-1];
        }
        else if(max_height > -1 && h[i]<h[max_height])  /* Local Maximum height */
        {
            prev[i] = max_height;
        }
        else                                            /* heighest tower */
        {
            prev[i] = -1;
            max_height = i;
        }
    }

    /* Set next heights */
    max_height = -1;
    for (i=n-2;i>=0;i--)
    {
        if(h[i+1]>h[i])             /* height of next tower is more */
        {
            next[i] = i+1;
        }
        else if(h[i]<h[next[i+1]])
        {
            next[i]= next[i+1];
        }
        else if(max_height > -1 && h[i]<h[max_height]) /* local maximum tower height */
        {
            next[i] = max_height;
        }
        else                                           /* heighes tower */
        {
            next[i] = -1;
            max_height = i;
        }
    }
}

int FillWater()
{
    int i, total_water = 0;
    int height, width;
    for (i=1;i<n-1;i++)
    {
        if(prev[i]>0 && next[i]>0)
        {
            /*height of water based on smaller next or previous tower */
            height = (h[prev[i]]<h[next[i]])?(h[prev[i]]-h[i]):(h[next[i]]-h[i]);

            /* Width spanning the previos and next towers */
            width = (next[i]-prev[i]-1)*W;

            //printf("\nHeight : %d, Width : %d for %d",height, width, h[i]);
            total_water += (height * width);
        }
    }
    return total_water;
}

/**
 * find water captured between towers
 * works perfactly and complexity is O(n)
 */
long int getWaterStorage(std::vector<long int> const & towers) {
  if(towers.size() < 3) return 0;
  int i = 1;
  long int water= 0;

  while(i<towers.size()) {
    //first find last element in ascending order
    while(i<towers.size() && towers[i-1]<=towers[i]) ++i;
    int s = i-1;
    //second find last element in discending order
    while(i<towers.size() && towers[i-1]>=towers[i]) ++i;
    int m = i -1;
    if(s == m) break;
    //third find last element in ascending order
    while(i<towers.size() && towers[i-1]<=towers[i]) ++i;
    int e = i -1;
    if(m == e) break;
    water += std::min(towers[s], towers[e]) - towers[m];
  }

  return water;
}
int main() {

  std::vector<long int> v;
  int n;
  //read size of v
  std::cin>>n;
  //read v array
  for(int i =0;i<n;++i)
  {
    long int e;
    std::cin>>e;
    v.push_back(e);
  }

  std::cout<<getWaterStorage(v)<<std::endl;

  return 0;
}

areeb$ ./a.out 
3  << this is size of the array
2 1 3 << these are element separated by space
1  << output

areeb$ ./a.out 
3
1 2 3
0

areeb$ ./a.out 
3
3 2 1
0

areeb$ ./a.out 
3
3 1 2
1

/**
 * find water captured between towers
 * works perfactly and complexity is O(n)
 */
long int getWaterStorage(std::vector<long int> const & towers) {
  if(towers.size() < 3) return 0;
  int i = 1;
  long int water= 0;

  while(i<towers.size()) {
    //first find last element in ascending order
    while(i<towers.size() && towers[i-1]<=towers[i]) ++i;
    int s = i-1;
    //second find last element in discending order
    while(i<towers.size() && towers[i-1]>=towers[i]) ++i;
    int m = i -1;
    if(s == m) break;
    //third find last element in ascending order
    while(i<towers.size() && towers[i-1]<=towers[i]) ++i;
    int e = i -1;
    if(m == e) break;
    water += std::min(towers[s], towers[e]) - towers[m];
  }

  return water;
}


int main() {

  std::vector<long int> v;
  int n;
  //read size of v
  std::cin>>n;
  //read v array
  for(int i =0;i<n;++i)
  {
    long int e;
    std::cin>>e;
    v.push_back(e);
  }

  std::cout<<getWaterStorage(v)<<std::endl;

  return 0;
}


areeb$ ./a.out 
3   << this is number of elements in the array
2 1 3  << array, all element on one line space sparated
1  << output
areeb$ ./a.out 
3
1 2 3
0
areeb@$ ./a.out 
3
3 2 1
0
areeb$ ./a.out 
3
3 1 2
1

# O(n) time, O(1) space
def area(heights):
ret = 0
cur_valley_area = 0
max_so_far = 0
index_of_max_so_far = -1

for i, h in enumerate(heights):
if h < max_so_far:
cur_valley_area += max_so_far - h
else:
ret += cur_valley_area
max_so_far = h
index_of_max_so_far = i
cur_valley_area = 0

# add everything that comes after (to the right of) the max height in the array
max_right_so_far = 0
for i in xrange(len(heights) - 1, index_of_max_so_far, -1):
h = heights[i]
max_right_so_far = max(h, max_right_so_far)
ret += max_right_so_far - h

return ret

# O(n) time, O(1) space
def area(heights):
  ret = 0
  cur_valley_area = 0
  max_so_far = 0
  index_of_max_so_far = -1

  for i, h in enumerate(heights):
    if h < max_so_far:
      cur_valley_area += max_so_far - h
    else:
      ret += cur_valley_area
      max_so_far = h
      index_of_max_so_far = i
      cur_valley_area = 0

  # add everything that comes after (to the right of) the max height in the array
  max_right_so_far = 0
  for i in xrange(len(heights) - 1, index_of_max_so_far, -1):
    h = heights[i]
    max_right_so_far = max(h, max_right_so_far)
    ret += max_right_so_far - h

  return ret

A solution with linear time (2 passes), constant space.
Loop to find the local maxima (aka towers). A local maximum is bigger than the element before and the element after, or it is an edge element (first / last) and bigger than the one after / before respectively. Take into account maximum with more than one column (columns are equal). Store the maxima locations in a pair vector (if single column maximum, both values of the pair are equal).
If you have less than 2 maxima, return 0 - no water kept.
Loop on the maxima locations, two at a time (looking at the valley between). The water kept between two maxima is the difference between the histogram value and the smaller of the two maxima values, floored by 0.

A discrete graph can be partitioned into alternating increasing and decreasing runs optionally interspersed with optional runs. Define a valley as a decreasing run followed by an optional number of constant runs followed by an increasing run. The height of the valley is the minimum of its leftmost point (the highest point on the decreasing run) and its rightmost point (the highest point on the increasing run). Its length is the total number of elements in its constituent runs. A valley's basin is its height times its length, which is the amount of water that valley can contain. Draw a picture to see why this makes sense.

Translating this idea into an algorithm is easy. You just traverse the histogram left to right, keeping track of decreasing, constant and increasing runs as you go. If you set it up correctly, you won't need to handle leftmost and rightmost "half-valleys" as special cases; they will just be valleys where the height is zero because one of the two end points has height zero.