# Why is this O(n^2) not getting timed out?

• ``````/*
For every histogram starting at position i, calculate the amount of water that can be stored
up to histogram j.
*/

public class Solution {
public int trap(int[] arr) {
int i = 0;
int water = 0;
int next_index = -1;

while( i<arr.length)
{
int water_so_far = 0;
next_index = -1;

for(int j = i+1; j<arr.length; j++)
{
if(isValid(i,j,arr) && arr[i]>0)
{
water_so_far = getWaterAmt(min(i,j,arr),arr, i, j);
next_index = j;

}
}

if(next_index==-1)
i++;
else
i=next_index;

water += water_so_far;
}

return water;

}

public int min(int i, int j, int[] arr)
{
return arr[i]<=arr[j]?arr[i]:arr[j];
}

/*
This method returns true, if the range start and end contains all
histograms smaller than min(start, end)

*/
public boolean isValid(int s, int e, int[] arr)
{
//int high = arr[s]>arr[e]?arr[s]:arr[e];

if(s+1==e)
return false;

int low = arr[s]<=arr[e]?arr[s]:arr[e];

for(int i=s+1;i<e;i++)
{
if(arr[i] > low)
return false;
}

return true;
}

/*
If the range is valid, compute water for that range.

*/

public int getWaterAmt(int low, int[] arr, int s, int e)
{
int i = s+1;
int water = 0;

while(i < e)
{
int level =  low - arr[i] >= 0?low - arr[i]:0;
water = water + level;
i++;
}

return water;
}

}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.