Trapping Rain Water LeetCode

DP O(n) time O(n) space

public int trap(int[] A) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
       
       int[] leftMax = new int[A.length];
       int[] rightMax = new int[A.length];
     
       for (int i=0; i<A.length; i++) {
           if (i==0) {
               leftMax[i] = 0;
               rightMax[A.length-1-i] = 0;
           } else {
               leftMax[i] = Math.max(leftMax[i-1], A[i-1]);
               rightMax[A.length-i-1] = Math.max(rightMax[A.length-i], A[A.length-i]);
           }
       }
     
       int sum = 0;
       for (int i=0; i<A.length; i++) {
           int height = Math.min(leftMax[i], rightMax[i]);
           if (height>A[i]) {
               sum+=height-A[i];
           }
       }
       return sum;
    }

But we have to scan twice and spend O(n) space.


Here is a good solution for scanning only once and spend O(1) space.
public int trap(int[] A) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
       
      int l=0, r=A.length-1, res =0;
      while (l<r) {
          int height = Math.min(A[l], A[r]);
         
          if (height == A[l]) {
              l++;
              while (l<r && A[l]<height) {
                  res+=height-A[l];
                  l++;
              }
          } else {
              r--;
              while (l<r && A[r]<height) {
                  res+=height-A[r];
                  r--;
              }
          }
      }
      return res;
    }