Instantly share code, notes, and snippets.

# mkozakov/gist:59af0fd5bddbed1a0399 Secret

Created October 29, 2013 06:48
Star You must be signed in to star a gist
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 /* 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; } }

### chrisdone commented Nov 13, 2013

@igor47 Only works in one direction.

### 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 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)

``````

### 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 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 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

### uladzimir-shelhunou commented Dec 5, 2013

rightMax should be equals land.length - 1

### 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 commented Dec 20, 2013

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

### markcrandall commented Dec 20, 2013

Here is a solution using C# and one lambda

```using System;
using System.Linq;

{
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));
}
}
}```

### 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 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 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

# 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 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 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 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 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 commented May 8, 2014

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

### isaiah-perumalla commented Aug 13, 2015

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

### harrytallbelt commented May 18, 2016 • edited

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```