Problem statement - Maximum water in a section
Problem statement -
Chef owns a swimming pool with width N meters which contains N continuous walls with height h[i] (possible zero) and width 1 meter each.
When it rains heavily, water is stored in the swimming pool in the form of sections (check Figure 1). Chef is busy calling his friends for a party. So, you need to determine the maximum water stored in a section among all the sections after a heavy rain.
Approach
We use a stack to track wall heights while iterating through the array:
- Push the current wall index onto the stack.
- If the current wall is taller than the top of the stack, pop the stack to calculate water trapped based on the height difference between the surrounding walls.
- Update the array that tracks the trapped water for each wall.
- After processing, the maximum value from this array gives the most water stored.
This ensures efficient water calculation between walls.
Time Complexity
- O(N): The algorithm processes each wall height once and each wall is pushed and popped from the stack at most once.
Space Complexity
- O(N): The stack and the dp array both require space proportional to the number of walls N.