Why do I get TLE with O(n) solution?


  • 1
    G

    I found two solutions in the discuss. Both of them are O(n) time complexity. The first one got TLE but the second one got AC. Can anyone explain on why the second solution is faster than the first one?

    First Solution:

    public int trap(int[] height) {
            if(height == null || height.length<3){  return 0;}
            int low= 0, high= height.length-1;
            int maxLeft= 0, maxRight=0;
            int res= 0;
            while(low <= high){
                maxLeft= Math.max(maxLeft, height[low]);
                maxRight= Math.max(maxRight, height[high]);
                if(maxLeft < maxRight){
                    res+= (maxLeft - height[low]);
                    low++;
                }else{  //maxLeft > maxRight
                    res+= (maxRight - height[high]);
                    high--;
                }
                
            }
            return res;
        }
    

    Second Solution (dp):

    public int trap(int[] height) {
            int len = height.length;
            if(len == 0)    return 0;
            int[] maxleft = new int[len];
            int[] maxright = new int[len];
            int max = Integer.MIN_VALUE;
            for(int i=0;i<len;i++){
                if(height[i] > max){
                    max = height[i];
                }
                maxleft[i] = max;
            }
            max = Integer.MIN_VALUE;
            for(int i=len-1;i>=0;i--){
                if(height[i] > max){
                    max = height[i];
                }
                maxright[i] = max;
            }
            int ret = 0;
            for(int i=0;i<len;i++){
                int diff = Math.min(maxleft[i],maxright[i]) - height[i];
                if(diff > 0)    ret += diff;
            }
            return ret;
        }

  • 0

    No idea what you're talking about, the first solution doesn't get TLE, it takes 2ms and easily gets accepted.


Log in to reply
 

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