Directi Interview Question
Developer Program EngineersCountry: India
Interview Type: Phone Interview
That logic is wrong.
You would fail on an input of say: 131529491.
Instead use a stack and scan through from left to right, with conditions to push or pop buildings onto or from the stack, you'll achieve it in time O(n) then too.
Find the index of the tallest building, and then go from both ends of the array until it hits the maximum's index.
public static int volumeCollected(int[] array) {
if (array == null || array.length <= 2) {
return 0;
}
int maxIndex = findMaxIndex(array);
int length = array.length;
int volume = 0;
int collector = array[0];
for (int i = 1; i < maxIndex; i++) {
if (array[i] > collector) {
collector = array[i];
} else {
volume += collector - array[i];
}
}
collector = array[length-1];
for (int i = length - 2; i > maxIndex; i--) {
if (array[i] > collector) {
collector = array[i];
} else {
volume += collector - array[i];
}
}
return volume;
}
private static int findMaxIndex(int[] array) {
int max = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] > max) {
max = i;
}
}
return max;
}
for ( int i =1 ; i < n ;++)
{
int priviousmax =a[0];
int currentmax =a [0];
int volume = 0;
if (a[i] > currentmax )
{
currentmax = a[i];
volume + = (i* (currentmax -privousmax )
priviousmax = currentmax;
}
else
volume + = currentmax - a[i] ;
}
Solution is o(n) time complexity, and two varibale for space complexity (o(2))
Suppose you are on index i
- Sourabh Jain November 27, 2014--- First find max height between 0 to i-1 , let assume it A
--- Now find max height between i+1 to n, let assume it B
let C = min(A,B)
if(C < height of building i)
than water storage on building i is 0
else
water got stored is (C-A)
do it for all i , 0 to n
you can do it in O(n) time complexity , O(2*n) space complexity using pre-computation.