Create a gist now

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Twitter Interview Solution
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
int[] myIntArray = {2, 5, 1, 2, 3, 4, 7, 7, 6};
System.out.println(calculateVolume(myIntArray));
}
public static int calculateVolume(int[] land) {
int leftMax = 0;
int rightMax = 0;
int left = 0;
int right = land.length - 1;
int volume = 0;
while(left < right) {
if(land[left] > leftMax) {
leftMax = land[left];
}
if(land[right] > rightMax) {
rightMax = land[right];
}
if(leftMax >= rightMax) {
volume += rightMax - land[right];
right--;
} else {
volume += leftMax - land[left];
left++;
}
}
return volume;
}
}
@igor47

This comment has been minimized.

Show comment
Hide comment
@igor47

igor47 Oct 30, 2013

fun problem! i took a stab at it also: https://gist.github.com/igor47/7228586

igor47 commented Oct 30, 2013

fun problem! i took a stab at it also: https://gist.github.com/igor47/7228586

@sathya-me

This comment has been minimized.

Show comment
Hide comment
@sathya-me

sathya-me Oct 30, 2013

will this work for the following case [2,7,2,7,4,7,1,7,3,7]

sathya-me commented Oct 30, 2013

will this work for the following case [2,7,2,7,4,7,1,7,3,7]

@joist

This comment has been minimized.

Show comment
Hide comment
@joist

joist Oct 30, 2013

@sathya-me : It does handle it properly. The left and the right pointers rise to 7 and then fill in all the gaps until they meet.

I tried my own hand at this problem and came up with a slightly more naive (but clearer) solution : https://gist.github.com/Joist/7229807

edit: I put my own attempt at the single pass method in my code with comments to make it a bit clearer.

joist commented Oct 30, 2013

@sathya-me : It does handle it properly. The left and the right pointers rise to 7 and then fill in all the gaps until they meet.

I tried my own hand at this problem and came up with a slightly more naive (but clearer) solution : https://gist.github.com/Joist/7229807

edit: I put my own attempt at the single pass method in my code with comments to make it a bit clearer.

@msimpson

This comment has been minimized.

Show comment
Hide comment
@msimpson

msimpson Oct 30, 2013

I wrote up a solution using JS, here: https://gist.github.com/msimpson/eb0189dd687d696ab70a

Mine is based on the point-inside-polygon methodology. It is more complex than what is above, and generates a maximum height at the start. However, it would continue to work with only slight modification on a two, or possibly three, dimensional matrix -- even with gaps inside columns that create enclosed areas.

msimpson commented Oct 30, 2013

I wrote up a solution using JS, here: https://gist.github.com/msimpson/eb0189dd687d696ab70a

Mine is based on the point-inside-polygon methodology. It is more complex than what is above, and generates a maximum height at the start. However, it would continue to work with only slight modification on a two, or possibly three, dimensional matrix -- even with gaps inside columns that create enclosed areas.

@orukusaki

This comment has been minimized.

Show comment
Hide comment
@dmitry

This comment has been minimized.

Show comment
Hide comment
@dmitry

dmitry Oct 30, 2013

Looked for the solutions and rewritten them to the ruby: https://gist.github.com/dmitry/287bd6cad9abc70436f4

dmitry commented Oct 30, 2013

Looked for the solutions and rewritten them to the ruby: https://gist.github.com/dmitry/287bd6cad9abc70436f4

@shaobohou

This comment has been minimized.

Show comment
Hide comment
@shaobohou

shaobohou commented Oct 30, 2013

Another single pass solution, https://gist.github.com/shaobohou/7231961

@Shruubi

This comment has been minimized.

Show comment
Hide comment
@Shruubi

Shruubi Oct 30, 2013

Did up a small Python solution passing both test cases: https://gist.github.com/Shruubi/7232152

Shruubi commented Oct 30, 2013

Did up a small Python solution passing both test cases: https://gist.github.com/Shruubi/7232152

@Zibx

This comment has been minimized.

Show comment
Hide comment
@Zibx

Zibx Oct 30, 2013

JS implementation. 2n complexity https://gist.github.com/Zibx/7235776

Zibx commented Oct 30, 2013

JS implementation. 2n complexity https://gist.github.com/Zibx/7235776

@thisvar

This comment has been minimized.

Show comment
Hide comment
@thisvar

thisvar Oct 30, 2013

Java, n complexity, single straight pass from left to right : https://gist.github.com/anonymous/7236132

thisvar commented Oct 30, 2013

Java, n complexity, single straight pass from left to right : https://gist.github.com/anonymous/7236132

@twuttke

This comment has been minimized.

Show comment
Hide comment
@twuttke

twuttke Oct 30, 2013

Slightly simpler, slightly faster, and handles negative heights: http://jsbin.com/iquQOSo/1/edit

function maxWater(heights) {
  var left = 0,
      right = heights.length - 1,
      leftMax = heights[left],
      rightMax = heights[right],
      volume = 0;

  while (left < right) {
    if (leftMax < rightMax) {
      var height = heights[++left];
      leftMax = Math.max(leftMax, height);
      volume += leftMax - height;
    } else {
      var height = heights[--right];
      rightMax = Math.max(rightMax, height);
      volume += rightMax - height;
    }  
  }
  return volume;
}

twuttke commented Oct 30, 2013

Slightly simpler, slightly faster, and handles negative heights: http://jsbin.com/iquQOSo/1/edit

function maxWater(heights) {
  var left = 0,
      right = heights.length - 1,
      leftMax = heights[left],
      rightMax = heights[right],
      volume = 0;

  while (left < right) {
    if (leftMax < rightMax) {
      var height = heights[++left];
      leftMax = Math.max(leftMax, height);
      volume += leftMax - height;
    } else {
      var height = heights[--right];
      rightMax = Math.max(rightMax, height);
      volume += rightMax - height;
    }  
  }
  return volume;
}
@olajep

This comment has been minimized.

Show comment
Hide comment
@olajep

olajep Oct 30, 2013

Did a quick Haskell solution: https://gist.github.com/olajep/7236551

rainSolver = solve 0

solve acc [] = acc
solve acc (x:xs)
  | xs' == [] = solve acc xs -- no right border -> this x cannot be left border
  | otherwise = solve (acc+area) xs'
  where
    height      = minimum [x, maximum xs]
    (elems,xs') = span (<height) xs
    area        = (length elems * height) - (sum elems)

olajep commented Oct 30, 2013

Did a quick Haskell solution: https://gist.github.com/olajep/7236551

rainSolver = solve 0

solve acc [] = acc
solve acc (x:xs)
  | xs' == [] = solve acc xs -- no right border -> this x cannot be left border
  | otherwise = solve (acc+area) xs'
  where
    height      = minimum [x, maximum xs]
    (elems,xs') = span (<height) xs
    area        = (length elems * height) - (sum elems)
@Zibx

This comment has been minimized.

Show comment
Hide comment
@AndroidHumanoid

This comment has been minimized.

Show comment
Hide comment
@AndroidHumanoid

AndroidHumanoid Oct 30, 2013

Short Java
http://it.laplit.com/index.php/humanoid-blog/128-article-7
https://gist.github.com/AndroidHumanoid/7241202

public static int mycalculateVolume(int[] land) {
int leftMax = 0;
int subvolume = 0;
int volume = 0;

    for (int index = 0; index < land.length; index++) {
        if (land[index] >= leftMax){
            leftMax = land[index];  
            volume = volume + subvolume;
            subvolume = 0;
        }
        else {
            subvolume = subvolume + leftMax - land[index];
        }
    }
    return volume;
}

AndroidHumanoid commented Oct 30, 2013

Short Java
http://it.laplit.com/index.php/humanoid-blog/128-article-7
https://gist.github.com/AndroidHumanoid/7241202

public static int mycalculateVolume(int[] land) {
int leftMax = 0;
int subvolume = 0;
int volume = 0;

    for (int index = 0; index < land.length; index++) {
        if (land[index] >= leftMax){
            leftMax = land[index];  
            volume = volume + subvolume;
            subvolume = 0;
        }
        else {
            subvolume = subvolume + leftMax - land[index];
        }
    }
    return volume;
}
@hwmrocker

This comment has been minimized.

Show comment
Hide comment
@hwmrocker

hwmrocker commented Oct 30, 2013

me too, i used just one iteration https://gist.github.com/hwmrocker/7241002

@pavelfatin

This comment has been minimized.

Show comment
Hide comment
@pavelfatin

pavelfatin commented Oct 30, 2013

O(n) recursive one-liners (Haskell, Clojure, Scala)

@domluna

This comment has been minimized.

Show comment
Hide comment
@domluna

domluna Oct 31, 2013

Solution in julia, just did a simple linear walkthrough https://gist.github.com/Niessy/7243069

domluna commented Oct 31, 2013

Solution in julia, just did a simple linear walkthrough https://gist.github.com/Niessy/7243069

@amuraco

This comment has been minimized.

Show comment
Hide comment
@amuraco

amuraco Oct 31, 2013

Single Iteration Streaming Java solution. Not that memory friendly though.
https://gist.github.com/amuraco/7244151

amuraco commented Oct 31, 2013

Single Iteration Streaming Java solution. Not that memory friendly though.
https://gist.github.com/amuraco/7244151

@jdanielmyers

This comment has been minimized.

Show comment
Hide comment
@jdanielmyers

jdanielmyers Oct 31, 2013

pretty simple single pass python solution: https://gist.github.com/jdanielmyers/7245316

jdanielmyers commented Oct 31, 2013

pretty simple single pass python solution: https://gist.github.com/jdanielmyers/7245316

@leikind

This comment has been minimized.

Show comment
Hide comment
@leikind

leikind Oct 31, 2013

My take: https://gist.github.com/leikind/7247086

Maybe not the most efficient, but it's only 10 lines of code of functional style Ruby

leikind commented Oct 31, 2013

My take: https://gist.github.com/leikind/7247086

Maybe not the most efficient, but it's only 10 lines of code of functional style Ruby

@abo-abo

This comment has been minimized.

Show comment
Hide comment
@abo-abo

abo-abo Oct 31, 2013

My take in Clojure: https://gist.github.com/abo-abo/7247459 .
Not the best efficiency, but very straightforward.

abo-abo commented Oct 31, 2013

My take in Clojure: https://gist.github.com/abo-abo/7247459 .
Not the best efficiency, but very straightforward.

@flowolf

This comment has been minimized.

Show comment
Hide comment
@flowolf

flowolf commented Oct 31, 2013

here is my Python solution:
https://gist.github.com/flowolf/7247585

@KvanTTT

This comment has been minimized.

Show comment
Hide comment
@KvanTTT

KvanTTT Oct 31, 2013

There is my awful but satisfactory solution with all answers generation for predifined count of walls and max wall height (in my case 8 * 8): https://github.com/KvanTTT/Twitter-Puddles-Counter

But it's not ideal. Number of answers can be reduced to 4 times due to symmetry along x and y axis. I mean
V(x_1, x_2, ..., x_n) = V(x_n, x_n-1, ..., x_1) and V(x_1, x_2, ..., x_n) = n*h - V(h - x_1, h - x_2, ..., h - x_n). Possible there are another dependencies from input heights which are not so clear.

KvanTTT commented Oct 31, 2013

There is my awful but satisfactory solution with all answers generation for predifined count of walls and max wall height (in my case 8 * 8): https://github.com/KvanTTT/Twitter-Puddles-Counter

But it's not ideal. Number of answers can be reduced to 4 times due to symmetry along x and y axis. I mean
V(x_1, x_2, ..., x_n) = V(x_n, x_n-1, ..., x_1) and V(x_1, x_2, ..., x_n) = n*h - V(h - x_1, h - x_2, ..., h - x_n). Possible there are another dependencies from input heights which are not so clear.

@Areks

This comment has been minimized.

Show comment
Hide comment
@Areks

Areks Oct 31, 2013

Hello guys, let me show my decision ))
function calc(input){
if (input.length < 3) return 0;
var v = 0,
sort = input.slice(0).sort(function(x,y){return y-x}),
a = input.indexOf(sort[0]),
b = input.indexOf(sort[1], (sort[0]==sort[1]) ? a+1 : 0),
last, first = ( a > b ) ? (last=a,b) : (last=b,a);
for (var j = first+1; j < last; j++ ) v+=sort[1]-input[j];
return v + calc(input.filter(function(z,y){return (y < first-1) || (y >= last) }))
}

Areks commented Oct 31, 2013

Hello guys, let me show my decision ))
function calc(input){
if (input.length < 3) return 0;
var v = 0,
sort = input.slice(0).sort(function(x,y){return y-x}),
a = input.indexOf(sort[0]),
b = input.indexOf(sort[1], (sort[0]==sort[1]) ? a+1 : 0),
last, first = ( a > b ) ? (last=a,b) : (last=b,a);
for (var j = first+1; j < last; j++ ) v+=sort[1]-input[j];
return v + calc(input.filter(function(z,y){return (y < first-1) || (y >= last) }))
}

@lutzik

This comment has been minimized.

Show comment
Hide comment
@lutzik

lutzik Oct 31, 2013

PHP solution:

public function findVolume($arr) {
$v = 0;
$l = 0;
$r = count($arr) - 1;

while ($l < count($arr) && $arr[$l + 1] >= $arr[$l]) {
    $l++;
}

while ($r > 0 && $arr[$r - 1] >= $arr[$r]) {
    $r--;
}

$pointer = $l;

while (++$pointer < $r) {
    $v += $arr[$l] - $arr[$pointer];
} 

$return $v;

}

lutzik commented Oct 31, 2013

PHP solution:

public function findVolume($arr) {
$v = 0;
$l = 0;
$r = count($arr) - 1;

while ($l < count($arr) && $arr[$l + 1] >= $arr[$l]) {
    $l++;
}

while ($r > 0 && $arr[$r - 1] >= $arr[$r]) {
    $r--;
}

$pointer = $l;

while (++$pointer < $r) {
    $v += $arr[$l] - $arr[$pointer];
} 

$return $v;

}

@fergara

This comment has been minimized.

Show comment
Hide comment
@ghost

This comment has been minimized.

Show comment
Hide comment
@ghost

ghost Oct 31, 2013

@AndroidHumanoid
I like your solution, but unfortunately it doesn't work for [2, 5, 1, 2, 3, 4, 7, 5, 6] which should give 11.

ghost commented Oct 31, 2013

@AndroidHumanoid
I like your solution, but unfortunately it doesn't work for [2, 5, 1, 2, 3, 4, 7, 5, 6] which should give 11.

@oralokan

This comment has been minimized.

Show comment
Hide comment
@oralokan

oralokan Oct 31, 2013

I did a python implementation based on a simple observation. For a square to be filled with water, it has to fulfill these two conditions:

  1. It has to be a free-space square (as opposed to a solid block) to begin with.
  2. There has to be a solid block at the same height on either side of it (not necessarily adjacently)

https://gist.github.com/oralokan/107958531b3e33062bc5

oralokan commented Oct 31, 2013

I did a python implementation based on a simple observation. For a square to be filled with water, it has to fulfill these two conditions:

  1. It has to be a free-space square (as opposed to a solid block) to begin with.
  2. There has to be a solid block at the same height on either side of it (not necessarily adjacently)

https://gist.github.com/oralokan/107958531b3e33062bc5

@ubermajestix

This comment has been minimized.

Show comment
Hide comment
@ubermajestix

ubermajestix Oct 31, 2013

Here's my solution in ruby that prints the board: https://gist.github.com/ubermajestix/7253875

ubermajestix commented Oct 31, 2013

Here's my solution in ruby that prints the board: https://gist.github.com/ubermajestix/7253875

@DrewFitz

This comment has been minimized.

Show comment
Hide comment
@DrewFitz

DrewFitz Oct 31, 2013

Here's mine which solves it in one pass. https://gist.github.com/DrewFitz/7254644

It moves through the array keeping a list of unresolved "left walls" and resolves the guaranteed water blocks when hitting a right wall. Each time it resolves, it only adds the new blocks gained by "raising" the puddle's water level.

DrewFitz commented Oct 31, 2013

Here's mine which solves it in one pass. https://gist.github.com/DrewFitz/7254644

It moves through the array keeping a list of unresolved "left walls" and resolves the guaranteed water blocks when hitting a right wall. Each time it resolves, it only adds the new blocks gained by "raising" the puddle's water level.

@Ruszrok

This comment has been minimized.

Show comment
Hide comment
@Ruszrok

Ruszrok Oct 31, 2013

I have solution - https://gist.github.com/Ruszrok/3adc23baa83b97de7145
It works in many cases. Can break it anyone?

Ruszrok commented Oct 31, 2013

I have solution - https://gist.github.com/Ruszrok/3adc23baa83b97de7145
It works in many cases. Can break it anyone?

@HollyGurza

This comment has been minimized.

Show comment
Hide comment
@HollyGurza

HollyGurza Nov 1, 2013

my Python solution - https://gist.github.com/HollyGurza/7261085 please test this

HollyGurza commented Nov 1, 2013

my Python solution - https://gist.github.com/HollyGurza/7261085 please test this

@benjaminliu

This comment has been minimized.

Show comment
Hide comment
@benjaminliu

benjaminliu Nov 1, 2013

Here is a test case, please try it
6, 1, 4, 6, 7, 5, 1, 6, 4

and here is my solution, double loop, much slower
https://gist.github.com/benjaminliu/7261468

benjaminliu commented Nov 1, 2013

Here is a test case, please try it
6, 1, 4, 6, 7, 5, 1, 6, 4

and here is my solution, double loop, much slower
https://gist.github.com/benjaminliu/7261468

@jianchenglee

This comment has been minimized.

Show comment
Hide comment
@bxt

This comment has been minimized.

Show comment
Hide comment
@bxt

bxt Nov 1, 2013

I have created a python solution that makes random landscapes like this one:

                           #                                                    
                          ###                                                   
               #~~~~~~~~######~~~~~~~#                                          
   #~~~~~~~~~~~###~~~~~~#######~~~~~##~#~~~~~~~##~~~~~~~~~~~~~~~~~~#            
   #~~~~~~~~~~####~~~~##########~~~~#####~~##~~##~~~~~~~~~~#~~~~~~##            
#~###~~~~~~~#######~~~##########~~~###############~~~~~~~~~#~~~~#####~#~##      
#~###~~~############~#############~###############~~~~~~~~####~~###########     
######~#############~##############################~#~#~~~#################     
######~#################################################~###################    
########################################################~###################~~##

bxt commented Nov 1, 2013

I have created a python solution that makes random landscapes like this one:

                           #                                                    
                          ###                                                   
               #~~~~~~~~######~~~~~~~#                                          
   #~~~~~~~~~~~###~~~~~~#######~~~~~##~#~~~~~~~##~~~~~~~~~~~~~~~~~~#            
   #~~~~~~~~~~####~~~~##########~~~~#####~~##~~##~~~~~~~~~~#~~~~~~##            
#~###~~~~~~~#######~~~##########~~~###############~~~~~~~~~#~~~~#####~#~##      
#~###~~~############~#############~###############~~~~~~~~####~~###########     
######~#############~##############################~#~#~~~#################     
######~#################################################~###################    
########################################################~###################~~##
@AndroidHumanoid

This comment has been minimized.

Show comment
Hide comment
@AndroidHumanoid

AndroidHumanoid Nov 1, 2013

Decker108 "I like your solution, but unfortunately it doesn't work for [2, 5, 1, 2, 3, 4, 7, 5, 6] which should give 11."

Yeees, what about that (it seems work, but how):

https://gist.github.com/AndroidHumanoid/7241202
http://it.laplit.com/index.php/ct-menu-item-8/128-article-7

public static int mycalculateVolume(int[] land) {
    int leftMax = 0;
    int rightMax = 0;
    int volumeLeft = 0;
    int volumeRight = 0;

    int volume = 0;

    for (int index = 0; index < land.length; index++) {
        if (land[index] >= leftMax){
            leftMax = land[index];  
            volume = volume + volumeLeft;
            volumeLeft = 0;
        } 
        else {
            volumeLeft = volumeLeft + leftMax - land[index];
        }
        if (land[land.length - 1 - index] >= rightMax){
            rightMax = land[land.length - 1 - index];  
            volume = volume + volumeRight;
            volumeRight = 0;
        }
        else {
            volumeRight = volumeRight + rightMax - land[land.length - 1 - index]; 
        }
    }
    return volume;
}

AndroidHumanoid commented Nov 1, 2013

Decker108 "I like your solution, but unfortunately it doesn't work for [2, 5, 1, 2, 3, 4, 7, 5, 6] which should give 11."

Yeees, what about that (it seems work, but how):

https://gist.github.com/AndroidHumanoid/7241202
http://it.laplit.com/index.php/ct-menu-item-8/128-article-7

public static int mycalculateVolume(int[] land) {
    int leftMax = 0;
    int rightMax = 0;
    int volumeLeft = 0;
    int volumeRight = 0;

    int volume = 0;

    for (int index = 0; index < land.length; index++) {
        if (land[index] >= leftMax){
            leftMax = land[index];  
            volume = volume + volumeLeft;
            volumeLeft = 0;
        } 
        else {
            volumeLeft = volumeLeft + leftMax - land[index];
        }
        if (land[land.length - 1 - index] >= rightMax){
            rightMax = land[land.length - 1 - index];  
            volume = volume + volumeRight;
            volumeRight = 0;
        }
        else {
            volumeRight = volumeRight + rightMax - land[land.length - 1 - index]; 
        }
    }
    return volume;
}
@BorzdeG

This comment has been minimized.

Show comment
Hide comment
@BorzdeG

BorzdeG Nov 2, 2013

my version of the solution with 22 test models: https://github.com/BorzdeG/info.alenkov.demo.puddle_rain

BorzdeG commented Nov 2, 2013

my version of the solution with 22 test models: https://github.com/BorzdeG/info.alenkov.demo.puddle_rain

@philipnilsson

This comment has been minimized.

Show comment
Hide comment
@philipnilsson

philipnilsson Nov 5, 2013

Probably the most elegant solution to this problem is using scanl/r and zipWith. Corresponds very closely to the mathematical breakdown of this problem. Here's a solution in Haskell.

water hs
  = sum $ zipWith (flip (-)) hs 
        $ zipWith min (scanl1 max hs) (scanr1 max hs)

philipnilsson commented Nov 5, 2013

Probably the most elegant solution to this problem is using scanl/r and zipWith. Corresponds very closely to the mathematical breakdown of this problem. Here's a solution in Haskell.

water hs
  = sum $ zipWith (flip (-)) hs 
        $ zipWith min (scanl1 max hs) (scanr1 max hs)
@skariel

This comment has been minimized.

Show comment
Hide comment
@skariel

skariel Nov 6, 2013

Mot solutions are actually wrong...

skariel commented Nov 6, 2013

Mot solutions are actually wrong...

@yannick1974

This comment has been minimized.

Show comment
Hide comment
@yannick1974

yannick1974 Nov 6, 2013

Hi all,

Another solution in Python using numpy (and matplotlib):

https://gist.github.com/yannick1974/7334581

Yannick

yannick1974 commented Nov 6, 2013

Hi all,

Another solution in Python using numpy (and matplotlib):

https://gist.github.com/yannick1974/7334581

Yannick

@celwell

This comment has been minimized.

Show comment
Hide comment
@celwell

celwell Nov 7, 2013

So does this work for:

4,0,0,4,0,4,0,0,4,2

?

celwell commented Nov 7, 2013

So does this work for:

4,0,0,4,0,4,0,0,4,2

?

@syfou

This comment has been minimized.

Show comment
Hide comment
@syfou

syfou Nov 8, 2013

Yet another solution: https://gist.github.com/syfou/7364514

It uses recursion: I tried to go for a readable and a painless, quickly implemented solution rather than something more clever.

syfou commented Nov 8, 2013

Yet another solution: https://gist.github.com/syfou/7364514

It uses recursion: I tried to go for a readable and a painless, quickly implemented solution rather than something more clever.

@est

This comment has been minimized.

Show comment
Hide comment
@est

est Nov 11, 2013

my dumb but working version

def get_volumn(seq):
    total = 0
    for level in xrange(max(seq)-1, 0, -1):
        row = [ 1 if row-level > 0 else 0 for row in seq]
        first = row.index(1)
        last = len(row) - row[::-1].index(1) - 1
        if last - first > 0:
            total += row[first:last].count(0)
    return total

if '__main__' == __name__:
    s1 =  [2,5,1,2,3,4,7,7,6]
    print get_volumn(s1)
    s2 = [ 2, 5, 1, 3, 1, 2, 1, 7, 7, 6]
    print get_volumn(s2)

est commented Nov 11, 2013

my dumb but working version

def get_volumn(seq):
    total = 0
    for level in xrange(max(seq)-1, 0, -1):
        row = [ 1 if row-level > 0 else 0 for row in seq]
        first = row.index(1)
        last = len(row) - row[::-1].index(1) - 1
        if last - first > 0:
            total += row[first:last].count(0)
    return total

if '__main__' == __name__:
    s1 =  [2,5,1,2,3,4,7,7,6]
    print get_volumn(s1)
    s2 = [ 2, 5, 1, 3, 1, 2, 1, 7, 7, 6]
    print get_volumn(s2)
@thulka

This comment has been minimized.

Show comment
Hide comment
@thulka

thulka Nov 12, 2013

mkozakov's solution is quite perfect, no allocations, no stack uage.

single pass, recursive in python: https://gist.github.com/thulka/7429806

btw, est, your solution wrong: [7,0,5,0,7,0] should be 16, yours returns 14. also you might have hidden loops in the list selectors, so not perfectly single pass. finally, it was about an elegant solution, not just a dumb working one. a simple working one, non single pass would be:

for each bin the water = min(leftmax, rightmax) - current height

thulka commented Nov 12, 2013

mkozakov's solution is quite perfect, no allocations, no stack uage.

single pass, recursive in python: https://gist.github.com/thulka/7429806

btw, est, your solution wrong: [7,0,5,0,7,0] should be 16, yours returns 14. also you might have hidden loops in the list selectors, so not perfectly single pass. finally, it was about an elegant solution, not just a dumb working one. a simple working one, non single pass would be:

for each bin the water = min(leftmax, rightmax) - current height

@chrisdone

This comment has been minimized.

Show comment
Hide comment
@chrisdone

chrisdone Nov 12, 2013

My first thought was to use a spreadsheet. Here's that in Haskell:

import Control.Lens
import qualified Data.Vector as V
import Data.Vector ((!),Vector)

-- | Calculate the water volume.
water :: Vector Int -> Int
water = V.sum . V.map (view _3) . loeb . V.imap cell where
  cell i x xs
    | i == 0               = edge _1
    | i == V.length xs - 1 = edge _2
    | otherwise            = col i x xs
    where edge ln = set l (view l (col i x xs)) (x,x,0)
            where l = cloneLens ln
  col i x xs = (l,r,min l r - x)
    where l = neighbor _1 (+)
          r = neighbor _2 (-)
          neighbor l o = max x (view l (xs ! (i `o` 1)))

It makes a vector where the value of each cell is calculated based on the two neighboring cells. Except edges, who only have one neighbor. It's a direct way of writing how I thought of the problem statement:

  • I'm a cell. My puddle's extent is determined by finding the largest cell to the left of me, and the largest to the right of me.
  • My potential volume is calculated by taking the minimum height of said two cells.
  • My actual volume is calculated by subtracting from that my height.
  • If I'm on the edge (either side), then my height on one side is restricted to me, and my volume is zero.

Done.

Oh, the loeb function is from here:

-- | Map over a structure, passing in itself.
loeb :: Functor f => f (f b -> b) -> f b
loeb x = fmap (\f -> f (loeb x)) x

chrisdone commented Nov 12, 2013

My first thought was to use a spreadsheet. Here's that in Haskell:

import Control.Lens
import qualified Data.Vector as V
import Data.Vector ((!),Vector)

-- | Calculate the water volume.
water :: Vector Int -> Int
water = V.sum . V.map (view _3) . loeb . V.imap cell where
  cell i x xs
    | i == 0               = edge _1
    | i == V.length xs - 1 = edge _2
    | otherwise            = col i x xs
    where edge ln = set l (view l (col i x xs)) (x,x,0)
            where l = cloneLens ln
  col i x xs = (l,r,min l r - x)
    where l = neighbor _1 (+)
          r = neighbor _2 (-)
          neighbor l o = max x (view l (xs ! (i `o` 1)))

It makes a vector where the value of each cell is calculated based on the two neighboring cells. Except edges, who only have one neighbor. It's a direct way of writing how I thought of the problem statement:

  • I'm a cell. My puddle's extent is determined by finding the largest cell to the left of me, and the largest to the right of me.
  • My potential volume is calculated by taking the minimum height of said two cells.
  • My actual volume is calculated by subtracting from that my height.
  • If I'm on the edge (either side), then my height on one side is restricted to me, and my volume is zero.

Done.

Oh, the loeb function is from here:

-- | Map over a structure, passing in itself.
loeb :: Functor f => f (f b -> b) -> f b
loeb x = fmap (\f -> f (loeb x)) x
@neuronsguy

This comment has been minimized.

Show comment
Hide comment
@neuronsguy

neuronsguy Nov 12, 2013

Short, single-pass python solution

q = [2,5,1,3,1,2,1,7,7,6]
def solve(heights):
    water = [0]*len(heights)
    total = 0
    runoff = 0
    for i,height in enumerate(heights):
        if i == 0:
            continue
        above = max(height, heights[i-1] + water[i-1]) - height 
        water[i] = above
        if water[i] == 0:
            runoff = 0
        else:
            runoff += water[i]
    return sum(water)-runoff
print q, solve(q)

neuronsguy commented Nov 12, 2013

Short, single-pass python solution

q = [2,5,1,3,1,2,1,7,7,6]
def solve(heights):
    water = [0]*len(heights)
    total = 0
    runoff = 0
    for i,height in enumerate(heights):
        if i == 0:
            continue
        above = max(height, heights[i-1] + water[i-1]) - height 
        water[i] = above
        if water[i] == 0:
            runoff = 0
        else:
            runoff += water[i]
    return sum(water)-runoff
print q, solve(q)
@chrisdone

This comment has been minimized.

Show comment
Hide comment
@chrisdone

chrisdone Nov 13, 2013

@neuronsguy That's an incomplete solution, it only works in one direction. E.g. solve([6,7,7,4,3,2,1,5,2])0

chrisdone commented Nov 13, 2013

@neuronsguy That's an incomplete solution, it only works in one direction. E.g. solve([6,7,7,4,3,2,1,5,2])0

@chrisdone

This comment has been minimized.

Show comment
Hide comment
@chrisdone

chrisdone Nov 13, 2013

@DrewFitz Only works properly in one direction.

print puddle([2,5,1,2,3,4,7,7,6]) → 10
print puddle([6,7,7,4,3,2,1,5,2]) → 11

chrisdone commented Nov 13, 2013

@DrewFitz Only works properly in one direction.

print puddle([2,5,1,2,3,4,7,7,6]) → 10
print puddle([6,7,7,4,3,2,1,5,2]) → 11
@chrisdone

This comment has been minimized.

Show comment
Hide comment
@chrisdone

chrisdone Nov 13, 2013

@HollyGurza Only works properly in one direction.

You guys really need to think about the problem in both directions.

chrisdone commented Nov 13, 2013

@HollyGurza Only works properly in one direction.

You guys really need to think about the problem in both directions.

@chrisdone

This comment has been minimized.

Show comment
Hide comment
@chrisdone

chrisdone Nov 13, 2013

@igor47 Only works in one direction.

chrisdone commented Nov 13, 2013

@igor47 Only works in one direction.

@tmoertel

This comment has been minimized.

Show comment
Hide comment
@tmoertel

tmoertel Nov 14, 2013

Thanks for the fun problem :-)

I ended up solving it recursively, working from the base cases up to a general solution, and then I converted the recursive algorithm into the following Python function taking a height array A. For a problem of size len(A) = N, the function requires O(N) time and O(1) space. For a full derivation of the algorithm, starting from first principles, see the (extensive) discussion in the source code:

https://github.com/tmoertel/practice/blob/master/water-holding-capacity/water_holding_capacity.py

def water_holding_capacity_iterative(A):
    (i, j) = (0, len(A) - 1)
    lm = rm = vol = 0
    # while segments remain, consume left- or right-end segment
    while i <= j:
        if lm < rm:
            vol += max(0, lm - A[i])
            lm = max(lm, A[i])
            i += 1
        else:
            vol += max(0, rm - A[j])
            rm = max(rm, A[j])
            j -= 1
    return vol

tmoertel commented Nov 14, 2013

Thanks for the fun problem :-)

I ended up solving it recursively, working from the base cases up to a general solution, and then I converted the recursive algorithm into the following Python function taking a height array A. For a problem of size len(A) = N, the function requires O(N) time and O(1) space. For a full derivation of the algorithm, starting from first principles, see the (extensive) discussion in the source code:

https://github.com/tmoertel/practice/blob/master/water-holding-capacity/water_holding_capacity.py

def water_holding_capacity_iterative(A):
    (i, j) = (0, len(A) - 1)
    lm = rm = vol = 0
    # while segments remain, consume left- or right-end segment
    while i <= j:
        if lm < rm:
            vol += max(0, lm - A[i])
            lm = max(lm, A[i])
            i += 1
        else:
            vol += max(0, rm - A[j])
            rm = max(rm, A[j])
            j -= 1
    return vol
@emakarov

This comment has been minimized.

Show comment
Hide comment
@emakarov

emakarov Nov 16, 2013

python:

numbers = [6,7,7,4,3,2,1,5,2]
def vol(numbers):
  prev_max = 0
  total = 0
  for n in numbers[0:-1]:
    if n > prev_max:
      prev_max = n
    else:
      total = total + (prev_max-n)
  total_1 = total
  total = 0
  numbers = numbers[::-1]
  prev_max = 0
  for n in numbers[0:-1]:
    if n > prev_max:
      prev_max = n
    else:
      total = total + (prev_max-n)
  total = min(total_1,total)
  return total

emakarov commented Nov 16, 2013

python:

numbers = [6,7,7,4,3,2,1,5,2]
def vol(numbers):
  prev_max = 0
  total = 0
  for n in numbers[0:-1]:
    if n > prev_max:
      prev_max = n
    else:
      total = total + (prev_max-n)
  total_1 = total
  total = 0
  numbers = numbers[::-1]
  prev_max = 0
  for n in numbers[0:-1]:
    if n > prev_max:
      prev_max = n
    else:
      total = total + (prev_max-n)
  total = min(total_1,total)
  return total

@emakarov

This comment has been minimized.

Show comment
Hide comment
@emakarov

emakarov Nov 16, 2013

or one-way loop in python

def vol2(numbers):
  prev_max_left = 0
  prev_max_right = 0
  total_left = 0
  total_right = 0
  for n in xrange(0,len(numbers)-1):
    if numbers[n] > prev_max_left:
      prev_max_left = numbers[n]
    elif numbers[n] < prev_max_left:
      total_left = total_left + (prev_max_left - numbers[n])
    if numbers[-1-n] > prev_max_right:
      prev_max_right = numbers[-1-n]
    elif numbers[-1-n] < prev_max_right:
      total_right = total_right + (prev_max_right - numbers[-1-n])
  return min(total_left,total_right)

emakarov commented Nov 16, 2013

or one-way loop in python

def vol2(numbers):
  prev_max_left = 0
  prev_max_right = 0
  total_left = 0
  total_right = 0
  for n in xrange(0,len(numbers)-1):
    if numbers[n] > prev_max_left:
      prev_max_left = numbers[n]
    elif numbers[n] < prev_max_left:
      total_left = total_left + (prev_max_left - numbers[n])
    if numbers[-1-n] > prev_max_right:
      prev_max_right = numbers[-1-n]
    elif numbers[-1-n] < prev_max_right:
      total_right = total_right + (prev_max_right - numbers[-1-n])
  return min(total_left,total_right)
@divipp

This comment has been minimized.

Show comment
Hide comment
@divipp

divipp Nov 20, 2013

Another Haskell solution, O(1) space when switched to foldl' and strict tuples:

water is = w1 + w2 + t1 - length is * m1 where
   (t1,m1,w1) = foldl f (0,0,0) is
   (t2,m2,w2) = foldl f (0,0,0) $ reverse is
   f (t,m,w) i = (t+i, max m i, w + max 0 (m-i))

divipp commented Nov 20, 2013

Another Haskell solution, O(1) space when switched to foldl' and strict tuples:

water is = w1 + w2 + t1 - length is * m1 where
   (t1,m1,w1) = foldl f (0,0,0) is
   (t2,m2,w2) = foldl f (0,0,0) $ reverse is
   f (t,m,w) i = (t+i, max m i, w + max 0 (m-i))
@andrewnguyen42

This comment has been minimized.

Show comment
Hide comment
@andrewnguyen42

andrewnguyen42 Dec 2, 2013

Elegant one liners are cool! Sadly mine is not one of those.

I start by calculating what the maximum amount of water that could be held is. Then, I go level by level and remove blocks that would have fallen off. Think of it as if you dipped a lego structure into a bathtub and pulled it out: every hole is filled at first, but as you pull it out of the water, each level loses some water.

https://gist.github.com/andrewnguyen42/7745194

andrewnguyen42 commented Dec 2, 2013

Elegant one liners are cool! Sadly mine is not one of those.

I start by calculating what the maximum amount of water that could be held is. Then, I go level by level and remove blocks that would have fallen off. Think of it as if you dipped a lego structure into a bathtub and pulled it out: every hole is filled at first, but as you pull it out of the water, each level loses some water.

https://gist.github.com/andrewnguyen42/7745194

@vvsh

This comment has been minimized.

Show comment
Hide comment
@vvsh

vvsh Dec 5, 2013

rightMax should be equals land.length - 1

vvsh commented Dec 5, 2013

rightMax should be equals land.length - 1

@allumbra

This comment has been minimized.

Show comment
Hide comment
@allumbra

allumbra Dec 19, 2013

Short JS solution:
https://gist.github.com/allumbra/8035125
1 pass. Keeps track of last time wall height was seen.

allumbra commented Dec 19, 2013

Short JS solution:
https://gist.github.com/allumbra/8035125
1 pass. Keeps track of last time wall height was seen.

@joneschris

This comment has been minimized.

Show comment
Hide comment

joneschris commented Dec 20, 2013

Another Python solution - https://gist.github.com/joneschris/8049901

@markcrandall

This comment has been minimized.

Show comment
Hide comment
@markcrandall

markcrandall Dec 20, 2013

Here is a solution using C# and one lambda

using System;
using System.Linq;

namespace TwitterInterviewAnswer
{
    class Program
    {
        static void Main(string[] args)
        {
            //the data
            int[] wallHeights = {2, 5, 1, 2, 3, 4, 7, 7, 6};

            //the lambda expression
            Func<int[], int> volume = walls => walls.Skip(1).Take(walls.Count() - 2)
                .Select((s, i) => new {s, i})
                .Select(v => new[] 
                 {
                     walls.Take(v.i + 1)
                        .Max(), 
                     walls
                        .Skip(v.i + 2)
                        .Max()
                  }
                 .Min() - v.s)
                 .Where(w => w > 0)
                 .Sum();

            //the output
            Console.WriteLine("The volume is: {0}", volume.Invoke(wallHeights));
            Console.ReadKey();
        }
    }
}

markcrandall commented Dec 20, 2013

Here is a solution using C# and one lambda

using System;
using System.Linq;

namespace TwitterInterviewAnswer
{
    class Program
    {
        static void Main(string[] args)
        {
            //the data
            int[] wallHeights = {2, 5, 1, 2, 3, 4, 7, 7, 6};

            //the lambda expression
            Func<int[], int> volume = walls => walls.Skip(1).Take(walls.Count() - 2)
                .Select((s, i) => new {s, i})
                .Select(v => new[] 
                 {
                     walls.Take(v.i + 1)
                        .Max(), 
                     walls
                        .Skip(v.i + 2)
                        .Max()
                  }
                 .Min() - v.s)
                 .Where(w => w > 0)
                 .Sum();

            //the output
            Console.WriteLine("The volume is: {0}", volume.Invoke(wallHeights));
            Console.ReadKey();
        }
    }
}
@mkozakov

This comment has been minimized.

Show comment
Hide comment
@mkozakov

mkozakov Jan 3, 2014

@jbojcic your code won't work for something like [7,3,2,4].
You will fill in water that should spill out

Owner

mkozakov commented Jan 3, 2014

@jbojcic your code won't work for something like [7,3,2,4].
You will fill in water that should spill out

@jbojcic

This comment has been minimized.

Show comment
Hide comment
@jbojcic

jbojcic Jan 19, 2014

@mkozakov it won't fill up water that should spill out but it will spill out everything, which is also wrong

jbojcic commented Jan 19, 2014

@mkozakov it won't fill up water that should spill out but it will spill out everything, which is also wrong

@sumerc

This comment has been minimized.

Show comment
Hide comment
@sumerc

sumerc Feb 18, 2014

# Actually the original implementation is as following which is done in n-pass:

def water_vol_orig(a):    
    lv = rv = -1
    result = lmax = rmax = l = 0
    r = len(a)-1 # no pass on array    
    while (l < r):
        lv = a[l]
        if lv > lmax:
            lmax = lv

        rv = a[r]
        if rv > rmax:
            rmax = rv

        if lmax >= rmax:
            result += rmax - rv
            r -= 1
        else:
            result += lmax - lv
            l += 1
    return result

# This implementation avoids the lookup for the max item in the array to finish in n-pass. 
# However, it is doing 3 comparisons inside the inner loop and in dynamic languages like Python/Java 
# indexed access to an array is expensive, using enumerators is far more effective. 

# So more efficient way of doing this in Python may be:
#1) find the max item
#2) approach to max item from left and right.

def water_vol_fast(a):

    def _imax(x): # find max in single pass, faster than max(..,itemgetter(..))
        max_idx = max_val = 0
        for i, v in enumerate(a):
            if v > max_val:
                max_val = v
                max_idx = i
        return max_idx

    def _volp(x): 
        max = result = 0        
        for e in x:
            if e > max:
                max = e
            else:
                result += max - e
        return result

    imax = _imax(a) # n-pass
    return _volp(a[:imax]) + _volp(reversed(a[imax:])) # n pass

# This version will have 2N comparisons(1N for finding max and 1N for calculating the volume) and no index 
# based access to any array.

# If these are profiled, one can see the difference:

# water_vol_orig takes 0.405603 CPU Secs, and water_vol will take 0.265202 which is nearly %80 faster.

# You can test above by:

# for test:
import random 
a = [int(1000*random.random()) for i in range(10000)]
assert water_vol_orig(a) == water_vol_fast(a)

sumerc commented Feb 18, 2014

# Actually the original implementation is as following which is done in n-pass:

def water_vol_orig(a):    
    lv = rv = -1
    result = lmax = rmax = l = 0
    r = len(a)-1 # no pass on array    
    while (l < r):
        lv = a[l]
        if lv > lmax:
            lmax = lv

        rv = a[r]
        if rv > rmax:
            rmax = rv

        if lmax >= rmax:
            result += rmax - rv
            r -= 1
        else:
            result += lmax - lv
            l += 1
    return result

# This implementation avoids the lookup for the max item in the array to finish in n-pass. 
# However, it is doing 3 comparisons inside the inner loop and in dynamic languages like Python/Java 
# indexed access to an array is expensive, using enumerators is far more effective. 

# So more efficient way of doing this in Python may be:
#1) find the max item
#2) approach to max item from left and right.

def water_vol_fast(a):

    def _imax(x): # find max in single pass, faster than max(..,itemgetter(..))
        max_idx = max_val = 0
        for i, v in enumerate(a):
            if v > max_val:
                max_val = v
                max_idx = i
        return max_idx

    def _volp(x): 
        max = result = 0        
        for e in x:
            if e > max:
                max = e
            else:
                result += max - e
        return result

    imax = _imax(a) # n-pass
    return _volp(a[:imax]) + _volp(reversed(a[imax:])) # n pass

# This version will have 2N comparisons(1N for finding max and 1N for calculating the volume) and no index 
# based access to any array.

# If these are profiled, one can see the difference:

# water_vol_orig takes 0.405603 CPU Secs, and water_vol will take 0.265202 which is nearly %80 faster.

# You can test above by:

# for test:
import random 
a = [int(1000*random.random()) for i in range(10000)]
assert water_vol_orig(a) == water_vol_fast(a)
@Mak-Sym

This comment has been minimized.

Show comment
Hide comment
@Mak-Sym

Mak-Sym Feb 23, 2014

Hm... tried to run original solution against the data with 3 maximums and it didn't work...

public class TestTest {
    public static void main (String[] args) throws java.lang.Exception
    {
        int[] testData1 = {1, 2, 1, 3, 2, 1, 0, 2, 4, 3, 1, 5, 3, 1, 4, 1, 2, 1, 0};
        int expectedResult1 = 17;
        int[] testData2 = {4, 1, 2, 1, 3, 2, 1, 0, 2, 4, 3, 1, 5, 3, 1, 4, 1, 2, 1, 0};
        int expectedResult2 = 40;
        int[] testData3 = {1, 3, 4, 1, 2, 1, 3, 2, 1, 0, 2, 4, 3, 1, 5, 3, 1, 4, 1, 2, 1, 0};
        int expectedResult3 = 40;
        int[] testData4 = {2, 1, 3, 4, 1, 2, 1, 3, 2, 1, 0, 2, 4, 3, 1, 5, 3, 1, 4, 1, 2, 1, 0};
        int expectedResult4 = 41;
        int[] testData5 = {2, 1, 3, 4, 1, 2, 1, 3, 2, 1, 0, 2, 4, 3, 1, 5, 3, 1, 4, 1, 2, 1, 0, 5, 2, 1, 3};
        int expectedResult5 = 61;

        test(expectedResult1, testData1);
        test(expectedResult2, testData2);
        test(expectedResult3, testData3);
        test(expectedResult4, testData4);
        test(expectedResult5, testData5);   //[ERROR] Test failure! Expected: 61 but was: 62

    }

    public static void test(int expected, int[] array){
        int result = calculateVolume(array);
        if(result != expected) {
            System.out.println("[ERROR] Test failure! Expected: " + expected + " but was: " + result);
        } else {
            System.out.println("[INFO] Test successful!");
        }
    }

    public static int calculateVolume(int[] land) {

        int leftMax = 0;
        int rightMax = 0;
        int left = 0;
        int right = land.length - 1;
        int volume = 0;

        while(left < right) {
            if(land[left] > leftMax) {
                leftMax = land[left];
            }
            if(land[right] > rightMax) {
                rightMax = land[right];
            }
            if(leftMax >= rightMax) {
                volume += rightMax - land[right];
                right--;
            } else {
                volume += leftMax - land[left];
                left++;
            }
        }
        return volume;
    }
}

Mak-Sym commented Feb 23, 2014

Hm... tried to run original solution against the data with 3 maximums and it didn't work...

public class TestTest {
    public static void main (String[] args) throws java.lang.Exception
    {
        int[] testData1 = {1, 2, 1, 3, 2, 1, 0, 2, 4, 3, 1, 5, 3, 1, 4, 1, 2, 1, 0};
        int expectedResult1 = 17;
        int[] testData2 = {4, 1, 2, 1, 3, 2, 1, 0, 2, 4, 3, 1, 5, 3, 1, 4, 1, 2, 1, 0};
        int expectedResult2 = 40;
        int[] testData3 = {1, 3, 4, 1, 2, 1, 3, 2, 1, 0, 2, 4, 3, 1, 5, 3, 1, 4, 1, 2, 1, 0};
        int expectedResult3 = 40;
        int[] testData4 = {2, 1, 3, 4, 1, 2, 1, 3, 2, 1, 0, 2, 4, 3, 1, 5, 3, 1, 4, 1, 2, 1, 0};
        int expectedResult4 = 41;
        int[] testData5 = {2, 1, 3, 4, 1, 2, 1, 3, 2, 1, 0, 2, 4, 3, 1, 5, 3, 1, 4, 1, 2, 1, 0, 5, 2, 1, 3};
        int expectedResult5 = 61;

        test(expectedResult1, testData1);
        test(expectedResult2, testData2);
        test(expectedResult3, testData3);
        test(expectedResult4, testData4);
        test(expectedResult5, testData5);   //[ERROR] Test failure! Expected: 61 but was: 62

    }

    public static void test(int expected, int[] array){
        int result = calculateVolume(array);
        if(result != expected) {
            System.out.println("[ERROR] Test failure! Expected: " + expected + " but was: " + result);
        } else {
            System.out.println("[INFO] Test successful!");
        }
    }

    public static int calculateVolume(int[] land) {

        int leftMax = 0;
        int rightMax = 0;
        int left = 0;
        int right = land.length - 1;
        int volume = 0;

        while(left < right) {
            if(land[left] > leftMax) {
                leftMax = land[left];
            }
            if(land[right] > rightMax) {
                rightMax = land[right];
            }
            if(leftMax >= rightMax) {
                volume += rightMax - land[right];
                right--;
            } else {
                volume += leftMax - land[left];
                left++;
            }
        }
        return volume;
    }
}

@sumerc

This comment has been minimized.

Show comment
Hide comment
@sumerc

sumerc Feb 24, 2014

@Mak-Sym Original implementation returns 51 and your expectation should not be 61. 51 is the correct volume for input set: {2, 1, 3, 4, 1, 2, 1, 3, 2, 1, 0, 2, 4, 3, 1, 5, 3, 1, 4, 1, 2, 1, 0, 5, 2, 1, 3}.

Please do not forget the fact that water will spill from left/right if there is no surrounding block.

sumerc commented Feb 24, 2014

@Mak-Sym Original implementation returns 51 and your expectation should not be 61. 51 is the correct volume for input set: {2, 1, 3, 4, 1, 2, 1, 3, 2, 1, 0, 2, 4, 3, 1, 5, 3, 1, 4, 1, 2, 1, 0, 5, 2, 1, 3}.

Please do not forget the fact that water will spill from left/right if there is no surrounding block.

@Mak-Sym

This comment has been minimized.

Show comment
Hide comment
@Mak-Sym

Mak-Sym Feb 25, 2014

Thanks!

There is typo in my post - sorry about that
I meant this one:

int[] testData5 = {2, 1, 3, 5, 1, 2, 1, 3, 2, 1, 0, 2, 4, 3, 1, 5, 3, 1, 4, 1, 2, 1, 0, 5, 2, 1, 3};  //should be 61, but was 62

Mak-Sym commented Feb 25, 2014

Thanks!

There is typo in my post - sorry about that
I meant this one:

int[] testData5 = {2, 1, 3, 5, 1, 2, 1, 3, 2, 1, 0, 2, 4, 3, 1, 5, 3, 1, 4, 1, 2, 1, 0, 5, 2, 1, 3};  //should be 61, but was 62
@Mak-Sym

This comment has been minimized.

Show comment
Hide comment
@Mak-Sym

Mak-Sym Feb 25, 2014

Whoops - found bug in my calculations - it should be 62 (not sure how I missed this during numerous manual verifications and my v1 impl :) )

Mak-Sym commented Feb 25, 2014

Whoops - found bug in my calculations - it should be 62 (not sure how I missed this during numerous manual verifications and my v1 impl :) )

@Pranz

This comment has been minimized.

Show comment
Hide comment
@Pranz

Pranz May 8, 2014

unspoiled solution; I think mine works the same way as yours.
https://gist.github.com/Pranz/45eff77d201ef1e2dc61

Pranz commented May 8, 2014

unspoiled solution; I think mine works the same way as yours.
https://gist.github.com/Pranz/45eff77d201ef1e2dc61

@bourneagain

This comment has been minimized.

Show comment
Hide comment
@isaiah-perumalla

This comment has been minimized.

Show comment
Hide comment
@isaiah-perumalla

isaiah-perumalla commented Aug 13, 2015

here is an alternate but simple nlog(n) solution
https://gist.github.com/isaiah-perumalla/105b72e6b99f69b599ec

@harrytallbelt

This comment has been minimized.

Show comment
Hide comment
@harrytallbelt

harrytallbelt May 18, 2016

just an F# solution for aestetic pleasure

let oneWayCapacity a =
    let mutable max = 0
    a |> List.map (fun e -> if e > max then max <- e; 0 else max - e)

let totalCapacity a =
    let aL = a |> oneWayCapacity
    let aR = a |> List.rev |> oneWayCapacity |> List.rev
    List.map2 min aL aR |> List.sum


let test a =
    a |> totalCapacity |>
    printfn "totalCapacity %A = %i" a

let () = 
    [1; 2; 1; 3; 5; 3; 1; 2; 4; 1] |> test
    [2; 5; 10; 7; 3; 8; 5; 2] |> test
    [2; 5; 1; 2; 3; 4; 7; 7; 6] |> test

https://gist.github.com/harry-tallbelt/cc236e710c9edf858853c118bc38c9ad

harrytallbelt commented May 18, 2016

just an F# solution for aestetic pleasure

let oneWayCapacity a =
    let mutable max = 0
    a |> List.map (fun e -> if e > max then max <- e; 0 else max - e)

let totalCapacity a =
    let aL = a |> oneWayCapacity
    let aR = a |> List.rev |> oneWayCapacity |> List.rev
    List.map2 min aL aR |> List.sum


let test a =
    a |> totalCapacity |>
    printfn "totalCapacity %A = %i" a

let () = 
    [1; 2; 1; 3; 5; 3; 1; 2; 4; 1] |> test
    [2; 5; 10; 7; 3; 8; 5; 2] |> test
    [2; 5; 1; 2; 3; 4; 7; 7; 6] |> test

https://gist.github.com/harry-tallbelt/cc236e710c9edf858853c118bc38c9ad

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment