• Couldn’t solve the problem, got 50% of the logic only
• Here’s how the solutions work

Approach 1: O(n) Space - Two Arrays (Easier to conceptualize)

Core Idea: Pre-compute the maximum heights on the left and right of every position, then calculate water trapped.

Steps:

1. Create two arrays: max_left[] and max_right[], both of size n
2. First pass (left to right): Fill max_left[i] = maximum height from index 0 to i
   • max_left[0] = height[0]
   • max_left[i] = max(max_left[i-1], height[i])
3. Second pass (right to left): Fill max_right[i] = maximum height from index i to end
   • max_right[n-1] = height[n-1]
   • max_right[i] = max(max_right[i+1], height[i])
4. Third pass: For each position, calculate water:
   • water_at_i = min(max_left[i], max_right[i]) - height[i]
   • If positive, add to total; if negative/zero, no water trapped

Why it works: You have complete information about what's on both sides of every position before calculating water.

Time: O(n) - three passes Space: O(n) - two arrays

Approach 2: O(1) Space - Two Pointers (Optimal but trickier)

Core Idea: Use two pointers moving from both ends, maintaining running maximums, and only calculate water on the side with the SMALLER maximum.

Key Insight: You don't need to know BOTH max_left and max_right for a position if you know one side's max is definitely smaller. The smaller side is the bottleneck (determines water level), so you can calculate water there immediately.

Steps:

1. Initialize: left = 0, right = n-1, left_max = 0, right_max = 0, water = 0
2. While left < right:
   • Update maximums:
     • left_max = max(left_max, height[left])
     • right_max = max(right_max, height[right])
   • Decision point: Compare left_max vs right_max
     • If left_max < right_max:
       • Water at left position = left_max - height[left]
       • Move left++ (we know left side is bottleneck)
     • Else:
       • Water at right position = right_max - height[right]
       • Move right-- (we know right side is bottleneck)

Why it works:

• When left_max < right_max, you KNOW the water level at position left is determined by left_max (regardless of what's beyond right)