Rain water harvesting

#1

please explain other approach than brute force for rainwater harvesting

#2

  • Approach: The idea is to traverse every array element and find the highest bars on the left and right sides. Take the smaller of two heights. The difference between the smaller height and height of the current element is the amount of water that can be stored in this array element.
    you must pre-compute the highest bar on the left and right of every bar in linear time. Then use these pre-computed values to find the amount of water in every array element.

  • Algorithm:

    1. Create two arrays left and right of size n. create a variable max_ = INT_MIN .
    2. Run one loop from start to end. In each iteration update max_ as max_ = max(max_, arr[i]) and also assign left[i] = max_
    3. Update max_ = INT_MIN.
    4. Run another loop from end to start. In each iteration update max_ as max_ = max(max_, arr[i]) and also assign right[i] = max_
    5. Traverse the array from start to end.
    6. The amount of water that will be stored in this column is min(a,b) – array[i] ,(where a = left[i] and b = right[i]) add this value to total amount of water stored
    7. Print the total amount of water stored.

Reference Code

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.