Hard · Two Pointers
Understand → Visualise → Practice.
At each index, trapped water is controlled by the tallest wall on its left and right. Two pointers avoid storing both arrays of maxima.
Process the shorter side because its opposite boundary is already tall enough; its own maximum determines the water there.
Place pointers at both ends with maxima 0.
Update its maximum and add max − height.
Every position has then been settled once.
O(n) time and O(1) extra space.
Using only neighbouring bars misses water held by distant boundaries.
Read the full guides first: Big-O and Complexity, Arrays and Dynamic Arrays, Prefix Sums and Difference Arrays.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.