Two Pointers technique: Trapping Water (Array)

42. Trapping Rain Water in Rust, Scala, Java and Python

Task: count how many tiles are blue (with water)

Answer: is 6.

Hint:

You need to store counter for tiles of water. Let’s call it trappedWater = 0.

Our 2 pointers:

left = 0 — pointer for the left side

right = height.length — 1 — pointer for the right side

And to track tallest tower seen from left and right.

leftMax = 0 — to keep track of the maximum height on the left

rightMax = 0 — to keep track of the maximum height on the right

Water trapped by any tower depends on the minimum of maximum height of towers on both sides.

Algorithm

1. Move the pointers towards each other: while (left < right){…}
2. If the height at the left pointer is less than the height at the right pointer => update the leftMax and calculate the trapped water on the left:

if (height[left] < height[right]) {
   leftMax = Math.max(leftMax, height[left]);
   trappedWater += leftMax - height[left];
   left++;
} 

3. Else the height at the right pointer is less than or equal to the height at the left pointer => update the rightMax and calculate the trapped water on the right:

else {
      rightMax = Math.max(rightMax, height[right]);
      trappedWater += rightMax - height[right];
      right--;
}

Rust

impl Solution {
    pub fn trap(height: Vec<i32>) -> i32 {
         if height.is_empty() {
        return 0;
    }

    let mut left = 0;
    let mut right = height.len() - 1;
    let mut left_max = 0;
    let mut right_max = 0;
    let mut trapped_water = 0;

    while left < right {
        if height[left] < height[right] {
            left_max = left_max.max(height[left]);
            trapped_water += left_max - height[left];
            left += 1;
        } else {
            right_max = right_max.max(height[right]);
            trapped_water += right_max - height[right];
            right -= 1;
        }
    }

    trapped_water
    }
}

Scala

object Solution {
    def trap(height: Array[Int]): Int = {
         if (height == null || height.length == 0) {
         return 0
    }

    var left = 0
    var right = height.length - 1
    var leftMax = 0
    var rightMax = 0
    var trappedWater = 0

    while (left < right) {
      if (height(left) < height(right)) {
        leftMax = leftMax.max(height(left))
        trappedWater += leftMax - height(left)
        left += 1
      } else {
        rightMax = rightMax.max(height(right))
        trappedWater += rightMax - height(right)
        right -= 1
      }
    }

    trappedWater
    }
}

Java

public class TrapRainWater {

    public static int trap(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }

        int left = 0; // pointer for the left side
        int right = height.length - 1; // pointer for the right side
        int leftMax = 0; // to keep track of the maximum height on the left
        int rightMax = 0; // to keep track of the maximum height on the right
        int trappedWater = 0;

        while (left < right) {
            // Move the pointers towards each other
            if (height[left] < height[right]) {
                // If the height at the left pointer is less than the height at the right pointer
                // Update the leftMax and calculate the trapped water on the left
                leftMax = Math.max(leftMax, height[left]);
                trappedWater += leftMax - height[left];
                left++;
            } else {
                // If the height at the right pointer is less than or equal to the height at the left pointer
                // Update the rightMax and calculate the trapped water on the right
                rightMax = Math.max(rightMax, height[right]);
                trappedWater += rightMax - height[right];
                right--;
            }
        }

        return trappedWater;
    }
}

Python

class Solution(object):
    def trap(self, height):
        if not height:
            return 0

        left, right = 0, len(height) - 1
        left_max, right_max = 0, 0
        trapped_water = 0

        while left < right:
            if height[left] < height[right]:
                left_max = max(left_max, height[left])
                trapped_water += left_max - height[left]
                left += 1
            else:
                right_max = max(right_max, height[right])
                trapped_water += right_max - height[right]
                right -= 1

        return trapped_water

Complexity analysis

This algorithm has a time complexity of O(N) and a space complexity of O(1), where N is the length of the input array.