Water collected between towers

Question

I recently came across an interview question asked by Amazon and I am not able to find an optimized algorithm to solve this question:

You are given an input array whose each element represents the height of a line towers. The width of every tower is 1. It starts raining. How much water is collected between the towers?

Example

Input: [1,5,3,7,2] , Output: 2 units
Explanation: 2 units of water collected between towers of height 5 and 7

   *
   *
 *w*
 *w*
 ***
 ****
*****

Another Example

Input: [5,3,7,2,6,4,5,9,1,2] , Output: 14 units 
Explanation= 2 units of water collected between towers of height 5 and 7 +
             4 units of water collected between towers of height 7 and 6 + 
             1 units of water collected between towers of height 6 and 5 +
             2 units of water collected between towers of height 6 and 9 +
             4 units of water collected between towers of height 7 and 9 +
             1 units of water collected between towers of height 9 and 2.

At first I thought this could be solved by Stock-Span Problem (http://www.geeksforgeeks.org/the-stock-span-problem/) but I was wrong so it would be great if anyone can think of a time-optimized algorithm for this question.

Answer 1

Once the water's done falling, each position will fill to a level equal to the smaller of the highest tower to the left and the highest tower to the right.

Find, by a rightward scan, the highest tower to the left of each position. Then find, by a leftward scan, the highest tower to the right of each position. Then take the minimum at each position and add them all up.

Something like this ought to work:

int tow[N]; // nonnegative tower heights
int hl[N] = {0}, hr[N] = {0}; // highest-left and highest-right
for (int i = 0; i < n; i++) hl[i] = max(tow[i], (i!=0)?hl[i-1]:0);
for (int i = n-1; i >= 0; i--) hr[i] = max(tow[i],i<(n-1) ? hr[i+1]:0);
int ans = 0;
for (int i = 0; i < n; i++) ans += min(hl[i], hr[i]) - tow[i];

Answer 2

Here's an efficient solution in Haskell

rainfall :: [Int] -> Int
rainfall xs = sum (zipWith (-) mins xs)
    where mins = zipWith min maxl maxr
          maxl = scanl1 max xs
          maxr = scanr1 max xs

it uses the same two-pass scan algorithm mentioned in the other answers.

Answer 3

Refer this website for code, its really plain and simple http://learningarsenal.info/index.php/2015/08/21/amount-of-rain-water-collected-between-towers/

Input: [5,3,7,2,6,4,5,9,1,2] , Output: 14 units

Explanation

Each tower can hold water upto a level of smallest height between heighest tower to left, and highest tower to the right.

Thus we need to calculate highest tower to left on each and every tower, and likewise for the right side.

Here we will be needing two extra arrays for holding height of highest tower to left on any tower say, int leftMax[] and likewise for right side say int rightMax[].

STEP-1

We make a left pass of the given array(i.e int tower[]),and will be maintaining a temporary maximum(say int tempMax) such that on each iteration height of each tower will be compared to tempMax, and if height of current tower is less than tempMax then tempMax will be set as highest tower to left of it, otherwise height of current tower will be assigned as the heighest tower to left and tempMax will be updated with current tower height,

STEP-2

We will be following above procedure only as discussed in STEP-1 to calculate highest tower to right BUT this times making a pass through array from right side.

STEP-3

The amount of water which each tower can hold is-

(minimum height between highest right tower and highest left tower) – (height of tower)

Answer 4

You can do this by scanning the array twice.

The first time you scan from top to bottom and store the value of the tallest tower you have yet to encounter when reaching each row.

You then repeat the process, but in reverse. You start from the bottom and work towards the top of the array. You keep track of the tallest tower you have seen so far and compare the height of it to the value for that tower in the other result set.

Take the difference between the lesser of these two values (the shortest of the tallest two towers surrounding the current tower, subtract the height of the tower and add that amount to the total amount of water.

int maxValue = 0;
int total = 0;
int[n] lookAhead

for(i=0;i<n;i++)
{
    if(input[i] > maxValue) maxValue = input[i];
    lookahead[i] = maxValue;
}

maxValue = 0;
for(i=n-1;i>=0;i--)
{
    // If the input is greater than or equal to the max, all water escapes.
    if(input[i] >= maxValue)
    { 
        maxValue = input[i];
    }
    else
    {
        if(maxValue > lookAhead[i])
        {
            // Make sure we don't run off the other side.
            if(lookAhead[i] > input[i])
            {
                total += lookAhead[i] - input[i];
            }
        }
        else
        {
            total += maxValue - input[i];
        }
    } 
}

Answer 5

Readable Python Solution:

def water_collected(heights):
    water_collected = 0
    left_height = []
    right_height = []

    temp_max = heights[0]
    for height in heights:
        if (height > temp_max):
            temp_max = height
        left_height.append(temp_max)

    temp_max = heights[-1]
    for height in reversed(heights):
        if (height > temp_max):
            temp_max = height
        right_height.insert(0, temp_max)

    for i, height in enumerate(heights):
        water_collected += min(left_height[i], right_height[i]) - height
    return water_collected

Answer 6

O(n) solution in Java, single pass

Another implementation in Java, finding the water collected in a single pass through the list. I scanned the other answers but didn't see any that were obviously using my solution.

1. Find the first "peak" by looping through the list until the tower height stops increasing. All water before this will not be collected (drain off to the left).
2. For all subsequent towers:
   • If the height of the subsequent tower decreases or stays the same, add water to a "potential collection" bucket, equal to the difference between the tower height and the previous max tower height.
   • If the height of the subsequent tower increases, we collect water from the previous bucket (subtract from the "potential collection" bucket and add to the collected bucket) and also add water to the potential bucket equal to the difference between the tower height and the previous max tower height.
   • If we find a new max tower, then all the "potential water" is moved into the collected bucket and this becomes the new max tower height.

In the example above, with input: [5,3,7,2,6,4,5,9,1,2], the solution works as follows:

• 5: Finds 5 as the first peak
• 3: Adds 2 to the potential bucket (5-3)

  collected = 0, potential = 2

• 7: New max, moves all potential water to the collected bucket

  collected = 2, potential = 0

• 2: Adds 5 to the potential bucket (7-2)

  collected = 2, potential = 5

• 6: Moves 4 to the collected bucket and adds 1 to the potential bucket (6-2, 7-6)

  collected = 6, potential = 2

• 4: Adds 2 to the potential bucket (6-4)

  collected = 6, potential = 4

• 5: Moves 1 to the collected bucket and adds 2 to the potential bucket (5-4, 7-5)

  collected = 7, potential = 6

• 9: New max, moves all potential water to the collected bucket

  collected = 13, potential = 0

• 1: Adds 8 to the potential bucket (9-1)

  collected = 13, potential = 8

• 2: Moves 1 to the collected bucket and adds 7 to the potential bucket (2-1, 9-2)

  collected = 14, potential = 15

After running through the list once, collected water has been measured.

public static int answer(int[] list) {
    int maxHeight = 0;
    int previousHeight = 0;
    int previousHeightIndex = 0;
    int coll = 0;
    int temp = 0;

    // find the first peak (all water before will not be collected)
    while(list[previousHeightIndex] > maxHeight) {
        maxHeight = list[previousHeightIndex];
        previousHeightIndex++;
        if(previousHeightIndex==list.length)            // in case of stairs (no water collected)
            return coll;
        else
            previousHeight = list[previousHeightIndex];
    }

    for(int i = previousHeightIndex; i<list.length; i++) {
        if(list[i] >= maxHeight) {      // collect all temp water
            coll += temp;
            temp = 0;
            maxHeight = list[i];        // new max height
        }
        else {
            temp += maxHeight - list[i];
            if(list[i] > previousHeight) {  // we went up... collect some water
                int collWater = (i-previousHeightIndex)*(list[i]-previousHeight);
                coll += collWater;
                temp -= collWater;
            }
        }

        // previousHeight only changes if consecutive towers are not same height
        if(list[i] != previousHeight) {
            previousHeight = list[i];
            previousHeightIndex = i;
        }
    }
    return coll;
}

Answer 7

None of the 17 answers already posted are really time-optimal.

For a single processor, a 2 sweep (left->right, followed by a right->left summation) is optimal, as many people have pointed out, but using many processors, it is possible to complete this task in O(log n) time. There are many ways to do this, so I'll explain one that is fairly close to the sequential algorithm.

Max-cached tree O(log n)

1: Create a binary tree of all towers such that each node contains the height of the highest tower in any of its children. Since the two leaves of any node can be computed independently, this can be done in O(log n) time with n cpu's. (Each value is handled by its own cpu, and they build the tree by repeatedly merging two existing values. All parallel branches can be executed in parallel. Thus, it's O(log2(n)) for a 2-way merge function (max, in this case)).

2a: Then, for each node in the tree, starting at the root, let the right leaf have the value max(left, self, right). This will create the left-to-right monotonic sweep in O(log n) time, using n cpu's.

2b: To compute the right-to-left sweep, we do the same procedure as before. Starting with root of the max-cached tree, let the left leaf have the value max(left, self, right). These left-to-right (2a) and right-to-left (2b) sweeps can be done in parallel if you'd like to. They both use the max-cached tree as input, and generate one new tree each (or sets their own fields in original tree, if you prefer that).

3: Then, for each tower, the amount of water on it is min(ltr, rtl) - towerHeight, where ltr is the value for that tower in the left-to-right monotonic sweep we did before, i.e. the maximum height of any tower to the left of us (including ourselves¹), and rtl is the same for the right-to-left sweep.

4: Simply sum this up using a tree in O(log n) time using n cpu's, and we're done.

---

¹ If the current tower is taller than all towers to the left of us, or taller than all towers to the the right of us, min(ltr, rtl) - towerHeight is zero.

Here's two other ways to do it.

Answer 8

You can traverse first from left to right, and calculate the water accumulated for the cases where there is a smaller building on the left and a larger one on the right. You would have to subtract the area of the buildings that are in between these two buildings and are smaller than the left one.

Similar would be the case for right to left.

Here is the code for left to right. I have uploaded this problem on leetcode online judge using this approach.

I find this approach much more intuitive than the standard solution which is present everywhere (calculating the largest building on the right and the left for each i ).

int sum=0, finalAns=0;
    idx=0;
    while(a[idx]==0 && idx < n)
        idx++;
    for(int i=idx+1;i<n;i++){

        while(a[i] < a[idx] && i<n){
            sum += a[i];
            i++;
        }
        if(i==n)
            break;
        jdx=i;
        int area = a[idx] * (jdx-idx-1);
        area -= sum;
        finalAns += area;

        idx=jdx;
        sum=0;
    }

The time complexity of this approach is O(n), as you are traversing the array two time linearly. Space complexity would be O(1).

Answer 9

Here is a solution in Groovy in two passes.

assert waterCollected([1, 5, 3, 7, 2]) == 2
assert waterCollected([5, 3, 7, 2, 6, 4, 5, 9, 1, 2]) == 14
assert waterCollected([5, 5, 5, 5]) == 0
assert waterCollected([5, 6, 7, 8]) == 0
assert waterCollected([8, 7, 7, 6]) == 0
assert waterCollected([6, 7, 10, 7, 6]) == 0

def waterCollected(towers) {
    int size = towers.size()
    if (size < 3) return 0

    int left = towers[0]
    int right = towers[towers.size() - 1]

    def highestToTheLeft = []
    def highestToTheRight = [null] * size

    for (int i = 1; i < size; i++) {

        // Track highest tower to the left
        if (towers[i] < left) {
            highestToTheLeft[i] = left
        } else {
            left = towers[i]
        }

        // Track highest tower to the right
        if (towers[size - 1 - i] < right) {
            highestToTheRight[size - 1 - i] = right
        } else {
            right = towers[size - 1 - i]
        }
    }

    int water = 0
    for (int i = 0; i < size; i++) {
        if (highestToTheLeft[i] && highestToTheRight[i]) {
            int minHighest = highestToTheLeft[i] < highestToTheRight[i] ? highestToTheLeft[i] : highestToTheRight[i]
            water += minHighest - towers[i]
        }
    }

    return water
}

Here same snippet with an online compiler: https://groovy-playground.appspot.com/#?load=3b1d964bfd66dc623c89

Answer 10

The first and the last bars in the list cannot trap water. For the remaining towers, they can trap water when there are max heights to the left and to the right.

water accumulation is: max( min(max_left, max_right) - current_height, 0 )

Iterating from the left, if we know that there is a max_right that is greater, min(max_left, max_right) will become just max_left. Therefore water accumulation is simplified as: max(max_left - current_height, 0) Same pattern when considering from the right side.

From the info above, we can write a O(N) time and O(1) space algorithm as followings(in Python):

def trap_water(A):

     water = 0
     left, right = 1, len(A)-1
     max_left, max_right = A[0], A[len(A)-1]

     while left <= right:
         if A[left] <= A[right]:
             max_left = max(A[left], max_left)
             water += max(max_left - A[left], 0)
             left += 1
         else:
             max_right = max(A[right], max_right)
             water += max(max_right - A[right], 0)
             right -= 1

     return water

Answer 11

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    let maxLeftArray = [], maxRightArray = [];
    let maxLeft = 0, maxRight = 0;
    const ln = height.length;
    let trappedWater = 0;
    for(let i = 0;i < height.length; i ++) {
        maxLeftArray[i] = Math.max(height[i], maxLeft);
        maxLeft = maxLeftArray[i];
        maxRightArray[ln - i - 1] = Math.max(height[ln - i - 1], maxRight);
        maxRight = maxRightArray[ln - i - 1];
    }
    for(let i = 0;i < height.length; i ++) {
        trappedWater += Math.min(maxLeftArray[i], maxRightArray[i]) - height[i];
    }
    return trappedWater;
};

var arr = [5,3,7,2,6,4,5,9,1,2];
console.log(trap(arr));

You could read the detailed explanation in my blogpost: trapping-rain-water

Answer 12

Here is one more solution written on Scala

def find(a: Array[Int]): Int = {
  var count, left, right = 0

  while (left < a.length - 1) {
    right = a.length - 1
    for (j <- a.length - 1 until left by -1) {
      if (a(j) > a(right)) right = j
    }

    if (right - left > 1) {
      for (k <- left + 1 until right) count += math.min(a(left), a(right)) - a(k)
      left = right
    } else left += 1
  }

  count
}

Answer 13

An alternative algorithm in the style of Euclid, which I consider more elegant than all this scanning is:

Set the two tallest towers as the left and right tower. The amount of water contained between these towers is obvious.

Take the next tallest tower and add it. It must be either between the end towers, or not. If it is between the end towers it displaces an amount of water equal to the towers volume (thanks to Archimedes for this hint). If it outside the end towers it becomes a new end tower and the amount of additional water contained is obvious.

Repeat for the next tallest tower until all towers are added.

I've posted code to achieve this (in a modern Euclidean idiom) here: http://www.rosettacode.org/wiki/Water_collected_between_towers#F.23

Answer 14

I have a solution that only requires a single traversal from left to right.

def standing_water(heights):

    if len(heights) < 3:
        return 0

    i = 0   # index used to iterate from left to right
    w = 0   # accumulator for the total amount of water

    while i < len(heights) - 1:

        target = i + 1
        for j in range(i + 1, len(heights)):

            if heights[j] >= heights[i]:
                target = j
                break

            if heights[j] > heights[target]:
                target = j

        if target == i:
            return w

        surface = min(heights[i], heights[target])

        i += 1

        while i < target:
            w += surface - heights[i]
            i += 1

    return w

Answer 15

An intuitive solution for this problem is one in which you bound the problem and fill water based on the height of the left and right bounds.

My solution:

• Begin at the left, setting both bounds to be the 0th index.
• Check and see if there is some kind of a trajectory (If you were to walk on top of these towers, would you ever go down and then back up again?) If that is the case, then you have found a right bound.
• Now back track and fill the water accordingly (I simply added the water to the array values themselves as it makes the code a little cleaner, but this is obviously not required).
• The punch line: If the left bounding tower height is greater than the right bounding tower height than you need to increment the right bound. The reason is because you might run into a higher tower and need to fill some more water. However, if the right tower is higher than the left tower then no more water can be added in your current sub-problem. Thus, you move your left bound to the right bound and continue.

Here is an implementation in C#:

        int[] towers = {1,5,3,7,2};

        int currentMinimum = towers[0];

        bool rightBoundFound = false;

        int i = 0;
        int leftBoundIndex = 0;
        int rightBoundIndex = 0;

        int waterAdded = 0;

        while(i < towers.Length - 1)
        {

            currentMinimum = towers[i];

            if(towers[i] < currentMinimum)
            {
                currentMinimum = towers[i];
            }

            if(towers[i + 1] > towers[i])
            {
                rightBoundFound = true;
                rightBoundIndex = i + 1;
            }

            if (rightBoundFound)
            {

                for(int j = leftBoundIndex + 1; j < rightBoundIndex; j++)
                {

                    int difference = 0;

                    if(towers[leftBoundIndex] < towers[rightBoundIndex])
                    {
                        difference = towers[leftBoundIndex] - towers[j];
                    }
                    else if(towers[leftBoundIndex] > towers[rightBoundIndex])
                    {
                        difference = towers[rightBoundIndex] - towers[j];
                    }
                    else
                    {
                        difference = towers[rightBoundIndex] - towers[j];
                    }

                    towers[j] += difference;
                    waterAdded += difference;

                }

                if (towers[leftBoundIndex] > towers[rightBoundIndex])
                {
                    i = leftBoundIndex - 1;
                }
                else if (towers[rightBoundIndex] > towers[leftBoundIndex])
                {
                    leftBoundIndex = rightBoundIndex;
                    i = rightBoundIndex - 1;
                }
                else
                {
                    leftBoundIndex = rightBoundIndex;
                    i = rightBoundIndex - 1;
                }
                rightBoundFound = false;

            }

            i++;

        }

I have no doubt that there are more optimal solutions. I am currently working on a single-pass optimization. There is also a very neat stack implementation of this problem, and it uses a similar idea of bounding.

Answer 16

Here is my solution, it passes this level and pretty fast, easy to understand The idea is very simple: first, you figure out the maximum of the heights (it could be multiple maximum), then you chop the landscape into 3 parts, from the beginning to the left most maximum heights, between the left most max to the right most max, and from the right most max to the end.

In the middle part, it's easy to collect the rains, one for loop does that. Then for the first part, you keep on updating the current max height that is less than the max height of the landscape. one loop does that. Then for the third part, you reverse what you have done to the first part

def answer(heights):
    sumL = 0
    sumM = 0
    sumR = 0
    L = len(heights)
    MV = max(heights)
    FI = heights.index(MV)
    LI = L - heights[::-1].index(MV) - 1
    if LI-FI>1:
        for i in range(FI+1,LI):
            sumM = sumM + MV-heights[i]

    if FI>0:
        TM = heights[0]
        for i in range(1,FI):
            if heights[i]<= TM:
                sumL = sumL + TM-heights[i]
            else:
                TM = heights[i]
    if LI<(L-1):
        TM = heights[-1]
        for i in range(L-1,LI,-1):
            if heights[i]<= TM:
               sumL = sumL + TM-heights[i]
            else:
               TM = heights[i]
    return(sumL+sumM+sumR)        

Answer 17

Here is a solution in JAVA that traverses the list of numbers once. So the worst case time is O(n). (At least that's how I understand it).

For a given reference number keep looking for a number which is greater or equal to the reference number. Keep a count of numbers that was traversed in doing so and store all those numbers in a list.

The idea is this. If there are 5 numbers between 6 and 9, and all the five numbers are 0's, it means that a total of 30 units of water can be stored between 6 and 9. For a real situation where the numbers in between aren't 0's, we just deduct the total sum of the numbers in between from the total amount if those numbers were 0. (In this case, we deduct from 30). And that will give the count of water stored in between these two towers. We then save this amount in a variable called totalWaterRetained and then start from the next tower after 9 and keep doing the same till the last element.

Adding all the instances of totalWaterRetained will give us the final answer.

JAVA Solution: (Tested on a few inputs. Might be not 100% correct)

private static int solveLineTowerProblem(int[] inputArray) {
    int totalWaterContained = 0;
    int index;
    int currentIndex = 0;
    int countInBetween = 0;
    List<Integer> integerList = new ArrayList<Integer>();

    if (inputArray.length < 3) {
        return totalWaterContained;
    } else {
        for (index = 1; index < inputArray.length - 1;) {
            countInBetween = 0;
            integerList.clear();

            int tempIndex = index;
            boolean flag = false;

            while (inputArray[currentIndex] > inputArray[tempIndex] && tempIndex < inputArray.length - 1) {
                integerList.add(inputArray[tempIndex]);
                tempIndex++;
                countInBetween++;
                flag = true;
            }

            if (flag) {
                integerList.add(inputArray[index + countInBetween]);
                integerList.add(inputArray[index - 1]);

                int differnceBetweenHighest = min(integerList.get(integerList.size() - 2),
                        integerList.get(integerList.size() - 1));
                int totalCapacity = differnceBetweenHighest * countInBetween;
                totalWaterContained += totalCapacity - sum(integerList);
            }
            index += countInBetween + 1;
            currentIndex = index - 1;
        }
    }
    return totalWaterContained;
}

Answer 18

Here is my take to the problem, I use a loop to see if the previous towers is bigger than the actual one. If it is then I create another loop to check if the towers coming after the actual one are bigger or equal to the previous tower. If that's the case then I just add all the differences in height between the previous tower and all other towers. If not and if my loop reaches my last object then I simply reverse the array so that the previous tower becomes my last tower and call my method recursively on it. That way I'm certain to find a tower bigger than my new previous tower and will find the correct amount of water collected.

public class towers {
    public static int waterLevel(int[] i) {
        int totalLevel = 0;

        for (int j = 1; j < i.length - 1; j++) {
            if (i[j - 1] > i[j]) {
                for (int k = j; k < i.length; k++) {
                    if (i[k] >= i[j  - 1]) {
                        for (int l = j; l < k; l++) { 
                            totalLevel += (i[j - 1] - i[l]);
                        }

                        j = k;
                        break;
                    }  

                    if (k == i.length - 1) {
                        int[] copy = Arrays.copyOfRange(i, j - 1, k + 1);
                        int[] revcopy = reverse(copy);
                        totalLevel += waterLevel(revcopy);
                    }
                }
            }
        }

        return totalLevel;
    }

    public static int[] reverse(int[] i) {
        for (int j = 0; j < i.length / 2; j++) {
            int temp = i[j];
            i[j] = i[i.length - j - 1];
            i[i.length - j - 1] = temp;
        }

        return i;
    }

    public static void main(String[] args) {
        System.out.println(waterLevel(new int[] {1, 6, 3, 2, 2, 6}));
    }
}

Answer 19

Tested all the Java solution provided, but none of them passes even half of the test-cases I've come up with, so there is one more Java O(n) solution, with all possible cases covered. The algorithm is really simple:

1) Traverse the input from the beginning, searching for tower that is equal or higher that the given tower, while summing up possible amount of water for lower towers into temporary var.

2) Once the tower found - add that temporary var into main result var and shorten the input list.

3) If no more tower found then reverse the remaining input and calculate again.

public int calculate(List<Integer> input) {
    int result = doCalculation(input);
    Collections.reverse(input);
    result += doCalculation(input);
    return result;
}

private static int doCalculation(List<Integer> input) {
    List<Integer> copy = new ArrayList<>(input);
    int result = 0;
    for (ListIterator<Integer> iterator = input.listIterator(); iterator.hasNext(); ) {
        final int firstHill = iterator.next();
        int tempResult = 0;
        int lowerHillsSize = 0;
        while (iterator.hasNext()) {
            final int nextHill = iterator.next();
            if (nextHill >= firstHill) {
                iterator.previous();
                result += tempResult;
                copy = copy.subList(lowerHillsSize + 1, copy.size());
                break;
            } else {
                tempResult += firstHill - nextHill;
                lowerHillsSize++;
            }
        }
    }
    input.clear();
    input.addAll(copy);
    return result;
}

For the test cases, please, take a look at this test class.

Feel free to create a pull request if you find uncovered test cases)

Answer 20

This is a funny problem, I just got that question in an interview. LOL I broke my mind on that stupid problem, and found a solution which need one pass (but clearly non-continuous). (and in fact you even not loop over the entire data, as you bypass the boundary...)

So the idea is. You start from the side with the lowest tower (which is now the reference). You directly add the content of the towers, and if you reach a tower which is highest than the reference, you call the function recursively (with side to be reset). Not trivial to explain with words, the code speak for himself.

  #include <iostream>
  using namespace std;

  int compute_water(int * array, int index_min, int index_max)
  {
  int water = 0;
  int dir;
  int start,end;
  int steps = std::abs(index_max-index_min)-1;
  int i,count;
  if(steps>=1)
  {
    if(array[index_min]<array[index_max])
    {
      dir=1;
      start = index_min;
      end = index_max;
    }
    else
    {
      dir = -1;
      start = index_max;
      end = index_min;
    }
    for(i=start+dir,count=0;count<steps;i+=dir,count++)
    {
      if(array[i]<=array[start])water += array[start] - array[i];
      else
      {
        if(i<end)water += compute_water(array, i, end);
        else water += compute_water(array, end, i);
        break;
      }
    }
  }
  return water;
}

int main(int argc,char ** argv)
{
  int size = 0;
  int * towers;
  if(argc==1)
  {
    cout<< "Usage: "<<argv[0]<< "a list of tower height separated by spaces" <<endl;
  }
  else
  {
    size = argc - 1;
    towers =  (int*)malloc(size*sizeof(int));
    for(int i = 0; i<size;i++)towers[i] = atoi(argv[i+1]);
    cout<< "water collected: "<< compute_water(towers, 0, size-1)<<endl;
    free(towers);
  }
}

Answer 21

I wrote this relying on some of the ideas above in this thread:

def get_collected_rain(towers):

    length = len(towers)
    acummulated_water=[0]*length
    left_max=[0]*length
    right_max=[0]*length

    for n in range(0,length):

        #first left item
        if n!=0:
            left_max[n]=max(towers[:n])

        #first right item
        if n!=length-1:
            right_max[n]=max(towers[n+1:length])

        acummulated_water[n]=max(min(left_max[n], right_max[n]) - towers[n], 0)

    return sum(acummulated_water)

Well ...

> print(get_collected_rain([9,8,7,8,9,5,6]))

> 5

Answer 22

Here's my attempt in jQuery. It only scans to the right.

Working fiddle (with helpful logging)

var a = [1, 5, 3, 7, 2];
var water = 0;

$.each(a, function (key, i) {
  if (i > a[key + 1]) { //if next tower to right is bigger
      for (j = 1; j <= a.length - key; j++) { //number of remaining towers to the right
          if (a[key+1 + j] >= i) { //if any tower to the right is bigger
              for (k = 1; k < 1+j; k++) {
              //add to water: the difference of the first tower and each tower between the first tower and its bigger tower
                  water += a[key] - a[key+k];
              }
          }
      }
  }
});

console.log("Water: "+water);

Answer 23

Here's my go at it in Python. Pretty sure it works but haven't tested it.

Two passes through the list (but deleting the list as it finds 'water'):

def answer(heights):

def accWater(lst,sumwater=0):
    x,takewater = 1,[]
    while x < len(lst):
        a,b = lst[x-1],lst[x]
        if takewater:
            if b < takewater[0]:
                takewater.append(b)
                x += 1
            else:
                sumwater += sum(takewater[0]- z for z in takewater)
                del lst[:x]
                x = 1
                takewater = []
        else:
            if b < a:
                takewater.extend([a,b])
                x += 1
            else:
                x += 1
    return [lst,sumwater]

heights, swater = accWater(heights)
x, allwater = accWater(heights[::-1],sumwater=swater)
return allwater

Answer 24

private static int soln1(int[] a)
    {
        int ret=0;
        int l=a.length;
        int st,en=0;
        int h,i,j,k=0;
        int sm;
        for(h=0;h<l;h++)
        {
        for(i=1;i<l;i++)
        {
            if(a[i]<a[i-1])
            {
                st=i;
                for(j=i;j<l-1;j++)
                {
                    if(a[j]<=a[i] && a[j+1]>a[i])
                    {
                        en=j;
                        h=en;
                        break;
                    }
                }
                if(st<=en)
                {
                    sm=a[st-1];
                    if(sm>a[en+1])
                        sm=a[en+1];
                    for(k=st;k<=en;k++)
                    {
                        ret+=sm-a[k];
                        a[k]=sm;
                    }
                }
            }
        }
        }
        return ret;
    }

Answer 25

/*** Theta(n) Time COmplexity ***/
        static int trappingRainWater(int ar[],int n)
        {
            int res=0;
            int lmaxArray[]=new int[n];
            int rmaxArray[]=new int[n];
            lmaxArray[0]=ar[0];
            for(int j=1;j<n;j++)
            {
                lmaxArray[j]=Math.max(lmaxArray[j-1], ar[j]);
            }
            rmaxArray[n-1]=ar[n-1];
            for(int j=n-2;j>=0;j--)
            {
                rmaxArray[j]=Math.max(rmaxArray[j+1], ar[j]);
            }
            for(int i=1;i<n-1;i++)
            {
                res=res+(Math.min(lmaxArray[i], rmaxArray[i])-ar[i]);
            }
            return res;
        }