-
-
Save mkozakov/59af0fd5bddbed1a0399 to your computer and use it in GitHub Desktop.
/* 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; | |
} | |
} |
@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.
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
Whoops - found bug in my calculations - it should be 62 (not sure how I missed this during numerous manual verifications and my v1 impl :) )
unspoiled solution; I think mine works the same way as yours.
https://gist.github.com/Pranz/45eff77d201ef1e2dc61
This seems to work ...
https://gist.github.com/bourneagain/0cb90851106756746933
here is an alternate but simple nlog(n) solution
https://gist.github.com/isaiah-perumalla/105b72e6b99f69b599ec
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
Hm... tried to run original solution against the data with 3 maximums and it didn't work...