Coding Hard Software Engineer Backend Data Scientist

Given an array of integers `height` representing an elevation map, compute how much water it can trap after raining (Trapping Rain Water).

Practise this question with AI feedback

Record your spoken answer or type your response to receive immediate scoring and STAR improvements.

💡 Suggested Approach & Sample Answer

Optimal Two-Pointer Approach & Code:
- Maintain two pointers inward from left and right, tracking left_max and right_max boundaries to calculate trapped water in O(1) space.

def trap_rain_water(height: list[int]) -> int:
    if not height:
        return 0
    left, right = 0, len(height) - 1
    left_max, right_max = height[left], height[right]
    total_water = 0
    while left < right:
        if left_max < right_max:
            left += 1
            left_max = max(left_max, height[left])
            total_water += left_max - height[left]
        else:
            right -= 1
            right_max = max(right_max, height[right])
            total_water += right_max - height[right]
    return total_water

Complexity & Key Logic:
- Time Complexity: O(N) single pass visiting each bar once.
- Space Complexity: O(1) auxiliary space.
- Algorithm Details:
- Water trapped at any index is determined by min(max_left, max_right) - height[i].
- By advancing the pointer with the smaller boundary, we know that the other side is guaranteed to be taller, so water capacity is bounded strictly by the smaller maximum.

🎯 What Interviewers Listen For

How would you answer this in a real interview?

Use our free AI mock practice tool to test your response, analyze speaking pacing, and refine your STAR structure.

🔗 Related Coding Questions