Skip to content

Instantly share code, notes, and snippets.

@andrewnguyen42 andrewnguyen42/waterFill
Last active Dec 29, 2015

Embed
What would you like to do?
An imperative solution to the waterflow problem: http://philipnilsson.github.io/Badness10k/articles/waterflow/
public static int waterFill(int[] arr){
int rainCount=0;
int max=arr[0];
for(int i=0;i<arr.length;i++){
max=(arr[i]>max)?arr[i]:max;
}
//fill it up
for(int i=0;i<arr.length;i++){
rainCount+=max-arr[i];
}
int height=max;
int toRemove;
boolean contained;
//then carve out the space
while(height>0){
toRemove=0;
contained=false;
for(int i=0;i<arr.length;i++){
if(isWall(height,arr[i])&&!contained){
contained=true;
rainCount-=toRemove;
toRemove=0;
}else if(isWall(height,arr[i])&&contained){
toRemove=0;
}
if(!isWall(height,arr[i]))
toRemove++;
}
//remove the water that would have fallen out at the end
if(!isWall(height,arr[arr.length-1])){
rainCount-=toRemove;
}
height--;
}
return rainCount;
}
private static boolean isWall(int height, int indexHeight){
return height<=indexHeight;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.