Classic 150 Interview Questions P42 Trapping Rain Water

---

Timeline

Timeline

2025-11-05

init

Two pointers

---

Problem:

P42 Trapping Rain Water

https://leetcode.cn/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-interview-150

Each time pour water into the lowest place, similar to the 3D idea below, and it can also be considered a simplified version.

Reference:

P407 Trapping Rain Water II

https://even629.com/posts/407/

#include <vector>
#include <algorithm>
using std::vector;

class Solution {
    public:
	int trap(vector<int> &height)
	{
		int n = height.size();
		int left = 0, right = n - 1;
		int rain = 0;

		while (left < right) {
			// Pour water into the lowest place on the boundary.
			if (height[left] < height[right]) {
				if (height[left + 1] < height[left]) {
					rain += height[left] - height[left + 1];
					height[left + 1] = height[left];
				}
				left++;
			} else {
				if (height[right - 1] < height[right]) {
					rain += height[right] - height[right - 1];
					height[right - 1] = height[right];
				}
				right--;
			}
		}
		return rain;
	}
};

hot100 rewrite

#include <vector>
using std::vector;

class Solution {
    public:
        int trap(vector<int> &height)
        {
                int n = height.size(), i = 0, j = n - 1;
                int water = 0;

                while (i < j && height[i] == 0) {
                        i++;
                }
                while (j > i && height[j] == 0) {
                        j--;
                }

                int tmp;
                while (i < j) {
                        if (height[i] <= height[j]) {
                                tmp = i;
                                i++;
                                while (i < j && height[i] < height[tmp]) {
                                        water += height[tmp] - height[i];
                                        i++;
                                }
                        } else {
                                tmp = j;
                                j--;
                                while (i < j && height[j] < height[tmp]) {
                                        water += height[tmp] - height[j];
                                        j--;
                                }
                        }
                }
                return water;
        }
};