Why my O(n^2) method used less time than my O(n) method


  • 0
    Z

    o(n^2) method:
    I select the first large number, and the second large number, calculate the area between them, and calculate the area outside this two numbers by using the recursion.
    it should cost O(n^2) in the worst case, as the Array is sorted in descending However it beat 66%:
    public int trap(int[] height) {
    if(height == null || height.length < 3) return 0;
    return helper(height, 0, height.length - 1);
    }

    public int helper(int[] height, int start, int last){
        if(last - start < 2) return 0;
        int left = start; 
        int right = last;
        int index_left = start;
        int index_right = -1;
        int max_left = height[start];
        int max_right = -1;
        int rst = 0;
        for(int i = start; i <= last; i++){
            if(height[i] >= max_left){
                max_left = height[i];
                index_left = i;
            }
        }
        for(int i = start; i <= last; i++){
            if(height[i] >= max_right && i != index_left){
                max_right = height[i];
                index_right = i;
            }
        }
        
        
        
        int top = Math.min(max_left, max_right);
        if(index_left > index_right){
            int temp = index_right;
            index_right = index_left;
            index_left = temp;
        }
        for(int i = index_left; i <= index_right; i++){
            rst += (height[i] < top) ? top - height[i] : 0;
        }
        rst += helper(height, start, index_left);
        rst += helper(height, index_right, last);
        return rst;  
    }
    

    the O(n) method is like every others did, using two pointers: it only beats 15%:

    public int trap(int[] height) {
        if(height == null || height.length < 3) return 0;
        int left = 0, right = height.length - 1;
        int left_max = height[left], right_max = height[right];
        int rst = 0;
        while(left < right){
            if(height[left] < height[right]){
                left++;
                if(height[left] < left_max) rst += left_max - height[left];
                else left_max = height[left];
            }
            else{
                right--;
                if(height[right] < right_max) rst += right_max - height[right];
                else right_max = height[right];
            }
        }
        return rst;
    }

Log in to reply
 

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