Skip to content

Instantly share code, notes, and snippets.

@sagarr

sagarr/WallAndWater.java

Created December 7, 2013 06:29
Show Gist options
  • Save sagarr/7837934 to your computer and use it in GitHub Desktop.
Save sagarr/7837934 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment