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


  • 0
    M
    /*
     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;
        	}
        
        }

Log in to reply
 

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