Trapping Rain Water Solution for Amazon

Company: Amazon · Difficulty: Hard · Topics: Array, Two Pointers, Dynamic Programming, Stack

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.

Examples

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]

Output: 6

Explanation: The elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]

Output: 9

Explanation: The elevation map is represented by array [4,2,0,3,2,5]. In this case, 9 units of rain water (blue section) are being trapped.

Example 3:

Input: height = [2,0,2]

Output: 2

Explanation: The elevation map is represented by array [2,0,2]. In this case, 2 units of rain water are being trapped.

Intuition

The key insight is that water can only be trapped between two bars that are higher than the current position. The amount of water trapped at any position is determined by the minimum of the maximum heights on the left and right sides, minus the height of the current position.

Approach

Approach 1: Two Pointers (Optimal)

1. Use two pointers (left and right) starting from both ends

2. Keep track of the maximum heights from left and right

3. Move the pointer with the smaller maximum height

4. Calculate trapped water based on the smaller maximum

Approach 2: Dynamic Programming

1. Precompute maximum heights from left and right for each position

2. Calculate trapped water using the minimum of left and right maximums

3. More space efficient than brute force

Approach 3: Stack

1. Use a stack to keep track of indices of bars

2. When a bar is higher than the top of stack, calculate trapped water

3. Less intuitive but efficient

Dry Run

Let's trace through Example 1: height = [0,1,0,2,1,0,1,3,2,1,2,1]

Two Pointers Approach:

• left = 0, right = 11, leftMax = 0, rightMax = 1, water = 0
• height[left] = 0 < height[right] = 1, move left
• left = 1, leftMax = 1, water += max(0, min(1,1) - 1) = 0
• height[left] = 1 = height[right] = 1, move left
• left = 2, leftMax = 1, water += max(0, min(1,1) - 0) = 1
• Continue until all positions are processed

Solution

⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.

Solution 1: Two Pointers (Optimal)

Time Complexity: O(n) - Single pass through array

Space Complexity: O(1) - Constant extra space

Solution 2: Dynamic Programming

Time Complexity: O(n) - Two passes through array

Space Complexity: O(n) - Two arrays for left and right maximums

Solution 3: Stack

Time Complexity: O(n) - Single pass through array

Space Complexity: O(n) - Stack space

More Amazon coding questions