[LeetCode] 42. Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Thought process:
Iterate through the array. For each element, calculate the amount of water trapped in the current position. To do this, we need to iterate through the elements to the left and the right, and find the cap (top of water).

Solution 1 (brute force):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution { public int trap(int[] height) { int len = height.length; int trapped = 0; for (int i = 1; i < len - 1; i++) { int leftTop = 0; int rightTop = 0; for (int j = i - 1; j >= 0; j--) { leftTop = Math.max(leftTop, height[j]); } for (int j = i + 1; j < len; j++) { rightTop = Math.max(rightTop, height[j]); } trapped += Math.max(Math.min(leftTop, rightTop) - height[i], 0); } return trapped; } }

Time complexity: O(n^2).

In the brute force solution, we're calculating leftTop and rightTop for each iteration of the array. This is a lot of duplicate calculation. We can store the tops at the beginning in two arrays before running the main loop.

Solution 2 (DP);

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

class Solution { public int trap(int[] height) { int len = height.length; if (len < 3) { return 0; } int trapped = 0; int[] left = new int[len]; int[] right = new int[len]; left[0] = height[0]; right[len - 1] = height[len - 1]; for (int i = 1; i < len - 1; i++) { left[i] = Math.max(left[i - 1], height[i]); } for (int i = len - 2; i > 0; i--) { right[i] = Math.max(right[i + 1], height[i]); } for (int i = 1; i < len - 1; i++) { trapped += Math.min(left[i], right[i]) - height[i]; } return trapped; } }

We can further optimize the DP solution using two pointers to get a one-pass solution. Instead of creating the left and right arrays before the main loop, we can set one pointer and the beginning of the array, another at the end of the array, and iterate until they collide.

Solution 3 (two pointers);

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

class Solution { public int trap(int[] height) { int water = 0; int left = 0; int right = height.length - 1; int leftTop = 0; int rightTop = 0; while (left < right) { if (height[left] < height[right]) { leftTop = Math.max(leftTop, height[left]); water += leftTop - height[left]; left++; } else { rightTop = Math.max(rightTop, height[right]); water += rightTop - height[right]; right--; } } return water; } }

Time complexity: O(n).