Trapping Rain Water

Hard Arrays

Given an elevation map, compute how much rainwater can be trapped. Two-pointer solution in O(n) time and O(1) space.

Sample input

[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

Sample output

Solution

def trap(height):
    left, right = 0, len(height) - 1
    left_max = right_max = 0
    water = 0
    while left < right:
        if height[left] < height[right]:
            left_max = max(left_max, height[left])
            water += left_max - height[left]
            left += 1
        else:
            right_max = max(right_max, height[right])
            water += right_max - height[right]
            right -= 1
    return water

print(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))

function trap(height) {
  let left = 0, right = height.length - 1;
  let leftMax = 0, rightMax = 0, water = 0;
  while (left < right) {
    if (height[left] < height[right]) {
      leftMax = Math.max(leftMax, height[left]);
      water += leftMax - height[left];
      left++;
    } else {
      rightMax = Math.max(rightMax, height[right]);
      water += rightMax - height[right];
      right--;
    }
  }
  return water;
}

console.log(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]));

public class Main {
    static int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0, water = 0;
        while (left < right) {
            if (height[left] < height[right]) {
                leftMax = Math.max(leftMax, height[left]);
                water += leftMax - height[left];
                left++;
            } else {
                rightMax = Math.max(rightMax, height[right]);
                water += rightMax - height[right];
                right--;
            }
        }
        return water;
    }

    public static void main(String[] args) {
        System.out.println(trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
    }
}

fun trap(height: IntArray): Int {
    var left = 0
    var right = height.size - 1
    var leftMax = 0
    var rightMax = 0
    var water = 0
    while (left < right) {
        if (height[left] < height[right]) {
            leftMax = maxOf(leftMax, height[left])
            water += leftMax - height[left]
            left++
        } else {
            rightMax = maxOf(rightMax, height[right])
            water += rightMax - height[right]
            right--
        }
    }
    return water
}

fun main() {
    println(trap(intArrayOf(0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1)))
}

func trap(_ height: [Int]) -> Int {
    var left = 0, right = height.count - 1
    var leftMax = 0, rightMax = 0, water = 0
    while left < right {
        if height[left] < height[right] {
            leftMax = max(leftMax, height[left])
            water += leftMax - height[left]
            left += 1
        } else {
            rightMax = max(rightMax, height[right])
            water += rightMax - height[right]
            right -= 1
        }
    }
    return water
}

print(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))

int trap(List<int> height) {
  var left = 0, right = height.length - 1;
  var leftMax = 0, rightMax = 0, water = 0;
  while (left < right) {
    if (height[left] < height[right]) {
      if (height[left] > leftMax) leftMax = height[left];
      water += leftMax - height[left];
      left++;
    } else {
      if (height[right] > rightMax) rightMax = height[right];
      water += rightMax - height[right];
      right--;
    }
  }
  return water;
}

void main() {
  print(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]));
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int trap(const vector<int>& height) {
    int left = 0, right = height.size() - 1;
    int leftMax = 0, rightMax = 0, water = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            leftMax = max(leftMax, height[left]);
            water += leftMax - height[left];
            left++;
        } else {
            rightMax = max(rightMax, height[right]);
            water += rightMax - height[right];
            right--;
        }
    }
    return water;
}

int main() {
    cout << trap({0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}) << endl;
    return 0;
}

#include <stdio.h>

int trap(int *height, int n) {
    int left = 0, right = n - 1;
    int leftMax = 0, rightMax = 0, water = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] > leftMax) leftMax = height[left];
            water += leftMax - height[left];
            left++;
        } else {
            if (height[right] > rightMax) rightMax = height[right];
            water += rightMax - height[right];
            right--;
        }
    }
    return water;
}

int main() {
    int height[] = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    printf("%d\n", trap(height, 12));
    return 0;
}