Trapped Water Algorithm

TrappedWater.java

import java.util.stream.IntStream;
import java.util.Arrays;

// O(n^2) 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("Volume of trapped water = " + trappedWaterVolume);
    }
    
    public static int getTrappedWater(int[] topography) {
        int volume[] = new int[topography.length];
        
        for (int i = 1; i < topography.length - 1; i++) {
            int height = topography[i];
            int tallestLeft = getTallestLeft(topography, i);
            int tallestRight = getTallestRight(topography, i);
            
            volume[i] = Math.max(0, Math.min(tallestLeft, tallestRight) - height);
        }
        
        return IntStream.of(volume).sum();
    }
    
    public static int getTallestLeft(int[] topography, int index) {
        int max = topography[0];
        for (int i = 0; i < index; i++) {
            if (topography[i] > max) {
                max = topography[i];
            }
        }
        return max;
    }
    
    public static int getTallestRight(int[] topography, int index) {
        int max = topography[topography.length - 1];
        for (int i = topography.length - 1; i >= index; i--) {
            if (topography[i] > max) {
                max = topography[i];
            }
        }
        return max;
    }
}