Algorithm to solve for water accumulation given building heights

Question

I am practicing algorithms, and I have been stuck on this problem for a few days. When I test my solution, I am still incorrect. Here is the problem statement:

The Wall Street in New York is known for its breathtaking skyscrapers. But the raining season is approaching, and the amount of water that will fall over the buildings is going to be huge this year. Since every building is stuck to the buildings to its left and to its right (except for the first and the last one), the water can leak from a building only if the height of the building is higher than the height of the building to its left or to its right (the height of the edges of Wall Street is 0). All the buildings have the width of 1 meter. You are given the heights (in meters) of the buildings on Wall Street from left to right, and your task is to print to the standard output (stdout) the total amount of water (in cubic meters) held over the buildings on Wall Street.

Example input:

heights: [9 8 7 8 9 5 6]

Example output:

5

Explanation: In this example, between the first and the fifth building there are held 4 cubic meters of water (1 over the second, 2 over the third, and 1 over the fourth), and between the fifth and the seventh building there is 1 cubic meter of water held (over the sixth building).

My approach to this problem is to find global maxima, and use differences in these maxima to calculate water accumulation. I account for water I might have missed at the end using the local_water variable. Can anyone help me find the error in my algorithm or code?

NOTE: I am looking for a solution which passes through each element only once

Here is the input where I have an error:

heights: [8,8,4,5]

this input should yield 1, not my answer which is 0.

Here is my code:

def skyscrapers(heights):
    heights.insert(0,0)
    heights.append(0)
    local_max = 0
    global_max = 0
    total_water = 0
    local_water = 0
    end_water = []
        # end_water records water heights to be used for finding 
                # water between the final global maximum and 
                # subsequent local maximums. These potential values are
                # stored in local_water.
    for i in range(1, len(heights)-1):
        end_water.append(heights[i]) 

        # check for local max
        if heights[i-1] < heights[i] and heights[i] > heights[i+1]:

            # record potential collected water for after final
            # gloabl max
            for s in end_water:
                local_water += (heights[i] - s) * (heights[i] - s > 0)
            local_max=i

        # new global max
        if heights[local_max] > heights[global_max]:
            for s in heights[global_max:local_max]:
                if heights[global_max] - s > 0:
                    total_water += heights[global_max] - s
            global_max = local_max
            local_water = 0
            end_water = []

    total_water += local_water

    print total_water

Answer 1

height
   _       _
9 | |_   _| |      _ _
8 |   |_|   |     |   |
7 |         |  _  |   |
6 |         |_| | |   |  _
5 |             | |   |_| |
4 |             | |       |  _       _ 
3 |             | |       | | |  _  | |
2 |             | |       | | |_| |_| |
1 |0 1 2 3 4 5 6| |0 1 2 3| |0 1 2 3 4| pos

Here's a single-pass (!) (O(n)-time) O(n)-space algorithm based on the stack-based solution for Maximize the rectangular area under Histogram problem:

from collections import namedtuple

Wall = namedtuple('Wall', 'pos height')

def max_water_heldover(heights):
    """Find the maximum amount of water held over skyscrapers with *heights*."""
    stack = []
    water_held = 0 # the total amount of water held over skyscrapers
    for pos, height in enumerate(heights):
        while True:
            if not stack or height < stack[-1].height: # downhill
                stack.append(Wall(pos + 1, height)) # push possible left well wall
                break
            else: # height >= stack[-1].height -- found the right well wall/bottom
                bottom = stack.pop().height
                if stack: # if there is the left well wall
                    well_height = min(stack[-1].height, height) - bottom
                    if well_height:
                        water_held += (pos - stack[-1].pos) * well_height
    return water_held

Example:

>>> max_water_heldover([9, 8, 7, 8, 9, 5, 6])
5
>>> max_water_heldover([8, 8, 4, 5])
1
>>> max_water_heldover([3, 1, 2, 1, 3])
5

I've tested it against a brute-force O(n*m) algorithm:

from itertools import product

def test(max_buildings=6, max_floors=6):
    for nbuildings, nfloors in product(range(max_buildings), range(max_floors)):
        for heights in product(range(nfloors), repeat=nbuildings):
            assert max_water_heldover(heights) == max_water_heldover_bruteforce(heights), heights

where max_water_heldover_bruteforce() is:

import sys
from colorama import Back, Fore, Style, init # $ pip install colorama
init(strip=not sys.stderr.isatty())

def max_water_heldover_bruteforce(heights):
    if not heights: return 0
    BUILDING, AIR, WATER = ['B', ' ',
            Back.BLUE + Fore.WHITE + 'W' + Fore.RESET + Back.RESET + Style.RESET_ALL]
    matrix = [[WATER] * len(heights) for _ in range(max(heights))]
    for current_floor, skyscrapers in enumerate(matrix, start=1):
        outside = True
        for building_number, building_height in enumerate(heights):
            if current_floor <= building_height:
                outside = False
                skyscrapers[building_number] = BUILDING
            elif outside:
                skyscrapers[building_number] = AIR
        for i, building_height in enumerate(reversed(heights), 1):
            if current_floor > building_height:
                skyscrapers[-i] = AIR
            else:
                break
    if '--draw-skyscrapers' in sys.argv:
        print('\n'.join(map(''.join, matrix[::-1])), file=sys.stderr)
        print('-'*60, file=sys.stderr)
    return sum(1 for row in matrix for cell in row if cell == WATER)

The results are the same.

Answer 2

Here's a one-pass solution that improves on liuzhidong's and J.S. Sebastian's solutions by using only O(1) space:

def fillcount(elevations):
    start = 0
    end = len(elevations) - 1
    count = 0
    leftmax = 0
    rightmax = 0

    while start < end:
        while start < end and elevations[start] <= elevations[start + 1]:
            start += 1
        else:
            leftmax = elevations[start]

        while end > start and elevations[end] <= elevations[end - 1]:
            end -= 1
        else:
            rightmax = elevations[end]

        if leftmax < rightmax:
            start += 1
            while start < end and elevations[start] <= leftmax:
                count += leftmax - elevations[start]
                start += 1
        else:
            end -= 1
            while end > start and elevations[end] <= rightmax:
                count += rightmax - elevations[end]
                end -= 1

    return count

I tested it against this simpler two-pass solution:

def fillcount_twopass(elevations):
    global_max = max(range(len(elevations)), key=lambda x: elevations[x])
    count = 0
    local_max = 0

    for i in xrange(0, global_max):
        if elevations[i] > local_max:
            local_max = elevations[i]
        else:
            count += local_max - elevations[i]

    local_max = 0
    for i in xrange(len(elevations) - 1, global_max, -1):
        if elevations[i] > local_max:
            local_max = elevations[i]
        else:
            count += local_max - elevations[i]

    return count

The two-pass solution is based on the following logic:

1. Find the maximum peak for the whole graph -- the global maximum.
2. Scan from the left side towards the global maximum peak. Keep track of the left maximum. Every cell that is a) below or at the same level as the left maximum, b) to the right of the left maximum, and c) to the left of the global maximum will hold water. When the left maximum increases, it has no effect on the earlier columns, but the later columns now hold water at this new maximum level.
3. Do the same from the right, in reverse.

This is similar to what Rémi suggested, but uses the global maximum to provide an anchor, which simplifies things.

The one-pass solution is partially based on ideas from Mark Tolonen. It improves on the above by observing that we can do both the left and right pass simultaneously, without knowing the global maximum. That's because the current maximum on either side is either greater than, lower than, or equal to the maximum on the other side. The lower maximum will always be lower than the global maximum, even if we don't yet know what the global maximum is, so we can proceed from there to the next local maximum on that side. The algorithm in full detail:

1. Start with pointers at the start and the end of the list, and initialize left_max, right_max, and count to 0.
2. Scan right, incrementing start until you reach a left maximum. Then scan left, decrementing end until you reach a right maximum.
3. From the lower maximum, continue scanning until you reach a column greater than the local maximum, counting fillable cells along the way and adding them to count.
4. Repeat steps 2 and 3, ending when start and end coincide.

Note that for our purposes, a local maximum is simply any point that is preceded by an ascent (and possibly a plateau), and followed by a descent. Local maxima below the highest local maximum encountered so far are only encountered in step 3, where they have no effect.

This last solution can process ten million datapoints in 3 seconds:

>>> rands = [random.randrange(0, 1000000) for i in xrange(10000000)]
>>> %timeit fillcount(rands)
1 loops, best of 3: 3.3 s per loop

Answer 3

class Solution:


    # @param A, a list of integers
    # @return an integer
    def trap(self, A):
        uTrapper = []

        i = 0
        leftIndex = 0
        rightIndex = 0
        # only 2 left could not trap water
        while (i < (len(A) - 2)):
            leftIndex = self.findLeftBank((A[i:])) + i

            rightIndex = self.findRightBank((A[leftIndex+1:]), A[leftIndex]) + leftIndex + 1

            uTrapper.append((A[leftIndex : rightIndex+1]))
            i = rightIndex

        return self.getRainWater(uTrapper)

    def findLeftBank(self, list):
        for i in range(len(list)):
            curr = list[i]
            currNext = list[i+1] if i+1 < len(list) else 0

            if(curr > currNext):
                return i
        return len(list) - 1

    def findRightBank(self, list, leftHight):
        biggestLoc = len(list)
        biggest = 0
        for i in range(len(list)):
            if(list[i] >= leftHight):
                return i
            if(list[i] > biggest):
                biggestLoc = i
                biggest = list[i]

        return biggestLoc

    def getRainWater(self, lists):

        all = 0
        for i in range(len(lists)):
            list = lists[i]

            height = min(list[0], list[len(list)-1])
            for i in range(1, len(list)-1):
                if(list[i] > height):
                    continue
                all = all + (height - list[i])
        return all

s = Solution()
print s.trap([9,6,8,8,5,6,3])

Is above ok ?

Answer 4

I would like to propose my solution that seems really intuitive.

STRATEGY: The strategy is to find the local maxima in the heights of the buildings and, in the middle of every couple of maxima (when there are), to cumulate the water:

CODE:

from scipy.signal import argrelextrema
import numpy as np

def local_max_scipy(a):
    minima = argrelextrema(a, np.greater_equal)[0]
    return minima

def water_cumulative(buildings):
    local_maxima=local_max_scipy(buildings)
    water = 0
    # 2 or more maxima => there is water 
    if len(local_maxima)>1:
        # in the middle of every couple of local maxima
        for i in range((len(local_maxima)-1)):
            reference = 0
            #pick the shorter building between the two maxima as reference
            if buildings[local_maxima[i]] >= buildings[local_maxima[i+1]]:
                reference = buildings[local_maxima[i+1]]
            else:
                reference = buildings[local_maxima[i]]
            #cumulate the water
            for j in range(local_maxima[i+1]-local_maxima[i]):
                # just exit when building higher than the reference is found
                if buildings[local_maxima[i]+1+j] < reference:
                    water = water + reference - buildings[local_maxima[i]+1+j]
                else:
                    break
    return water 

TESTS:

The function was tested with:

buildings01 = np.array([3, 2, 1, 4, 5])

buildings02 = np.array([1, 2, 3, 4, 5])

buildings03 = np.array([9, 8, 7, 8, 9, 5, 6])

buildings04 = np.array([8, 8, 4, 5])

The output is:

>>>water_cumulative(buildings01)
3
>>>water_cumulative(buildings02)
0
>>>water_cumulative(buildings03)
5
>>>water_cumulative(buildings04)
1

Answer 5

I will provide my answer using R software. My approach towards this problem has been as following; creating 3 functions:

1. Startchoice() selects the vector beginning, discarding for instance heights of buildings which consecutive is not lower than himself.

2. SectorCalculation() uses the vector returned by Startchoice() to create small list of vector to calculate the water area that is between the buldings. If a local or global max is found after the first value, then the computer will iterate through index values of the vector until it finds the following local or global max height , storing the subset of the vector until that point in a list, eliminating that part of the vector but the last value to pass it again to the formula and redo the same preocedure until a the vector is all done.

3. Then, AreaCalculation() will be used to calculate for each vector in the output list the water they can handle.

The main() function only gets the initial vector, calls the functions explained above and sums the water hold by each small vector of building and gives the integer general result. Some example are provided below:

SectorCalculation<- function(vector){
  ## It outputs in a list the different side roofs
  counter<-1
  vectorList<- list()
  ## While vector is larger than 2
  ## Choose the max value in the string appart from the left value
  ### If it finds it, then that is the sector, eliminate it and start again 
  ###     the procedure with the part of the vector left
  ### Else , go to next index 
  while(length(vector)>2){
    vecleft<-StartChoice(vector)
    if(all.equal(vecleft,rep(0,length(vecleft)))!=TRUE){
      global_max<- max(vecleft[2:length(vecleft)])
      left<- vecleft[1]
      for(i in 2:length(vecleft)){
        if(i > length(vecleft)){
          return(vectorList)}
        else{
          if(vecleft[i]==global_max){
            vectorList[[counter]]<-vecleft[1:i]
            vector<- vecleft[i:length(vecleft)]
            counter<- counter+1
            break
          }
        }
      }
    }else{return(0)}
  }
  return(vectorList)
}


StartChoice<- function(vecHeights){
  ## It gives back the vector discarding zero values at the beginning 
  leftval<-integer(0)
  ChooseStart <- TRUE  
  for(i in 1:length(vecHeights)){
    if(length(leftval)==0){
      leftval[1]<- vecHeights[i]
    } 
    else if(i == length(vecHeights)){return(0)}
    else {
      if(vecHeights[i] >= leftval){
        leftval[1]<- vecHeights[i]
      }
      else{
        ChooseStart <- FALSE
        vectorleft<-vecHeights[(i-1):length(vecHeights)]
        break
      }
    }
  }
  return(vectorleft)
}



AreaCalculation<-function(HeightsPassed){
  ## Select the second highest value between left and right and 
  ## compute the value in the roof
  highest<- min(HeightsPassed[1], HeightsPassed[length(HeightsPassed)])  
  Res<-(highest-HeightsPassed)[(highest-HeightsPassed)>0] 
  # Selecting only those values higher than 0 
  TotWater<-sum(Res)  
  return(TotWater)
}

main<-function(Heights){
  ## if value containing values <= 0, out
  if(all.equal((Heights <= 0), rep(FALSE, length(Heights)))!=TRUE){
    stop("Either values equal or lower than 0 or non-numeric values supplied")
  } 
  ## Get in a list all the sectors to be calculated
  MyHeightslist<-SectorCalculation(Heights)
  ## If list different than a list 0 with a 0, then 
  ## just calculate by parts the water in the roofs; then sum it
  if(all.equal(MyHeightslist[[1]],rep(0,length(MyHeightslist[[1]])))!=TRUE)
  {
    byParts<-sapply(MyHeightslist, AreaCalculation) 
    TotalWater<-sum(byParts)
  }
  else{return(0)}
  return(TotalWater)
}

Some examples are provided below to see how it works :),

main(c(1,2,3))
[1] 0
main(c(9,8,7,8,9,5,6)) 
[1] 5
main(c(8,9,9,8,7,8,9,5,6))
[1] 5
main(c(8, 8, 4, 5))
[1] 1
main(c(3,1,3,1,1,3))
[1] 6
main(c(1,2,3,4))
[1] 0
main(c(3,2,1))
[1] 0

Cheers !,