[FEATURE] Optimize Trapping Rainwater Problem #2975
Description
Detailed description
The current implementation of the trappedRainwater() function uses a prefix max array (leftMax/rightMax) approach to compute trapped water. While this is correct and clear, it uses O(n) extra space.
An optimized two-pointer approach exists for the same problem that achieves O(1) space with the same time complexity of O(n).
Context
The current solution, while correct, uses additional space for prefix arrays. In problems like Trapped Rainwater, where multiple solutions exist, it’s important to adopt the most optimal one, especially in constrained environments like competitive programming or embedded systems.
By switching to the two-pointer approach, we reduce space complexity from O(n) to O(1) while maintaining O(n) time. This makes the solution more efficient and scalable, providing users with a cleaner and more optimal implementation that aligns with best practices.
Possible implementation
No response
Additional information
No response