SimuVedaAlgorithms Lab Open in the lab

Patterns / Advanced

Trapping Rain Water Visualizer

Water above a bar = the lower of (tallest wall on its left, tallest wall on its right) minus the bar. Two pointers find this without extra arrays.

Start the Trapping Rain Water simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n)
Average timeO(n)
Worst timeO(n)
Extra spaceO(1)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. The water above a bar depends on the tallest wall on each side. [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
  2. 0 < 1, so the right side is tall enough. Work on the left.
  3. leftMax is 0. No water above index 0.
  4. 1 ≤ 1, so the left side is tall enough. Work on the right.
  5. rightMax is 1. No water above index 11.
  6. 1 < 2, so the right side is tall enough. Work on the left.
  7. leftMax is 1. No water above index 1.
  8. 0 < 2, so the right side is tall enough. Work on the left.
  9. leftMax is 1, so 1 unit of water sit above index 2.
  10. 2 ≤ 2, so the left side is tall enough. Work on the right.
  11. rightMax is 2. No water above index 10.
  12. 1 ≤ 2, so the left side is tall enough. Work on the right.
  13. rightMax is 2, so 1 unit of water sit above index 9.
  14. 2 ≤ 2, so the left side is tall enough. Work on the right.
  15. rightMax is 2. No water above index 8.
  16. 2 < 3, so the right side is tall enough. Work on the left.
  17. leftMax is 2. No water above index 3.
  18. 1 < 3, so the right side is tall enough. Work on the left.
  19. leftMax is 2, so 1 unit of water sit above index 4.
  20. 0 < 3, so the right side is tall enough. Work on the left.
  21. leftMax is 2, so 2 units of water sit above index 5.
  22. 1 < 3, so the right side is tall enough. Work on the left.
  23. leftMax is 2, so 1 unit of water sit above index 6.
  24. Done. Total trapped water: 6.

Try it with your own input →

Trapping rain water in Java, Python, C++, C and JavaScript

int trap(int[] h) {
  int l = 0, r = h.length - 1;
  int leftMax = 0, rightMax = 0, water = 0;
  while (l < r) {
    if (h[l] < h[r]) {
      leftMax = Math.max(leftMax, h[l]);
      water += leftMax - h[l];
      l++;
    } else {
      rightMax = Math.max(rightMax, h[r]);
      water += rightMax - h[r];
      r--;
    }
  }
  return water;
}
def trap(h):
    l, r = 0, len(h) - 1
    left_max = right_max = water = 0
    while l < r:
        if h[l] < h[r]:
            left_max = max(left_max, h[l])
            water += left_max - h[l]
            l += 1
        else:
            right_max = max(right_max, h[r])
            water += right_max - h[r]
            r -= 1
    return water
int trap(const vector<int>& h) {
  int l = 0, r = (int)h.size() - 1;
  int leftMax = 0, rightMax = 0, water = 0;
  while (l < r) {
    if (h[l] < h[r]) {
      leftMax = max(leftMax, h[l]);
      water += leftMax - h[l];
      l++;
    } else {
      rightMax = max(rightMax, h[r]);
      water += rightMax - h[r];
      r--;
    }
  }
  return water;
}
int trap(int h[], int n) {
  int l = 0, r = n - 1;
  int leftMax = 0, rightMax = 0, water = 0;
  while (l < r) {
    if (h[l] < h[r]) {
      if (h[l] > leftMax) leftMax = h[l];
      water += leftMax - h[l];
      l++;
    } else {
      if (h[r] > rightMax) rightMax = h[r];
      water += rightMax - h[r];
      r--;
    }
  }
  return water;
}
function trap(h) {
  let l = 0, r = h.length - 1;
  let leftMax = 0, rightMax = 0, water = 0;
  while (l < r) {
    if (h[l] < h[r]) {
      leftMax = Math.max(leftMax, h[l]);
      water += leftMax - h[l];
      l++;
    } else {
      rightMax = Math.max(rightMax, h[r]);
      water += rightMax - h[r];
      r--;
    }
  }
  return water;
}

In an interview

LeetCode 42, Trapping Rain Water: how much water stays between the bars after rain?

Start by explaining the prefix-max / suffix-max version (O(n) space), then improve to this two-pointer version (O(1) space).

More patterns