~/leetcode $ 42. Trapping-Rain-Water

Last problem in two pointers… This feels like a similar problem to the one that I did yesterday, where we have a left and a right pointer representing the left and right’walls’. Thinking about where to initialise these pointers, if we initialise both of them at the start, how would we update them?

Because the left pointer represents the current left wall of the container, we can keep track of the container of water that would be contained if we ended with a wall that is at least as big as the left wall. When the right wall is as big as the left wall, then we know that the current water amount is guaranteed to be trapped, so we add this sum to the result and update the left pointer to be the same as the right pointer.

Then, we need to consider the case where we do not come across a wall that is as large as the left wall by the time we reach the end of the list. A realisation that I had is that the result should be the same either direction, therefore, we can just rerun the same algorithm but with the two pointers initialised at the end of the list and moving backwards.

The algorithm first calculates all the water that is guaranteed trapped when going left to right and then calculates all the water that is guaranteed to be trapped going right to left. We need to think about duplicates that are possible and subtracting these off as well. Duplicates occur when the left and right walls are the same (these will be counted in both iterations) so we can just ignore these when we go backwards

class Solution {
public:
    int trap(vector<int>& height) {
        int l = 0;
        int result = 0;

        // forward iteration
        int currWater = 0;
        for (int r = 0; r < height.size(); ++r) {
            if (height[r] >= height[l]) {
                result += currWater;
                currWater = 0;
                l = r;
            } else {
                currWater += (height[l] - height[r]);
            }
        }

        // backward iteration
        l = height.size() - 1;
        currWater = 0;
        for (int r = height.size() - 1; r >= 0; --r) {
            if (height[r] > height[l]) {
                result += currWater;
                currWater = 0;
                l = r;
            } else {
                currWater += (height[l] - height[r]);
            }
        }

        return result;
    }
}

Time Complexity: O(n)

Space Complexity: O(1)

Time Taken: 3m 35s