Rain water hasvesting problem.. But the best solution given to it, is logically complex to produce by oneself for first time. So how to think of it from ground zero and .. also does it help somewhere else too?

#1

Best Approach
Use the two pointer approach. Loop from index 0 to the end of the given array. If a wall greater than or equal to the previous wall is encountered then make note of the index of that wall in a var called previndex. Keep adding previous wall’s height minus the current (ith) wall to the variable water. Have a temporary variable that stores the same value as water. If no wall greater than or equal to the previous wall is found then quit. If previndex < size of the input array then subtract the temp variable from water, and loop from end of the input array to prev_index and find a wall greater than or equal to the previous wall (in this case, the last wall from backwards).

C++ Code

int maxWater_optimized(int arr[], int n)
{
int water = 0; // To store the final ans

int left_max = 0;  // Which stores the current max height of the left side
int right_max = 0; // Which stores the current max height of the right side

int lo = 0;     // Counter to traverse from the left_side
int hi = n - 1; // Counter to traverse from the right_side

while (lo <= hi)
{

    if (arr[lo] < arr[hi])
    {

        if (arr[lo] > left_max)
        {
            left_max = arr[lo]; // Updating left_max
        }
        else
        {

            water += left_max - arr[lo]; // Calculating the ans
        }
        lo++;
    }
    else
    {

        if (arr[hi] > right_max)
        {
            right_max = arr[hi]; // Updating right_max
        }
        else
        {
            water += right_max - arr[hi]; // Calculating the ans
        }
        hi--;
    }
}

return water;

}

I am finding this logic great but can you explain whether this can be used as a general approach in some kind of problems or is this just question specific.

#2

ok, first of all, i agree thinking this from ground zero is a bit tough
but once you are familiar with this kind of approach you will be able to think on similar lines in the future, which happens for most of the questions, so you do not need to worry about that
this particular approach is useful only in similar questions out of which this particular problem is one of the tougher ones, however the stack based approach for this question is quite interesting as well as useful
i will recommend u to learn and understand this approach but focus more on the stack based approach as that will be more helpful in a wider range of questions