Rain water harveting

#1


help???

#2

your approach is not correct
use this and try to implement
if find any difficulty ask to me

  • Approach: The idea is to traverse every array element and find the highest bars on 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.
  • Algorithm:
    1. Traverse the array from start to end.
    2. For every element, traverse the array from start to that index and find the maximum height (a) and traverse the array from the current index to end and find the maximum height (b) .
    3. The amount of water that will be stored in this column is min(a,b) – array[i] , add this value to total amount of water stored
    4. Print the total amount of water stored.
#3

this might sound dumb but can you tell to find maximum im confused

#4

refer this code
i have explained each step in this code

i hope this is helpful

#5

sir code passes 7 test cases bit shows TLE in 3 test cases

#6

yes this is basic approach to understand problem
now try to optimise this

Hint
To make this efficient 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.

logic remain same