Leetcode # 42. Trapping Rain Water

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

Solution

Time Complexity: O(len(height))
Space Complexity: O(1)

class Solution:
  def trap(self, height: List[int]) -> int:
    i, j = 0, len(height) - 1
    rain = 0
    while i < j:
      cur_h = min(height[i], height[j])
      if height[i] < height[j]:
        while height[i] <= cur_h and i < j:
          rain += cur_h - height[i]
          i += 1
      else:
        while height[j] <= cur_h and i < j:
          rain += cur_h - height[j]
          j -= 1
    return rain
      

Last Updated on 2023/08/16 by A1go