Skip to main content

42. Trapping Rain Water

https://leetcode.com/problems/trapping-rain-water/

Python​

Calculate on each index (Timelimit Exceed)​

  • Time: O(N^2)
  • Space: O(1)
class Solution:
    def trap(self, height: List[int]) -> int:
        total = 0

        for i in range(1, len(height)):
            left = height[:i]
            right = height[i+1:]

            if not left or not right:
                continue

            cap = min(max(left), max(right))
            if cap - height[i] > 0:
                total += cap - height[i]

        return total

Javascript​

var trap = function(height) {
   let left = 0;
   let right = height.length - 1;
   let maxLeft = height[left];
   let maxRight = height[right];
   let res = 0;

   while (left <= right) {
     if (maxLeft < maxRight) {
       if ((maxLeft - height[left]) > 0) res += (maxLeft - height[left]);
       maxLeft = Math.max(maxLeft, height[left]);
       left++;
     } else {
       if ((maxRight - height[right]) > 0) res += (maxRight - height[right]);
       maxRight = Math.max(maxRight, height[right]);
       right--;
     }
   }
   return res;
};