algorithmdata-structuresstack# How to get the water level in each bar of a histogram after raining?

There is a well-known problem called Trapping Rain Water or something similar. In this problem, you have to find the maximum amount of water that can stay inside the given histogram after it rains. I have a different version of this problem. I want to find the water level in each bar of a histogram. For example, look at this picture:

The input of this histogram is this array: `{0, 3, 0, 2, 0, 4, 0}`

The output (water level in each bar) is this array: `{0, 0, 3, 1, 3, 0, 0}`

Please note that each element of the output is the height of water in that bar. It does not matter where the water starts and ends.

How can I change the algorithm linked to the question to get this output?

The complexity should not increase. It should be `O(n)`

.

Solution

The original algorithm (with precalculation, which has O(𝑛) complexity) does not need much change. I will use as reference here the Python version of that algorithm, as contributed by Smitha Dinesh Semwal on GeeksForGeeks:

```
def findWater(arr, n):
left = [0]*n
right = [0]*n
water = 0
left[0] = arr[0]
for i in range(1, n):
left[i] = max(left[i-1], arr[i])
right[n-1] = arr[n-1]
for i in range(n-2, -1, -1):
right[i] = max(right[i + 1], arr[i])
for i in range(0, n):
water += min(left[i], right[i]) - arr[i]
return water
```

We see how the final loop adds vertical stacks of water to the final result. And as these vertical stacks are exactly what you want to get in an array (list) output, the change to that last loop is rather trivial:

```
result = []
for i in range(0, n):
result.append(min(left[i], right[i]) - arr[i])
return result
```

- How to generate uniformly distributed subintervals of an interval?
- Generating random number in a non-power-of-2 range from random bits
- Algorithm - Search and Replace a string
- Looking for a branchless algorithm for converting a specific set of 4-bit integers
- Different results for XIRR between Excel and ExcelFinancialFunctions 3.2.0
- Find four,whose sum equals to target
- A* algorithm can't find the goal in Python
- Efficiently getting all divisors of a given number
- Are there any existed API to split IEnumerable<T> to many Vector<T> in CSharp？
- Generating all divisors of a number given its prime factorization
- Efficient way to insert a number into a sorted array of numbers?
- BFS Maximize Minimum Distance from a Monster along a path
- Is there effective algorithm that will return all different combination?
- Big O of algorithm that steps over array recursively
- Modification of Dijkstra's algorithm to make it work with negative weights and its time complexity
- Traversing/Moving over an unfolded cube
- Fibonacci Recursion using Golden Ratio(Golden Number)
- Karatsuba implementation in C
- Why is O(n) better than O( nlog(n) )?
- What is Sliding Window Algorithm? Examples?
- How to write a function to navigate through a non-binary tree?
- Evenly distribute QDate values into certain number of slots
- Find max product using divide and conqure in O(n) time
- Cache-friendly sqare matrix transposition logic issue
- Why doesn't Dijkstra's algorithm work for negative weight edges?
- Fast Convertion From Adjacency List to Edge List
- I convert ASCII words into numbers but am stuck trying to decode them. How to convert 1=a, 2=b, 28=ab etc? (psudeocode okay)
- Reversing the word order in a string in place
- Trying to make a 2x2 rubik's cube solving algorithm , how do i find the solution path (DFS)?
- question about missing element in array