Water collected between the towers

Question

I recently came across an interview question posed by Amazon, and I cannot find an optimized algorithm to solve this question:

You are given an input array, each element of which represents the height of the lower case towers. The width of each tower is 1. It starts to rain. 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 with the help of the stock problem ( http://www.geeksforgeeks.org/the-stock-span-problem/ ), but I was wrong, so it would be great if anyone could think about a time-optimized algorithm for this question.

Answer 1

As soon as the water falls, each position will be filled to a level equal to the lower tower height on the left and the highest tower on the right.

Find, on proper viewing, the highest tower to the left of each position. Then use the scan on the left to find the highest tower to the right of each position. Then take a minimum at each position and add everything.

Something like this should 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 effective 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 scanning algorithm mentioned in other answers.

Answer 3

Check out this site for code, its really simple 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,9,2], Output: 14 units

Explanation

Each tower can hold water to the lowest height between the highest tower to the left and the highest tower to the right.

Thus, we need to calculate the height of the tower on the left of each tower, as well as for the right side.

Here we need two additional arrays for placing the height of the highest tower on the left of any tower, for example, int leftMax [], as well as for the right side: int rightMax [].

STEP 1

We make the left pass of this array (i.e. int tower []) and will maintain a temporary maximum (for example, int tempMax), so that at each iteration height of each tower it will be compared with tempMax, and if the height of the current tower is less than tempMax , then tempMax will be set as the highest tower to the left of it, otherwise the height of the current tower will be assigned as the largest tower to the left, and tempMax will be updated with the current height of the tower,

STEP-2

We will follow the procedure above, only as described in STEP-1, to calculate the height of the tower on the right, but this time makes the passage through the array on the right side.

STEP 3

The amount of water that each tower can withstand is

(minimum height between the top right tower and the highest left tower) - (tower height)

Answer 4

You can do this by scanning the array twice.

The first time you browse from top to bottom and save the value of the tallest tower that you have not yet encountered when reaching each line.

Then you repeat the process, but vice versa. You start from the bottom and work at the top of the array. You follow the tallest tower that you have seen so far, and compare its height with the value for this tower in another result set.

Take the difference between the smaller of these two values ​​(the shortest of the highest two towers surrounding the current tower, subtract the height of the tower and add it 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 solution for Python:

 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 Java implementation, finding water collected in one pass through a list. I looked at other answers, but did not see any that obviously used my solution.

• Find the first "peak" by going through the list until the height of the tower stops growing. All water will not be collected before (drain to the left).
• For all subsequent towers:
  • If the height of the subsequent tower decreases or remains unchanged, add water to the “potential collection” bucket equal to the difference between the height of the tower and the previous maximum height of the tower.
  • If the height of the subsequent tower increases, we collect water from the previous bucket (subtract from the bucket of the potential collection and add to the assembled bucket), and also add water to the potential bucket, equal to the difference between the tower height and the previous maximum tower height.
  • If we find a new maximum tower, then all of the "potential water" will be moved to the collected bucket, and this will become the new maximum height of the tower.

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

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

  collected = 0, potential = 2

• 7: New high, moves all potential water into a collected bucket

  assembled = 2, potential = 0

• 2: adds 5 to potential bucket (7-2)

  assembled = 2, potential = 5

• 6: moves 4 into the assembled bucket and adds 1 to the potential bucket (6-2, 7-6)

  assembled = 6, potential = 2

• 4: Add 2 to potential bucket (6-4)

  collected = 6, potential = 4

• 5: moves 1 into the assembled bucket and adds 2 to the potential bucket (5-4, 7-5)

  assembled = 7, potential = 6

• 9: New high, moves all potential water into a collected bucket

  collected = 13, potential = 0

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

  collected = 13, potential = 8

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

  assembled = 14, potential = 15

After going through the list, the collected water was measured once.

 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 responses already published are optimal in time.

For one processor, fetching 2 sweeps ( left->right , followed by summing right->left ) is optimal, as many people have pointed out, but using many processors, you can perform this task in O (log n). There are many ways to do this, so I will explain one that is close enough to a sequential algorithm.

Maximum Cached Tree O (log n)

1: Create a binary tree of all the towers so that each node contains the height of the highest tower of any of its children. Since two sheets of any node can be calculated independently, this can be done in O(log n) time with n cpu's.

2a: Then for each node in the tree, starting from the root, let the right leaf be set to max(left, self, right) . This will create a monotonic sweep from left to right in O(log n) using n cpu.

2b: To calculate the scroll from right to left, we follow the same procedure as before. Starting from the root of the tree with the maximum cache, let the left leaf be set to max(left, self, right) . These arrows from left to right (2a) and from right to left (2b) can be executed in parallel if you want. They both use the maximum cached tree as input and generate one new tree each (or set their own fields in the source tree if you prefer this).

3: Then for each tower the amount of water on it min(ltr, rtl) - towerHeight , where ltr is the value of this tower in the monotonous scan from left to right, which we did before, that is, the maximum height is any tower to our left (including us ¹ ) , and rtl same for the arrow from right to left.

4: just summarize this using the tree in O(log n) using n cpu and we are done.

---

¹ If the current tower is above all the towers to our left or above all the towers to our right, min(ltr, rtl) - towerHeight is zero.

Here are two other ways to do this .

Answer 8

You can move first from left to right and calculate the water accumulated for cases when a smaller building is located on the left and the other is on the right. You would have to subtract the area of ​​the buildings between the two buildings and less than the left.

Similarly, it would be right to the left.

Here is the code from left to right. I uploaded this issue to leetcode based online judges using this approach.

I find this approach more intuitive than the standard solution that is present everywhere (calculating the largest building on the right and 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 move the array twice linearly. The complexity of the space would be O (1).

Answer 9

Here is the Groovy solution 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 is a fragment with an online compiler: https://groovy-playground.appspot.com/#?load=3b1d964bfd66dc623c89

Answer 10

The first and last bars on the list cannot catch water. For the remaining towers, they can catch water when there are maximum heights left and right.

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

Iteration on the left, if we know that max_right is greater, min (max_left, max_right) will just become max_left. Therefore, the accumulation of water is simplified: max (max_left - current_height, 0) The same pattern when viewed from the right side.

From the above information, we can write the O (N) and O (1) space algorithm as the following (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

My ugly single workaround span

 def water_collection(buildings): valleyFlag = False water = 0 pool = [] for i, building in enumerate(buildings): if(i == 0): lastHill = building else: if lastHill <= building or i == len(buildings)-1: minHill = min(building, lastHill) print("Hill {} to Hill {}".format(lastHill, building)) summ = 0 for drop in pool: summ += minHill - drop water += minHill - drop print("Collected sum {}".format(summ)) pool = [] valleyFlag = False lastHill = building elif lastHill > building and valleyFlag == False: pool.append(building) valleyFlag = True elif lastHill > building and valleyFlag == True: pool.append(building) print(water) 

Answer 12

Here is another solution written in 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 Euclid-style algorithm, which I find more elegant than all of this scanning:

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

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

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

I wrote the code for this (in the modern Euclidean idiom) here: http://www.rosettacode.org/wiki/Water_collected_between_towers#F.23

Answer 14

I wrote this based on some of the above ideas 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 15

I have a solution that requires only one workaround 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 16

Here is my attempt at jQuery. It only scans to the right.

Working violin (with useful 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 17

Here come here in Python. Pretty sure it works, but didn't test it.

Two passes on the list (but deleting the list when 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 18

An intuitive solution to this problem is one in which you have connected the problem and filled the water based on the height of the left and right borders.

My decision:

• Start on the left side by setting both borders as the 0th index.
• Check and see if there is any trajectory (if you were taking a walk along the tops of these towers, would you ever go down and then again?) If so, then you found the right border.
• Now go back and fill the water accordingly (I just added water to the array by itself, as it makes the code a little cleaner, but this is obviously not required).
• Perforation line: If the height of the left bounding tower is greater than the height of the right bounding tower, than you need to increase the right bound. The reason is that you may run into a higher tower and fill up some more water. However, if the right tower is higher than the left tower, then no more water can be added to your current problem. Thus, you move your left connected to the right border and continue.

Here is the 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 single pass optimization. There is also a very neat stack implementation of this problem, and it uses a similar idea of ​​limitation.

Answer 19

Here is my solution, it goes through this level and is pretty fast, easy to understand. The idea is very simple: firstly, you calculate the maximum height (it can be a multiple of the maximum), then you divide the landscape into 3 parts, from the beginning to the left most maximum level, between the left maximum to right max max and to the right from max to the end.

In the middle part it is easy to collect rains, one for the cycle does it. Then for the first part, you continue to update the current maximum height, which is less than the maximum height of the landscape. one cycle does this. Then for the third part you will undo what you did with 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 20

Here is a solution in JAVA that iterates over a list of numbers once. So the worst case is O (n). (At least as I understand it).

For a given reference number, continue to search for a number greater than or equal to the reference number. Keep a count of the numbers you have traveled with, and save all these numbers in a list.

The idea is this. 5 6 9, 0, , 30 6 9. , 0, , 0. ( 30). , . totalWaterRetained, 9 .

totalWaterRetained .

JAVA: ( . 100% )

 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 21

JavaScript :

 let buildingHeights = [6, 1, 3, 5, 9, 2, 8]; /* * TOTAL store water * */ let max = (n1, n2) => { return n1 > n2 ? n1 : n2; }; let min = (n1, n2) => { return n1 > n2 ? n2 : n1; }; let maxHeightFromLeft = {}, maxHeightFromRight = {}; for (let i = 0; i < buildingHeights.length; i++) { maxHeightFromLeft[i] = max(buildingHeights[i], (i != 0) ? maxHeightFromLeft[i - 1] : 0); } for (let i = buildingHeights.length - 1; i >= 0; i--) { maxHeightFromRight[i] = max(buildingHeights[i], i < (buildingHeights.length - 1) ? maxHeightFromRight[i + 1] : 0); } let totalStorage = 0; for (let i = 0; i < buildingHeights.length; i++) { totalStorage += min(maxHeightFromLeft[i], maxHeightFromRight[i]) - buildingHeights[i]; } console.log(totalStorage); 

Answer 22

 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 23

, , , , . , , , , , . , . , , , . , , , , .

 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 24

Java-, , , Java O (n) , . :

1) , , , var.

2) - var var .

3) , .

 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; } 

, , .

, )

Answer 25

, . LOL , ( ). ( , ...)

, . ( ). , , , , ( , ). , .

  #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); } }