Trapping Rain Water

    # 🌧️ Trapping Rain Water - Hard Two Pointer Problem
    #
    # Problem Statement:
    #   Given n non-negative integers representing an elevation map where the width 
    #   of each bar is 1, compute how much water it can trap after raining.
    #
    # Input Examples:
    #   trap([0,1,0,2,1,0,1,3,2,1,2,1]) => 6
    #   trap([3,0,2,0,4]) => 7
    #
    # Algorithm: Two Pointers with Max Heights
    # - Use left and right pointers moving towards center
    # - Track left_max and right_max seen so far
    # - Water trapped at position = min(left_max, right_max) - current_height
    # - Move pointer with smaller max height (bottleneck determines water level)
    #
    # Time Complexity: O(n)
    # Space Complexity: O(1)
    def trap(height)
      return 0 if height.empty? || height.length < 3
      
      left = 0
      right = height.length - 1
      left_max = 0
      right_max = 0
      water_trapped = 0
      
      puts "Starting trap calculation for heights: #{height.inspect}"
      puts "Array length: #{height.length}"
      
      while left < right
        if height[left] < height[right]
          # Process left side (left side is the bottleneck)
          if height[left] >= left_max
            left_max = height[left]
            puts "Left #{left}: New left_max = #{left_max}, no water trapped"
          else
            water = left_max - height[left]
            water_trapped += water
            puts "Left #{left}: height=#{height[left]}, left_max=#{left_max}, water=#{water}, total=#{water_trapped}"
          end
          left += 1
        else
          # Process right side (right side is the bottleneck)
          if height[right] >= right_max
            right_max = height[right]
            puts "Right #{right}: New right_max = #{right_max}, no water trapped"
          else
            water = right_max - height[right]
            water_trapped += water
            puts "Right #{right}: height=#{height[right]}, right_max=#{right_max}, water=#{water}, total=#{water_trapped}"
          end
          right -= 1
        end
        
        puts "  Pointers: left=#{left}, right=#{right}, left_max=#{left_max}, right_max=#{right_max}"
      end
      
      puts "🌧️  Total water trapped: #{water_trapped}"
      water_trapped