42. Trapping Rain Water#

Brute-force#

class Solution {

  public int trap(int[] height) {
    //return bruteForce(height);
    //return memoization(height);
    return twoPointer(height);
  }

  /**
   * Intuition:
   * For a given index the amount of water it contains depends on
   * left max height, right max height and it's own height
   * MIN(left max height, right max height) - own height
   */

  /**
   * Approach 1: Brute Force - Calculate leftMax and rightMax for each index
   * and calculate capacity add to result
   *
   * Time Complexity: O(n^2)
   * Space Complexity: O(1)
   */
  public int bruteForce(int[] height) {
    int n = height.length;
    int result = 0;

    for (int i = 1; i < n - 1; i++) {
      int leftMax = 0;
      int rightMax = 0;

      for (int j = i; j >= 0; j--) {
        leftMax = Math.max(height[j], leftMax);
      }

      for (int j = i; j < n; j++) {
        rightMax = Math.max(height[j], rightMax);
      }

      // if height[i] itself is the highet then
      // leftMax == rightMax == height[i]

      result += Math.min(leftMax, rightMax) - height[i];
    }

    return result;
  }
}

Memoization#

 1/**
 2 * Approach 2: Memoization - Calculate left max and right max for all indices
 3 * and loop throught to calculate result from the stored result.
 4 *
 5 * Time Complexity: O(n) actually 3n
 6 * Space Complexity: O(n) actually 2n
 7 */
 8public int memoization(int[] heights) {
 9  int n = heights.length;
10  int result = 0;
11
12  int[] leftMax = new int[n];
13  int[] rightMax = new int[n];
14
15  leftMax[0] = heights[0];
16  rightMax[n - 1] = heights[n - 1];
17
18  // exclude left-most
19  for (int i = 1; i < n; i++) {
20    leftMax[i] = Math.max(heights[i], leftMax[i - 1]);
21  }
22
23  // exclude right-most
24  for (int i = n - 2; i >= 0; i--) {
25    rightMax[i] = Math.max(heights[i], rightMax[i + 1]);
26  }
27
28  for (int i = 1; i < n - 1; i++) {
29    result += Math.min(leftMax[i], rightMax[i]) - heights[i];
30  }
31
32  return result;
33}

Two-pointer#

Approach:

Use two pointers - Using the observation that holding capacity depends on the min value not on the max. leftMax always represent max of [start…left], rightMax always represent max of [right...end].

 1public int twoPointer(int[] height) {
 2  int n = height.length;
 3  int result = 0;
 4
 5  int left = 0;
 6  int right = n - 1;
 7
 8  int leftMax = height[0];
 9  int rightMax = height[n - 1];
10
11  while (left <= right) {
12    leftMax = Math.max(leftMax, height[left]);
13    rightMax = Math.max(rightMax, height[right]);
14
15    if (leftMax < rightMax) {
16      result += leftMax - height[left];
17      left++;
18    } else {
19      result += rightMax - height[right];
20      right--;
21    }
22  }
23
24  return result;
25}

Time Complexity

Space Complexity

\(\mathcal{O}(n)\)

\(\mathcal{O}(1)\)