101 Logo
onenoughtone

Solution Approach

Solution Overview

There are 3 main approaches to solve this problem:

  1. Dynamic Programming Approach - Complex approach
  2. Two Pointers Approach - Complex approach
  3. Stack-Based Approach - Complex approach

Approach 1: Dynamic Programming Approach

The dynamic programming approach involves precomputing the maximum height to the left and right of each position. Then, for each position, we can calculate the amount of water that can be trapped.

The key insight is that the amount of water that can be trapped at a position depends on the minimum of the maximum heights to its left and right, minus the height of the building at that position.

Algorithm:

  1. Create two arrays, leftMax and rightMax, to store the maximum height to the left and right of each position.
  2. For each position i, compute leftMax[i] as the maximum of leftMax[i-1] and heights[i].
  3. For each position i, compute rightMax[i] as the maximum of rightMax[i+1] and heights[i].
  4. For each position i, the amount of water trapped is min(leftMax[i], rightMax[i]) - heights[i].
  5. Sum up the water trapped at each position to get the total amount of trapped water.

Time Complexity:

O(n)

Where n is the number of buildings. We need to iterate through the array three times: once to compute leftMax, once to compute rightMax, and once to calculate the trapped water.

Space Complexity:

O(n)

We need two additional arrays of size n to store the maximum heights to the left and right of each position.

Approach 2: Two Pointers Approach

The two pointers approach is a more space-efficient solution. We use two pointers, one starting from the left and one from the right, and move them towards each other.

The key insight is that if the maximum height from the left is less than the maximum height from the right, then the water level at the left pointer is determined by the left maximum. Similarly, if the maximum height from the right is less, then the water level at the right pointer is determined by the right maximum.

Algorithm:

  1. Initialize two pointers, left = 0 and right = n-1, where n is the number of buildings.
  2. Initialize leftMax = heights[left] and rightMax = heights[right].
  3. While left < right:
  4. If leftMax < rightMax, move the left pointer: left++.
  5. Update leftMax if necessary: leftMax = max(leftMax, heights[left]).
  6. Add leftMax - heights[left] to the total trapped water.
  7. Else, move the right pointer: right--.
  8. Update rightMax if necessary: rightMax = max(rightMax, heights[right]).
  9. Add rightMax - heights[right] to the total trapped water.
  10. Return the total trapped water.

Time Complexity:

O(n)

Where n is the number of buildings. We iterate through the array once using the two pointers.

Space Complexity:

O(1)

We only use a constant amount of extra space regardless of the input size.

Approach 3: Stack-Based Approach

The stack-based approach uses a stack to keep track of the indices of buildings that can potentially trap water. We iterate through the array and push the current index onto the stack if the current height is less than or equal to the height at the top of the stack.

When we find a building taller than the one at the top of the stack, we know that water can be trapped between these two buildings, with the amount determined by the heights and the distance between them.

Algorithm:

  1. Initialize an empty stack and a variable to store the total trapped water.
  2. Iterate through the array of heights:
  3. While the stack is not empty and the current height is greater than the height at the top of the stack:
  4. Pop the top of the stack to get the index of the 'bottom' of the potential water trap.
  5. If the stack is now empty, break the loop.
  6. Calculate the width of the water trap as the distance between the current index and the new top of the stack.
  7. Calculate the height of the water trap as the minimum of the current height and the height at the new top of the stack, minus the height at the 'bottom'.
  8. Add width * height to the total trapped water.
  9. Push the current index onto the stack.
  10. Return the total trapped water.

Time Complexity:

O(n)

Where n is the number of buildings. We iterate through the array once, and each building is pushed and popped from the stack at most once.

Space Complexity:

O(n)

In the worst case, all buildings are in decreasing order of height, and we would push all of them onto the stack.

Pseudocode

solution.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function trap(heights):
    n = length of heights
    if n <= 2:
        return 0
    
    // Precompute maximum heights to the left and right
    leftMax = array of size n
    rightMax = array of size n
    
    // Initialize leftMax and rightMax
    leftMax[0] = heights[0]
    rightMax[n-1] = heights[n-1]
    
    // Fill leftMax array
    for i from 1 to n-1:
        leftMax[i] = max(leftMax[i-1], heights[i])
    
    // Fill rightMax array
    for i from n-2 to 0:
        rightMax[i] = max(rightMax[i+1], heights[i])
    
    // Calculate trapped water
    totalWater = 0
    for i from 0 to n-1:
        totalWater += min(leftMax[i], rightMax[i]) - heights[i]
    
    return totalWater
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone