Skip to content

Instantly share code, notes, and snippets.

@andrewnguyen42
Last active December 29, 2015 23:49
Show Gist options
  • Save andrewnguyen42/7745194 to your computer and use it in GitHub Desktop.
Save andrewnguyen42/7745194 to your computer and use it in GitHub Desktop.
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