## Directi Interview Question

Developer Program Engineers**Country:**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.