Trapped Water Problem O(n)

TrappedWaterFast.java

import java.util.stream.*;
import java.util.Arrays;

// O(n) solution to the Trapped Water Problem
// @see https://techdevguide.withgoogle.com/paths/advanced/volume-of-water/
public class TrappedWater {
    
    public static void main(String args[]) {
        int[] sampleTopography = { 1,3,2,4,1,3,1,4,5,2,2,1,4,2,2 };
        int trappedWaterVolume = getTrappedWater(sampleTopography);

        System.out.println(Arrays.toString(sampleTopography));
        System.out.println("Volume of trapped water = " + trappedWaterVolume);
    }
    
    // Time: O(n), Space: O(n)
    public static int getTrappedWater(int[] topography) {
        int volume = 0;
        
        // Fetch tallest heights to the left and right in O(n)
        int[] tallestLeft = getTallestLeft(topography);
        int[] tallestRight = getTallestRight(topography);
        
        // Calculate the volume for each bar in O(n)
        for (int i = 1; i < topography.length - 1; i++) {
            int height = topography[i];
            int left = tallestLeft[i];
            int right = tallestRight[i];
            
            volume += Math.max(0, Math.min(left, right) - height);
        }
                
        return volume;
    }
    
    public static int[] getTallestLeft(int[] topography) {
        int left[] = new int[topography.length];
        if (topography.length < 2) return left;

        left[0] = topography[0];
        left[topography.length - 1] = topography[topography.length - 1];
        
        for (int i = 1; i < topography.length - 1; i++) {
            left[i] = Math.max(topography[i], left[i - 1]);
        }
        
        return left;
    }
    
    public static int[] getTallestRight(int[] topography) {
        int right[] = new int[topography.length];
        if (topography.length < 2) return right;

        right[0] = topography[0];
        right[topography.length - 1] = topography[topography.length - 1];
        
        for (int i = topography.length - 2; i >= 1; i--) {
            right[i] = Math.max(topography[i], right[i + 1]);
        }
        
        return right;
    }
}