My Time Limit Exceeded solution


  • 0
    B

    I know it will be slow but like to share my thought. What I am trying to do is to scan every 'level' and find any pair of closing block, calculate the gap between each pair, and then subtract each element by 1, after that going through N, move to next level, and then until reach the 'maxheight'. Maxheight may not need to be pre-calculated but in the end of stopping case is every element is < 0, and that means you still need to scan entire array once.

    Apparently this is very time consuming approach, because your algorithm is basically N * maxheight, and the large maxheight can just slow you down...

        public int trap(int[] A) {
        
        if( A.length <= 2 ) return 0;
    
        int total = 0;
        
        int leftidx  = -1;
        int rightidx = -1;
        
        int maxheight = 0;
        for( int i = 0; i < A.length; i++ ) {
            if( A[i] > maxheight ) maxheight = A[i];
        }
        System.out.println("maxheight " + maxheight );
        
        while( maxheight > 0 ) {
        	
            for( int i = 0; i < A.length; i++ ) {
                
                if( leftidx == -1 && A[i] > 0 ) {
                	System.out.println( "set leftidx = " + i );
                    leftidx = i;
                    
                } else if( leftidx > 0 && rightidx == -1 && A[i] > 0 && (i - leftidx) == 1 ) {
                	System.out.println( "set leftidx = " + i );
                	leftidx = i;
                }
                else if( leftidx > 0 && rightidx == -1 && A[i] > 0 && (i - leftidx) > 1 ) {
                	System.out.println( "set rightidx = " + i );
                    rightidx = i;
                    // calculate capacity                    
                    total += (rightidx - leftidx - 1);
                    System.out.println("Total now " + total );
                    
                    System.out.println( "set leftidx = " + i );
                    leftidx = rightidx;
                    rightidx = -1;                                        
                }
                
                // lower one level                
                A[i]--;
            }
            
            maxheight--;
            System.out.println( "move to next level " + maxheight );
            leftidx = -1;
            rightidx = -1;
            for( int i = 0; i < A.length; i++ ) {
            	System.out.println( A[i] ); 
            }
        }
        
        return total;
    }

Log in to reply
 

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