WallAndWater.java

package com.rohankar.problem;

public class WallAndWater {

	public static int findWaterFilled(int[] walls) {
		int maxWallIndex = findMaxWallHeightIndex(walls);
		int volOnLHS = findWaterFilledOnLHS(walls, maxWallIndex);
		int volOnRHS = findWaterFilledOnRHS(walls, maxWallIndex);
		
		return volOnLHS + volOnRHS;
	}

	private static int findMaxWallHeightIndex(int[] walls) {
		int maxWallIndex = 0;
		int max = walls[0];
		for (int i = 0; i < walls.length; i++) {
			if (walls[i] > max) {
				maxWallIndex = i;
				max = walls[maxWallIndex];
			}
		}
		return maxWallIndex;
	}


	private static int findWaterFilledOnLHS(int[] walls, int maxWallIndex) {
		// find left side max
		int maxIdxOnLHS = -1;
		int maxOnLeft = 0;
		for (int j = maxWallIndex - 1; j >= 0; j--) {
			if (walls[j] > maxOnLeft) {
				maxOnLeft = walls[j];
				maxIdxOnLHS = j;
			}
		}

		// calculate on LHS
		int volOnLHS = 0;
		if ((maxWallIndex - maxIdxOnLHS) > 1) {
			for (int i = maxWallIndex - 1; i > 0; i--) {
				volOnLHS += walls[maxIdxOnLHS] - walls[i];
			}
		}
		return volOnLHS;
	}

	private static int findWaterFilledOnRHS(int[] walls, int maxWallIndex) {
		// find right side max
		int maxIdxOnRHS = maxWallIndex;
		int maxOnRight = 0;
		for (int j = maxWallIndex + 1; j < walls.length; j++) {
			if (walls[j] > maxOnRight) {
				maxOnRight = walls[j];
				maxIdxOnRHS = j;
			}
		}

		// calculate on RHS
		int volOnRHS = 0;
		if ((maxIdxOnRHS - maxWallIndex) > 1) {
			for (int i = maxWallIndex + 1; i < walls.length; i++) {
				volOnRHS += walls[maxIdxOnRHS] - walls[i];
			}
		}
		return volOnRHS;
	}
}