## Amazon Interview Question

Software Developers**Country:**India

1. Compute leftmax and rightmax arrays. leftmax[i] denotes max in arr[0..i]. rightmax[i] denotes max in arr[i..n-1].

2. compute extra[] for each tower.

extra[i] = ( (min(leftmax[i], rightmax[i]) - arr[i] > 0) ? arr[i] : min(leftmax[i], rightmax[i]))

3. compute the ans as in the normal algorithm.

ans += ( (min(leftmax[i], rightmax[i]) - arr[i] > 0) ? min(leftmax[i], rightmax[i]) - arr[i] > 0 : 0)

4. now the final result would be ans + firstmax(extra) + secondmax(extra).

Please let me know if there is anything wrong in this approach.

```
# Let's define a function to capture rainwater
arr = [2,0,4,0,6,0,2,0,1,0]
def trap_rain_water(arr):
#Initialize water variable
water = 0
#Iterate through array and find out volume of water captured at current bar
for i in range(1, len(arr)-1):
vol_at_current_bar = min(max(arr[:i]), max(arr[i:])) - arr[i]
if vol_at_current_bar > 0:
water += vol_at_current_bar
return water
```

}

- divm01986 October 20, 2018