What is the time complexity of my code?


  • 0
    S

    What is the amortized time complexity of my code?

    • Obviously, it is greater than O(n) because it takes some time to calculate the left and right borders. The result of dynamic programming sometimes cannot directly give out what we want. So sometimes it takes more than O(1) time to fill a cell in the DP table (lborder and rborder).
    • It also looks like less than O(n^2), because (1)the runtime beats 85.60% of java submissions (2)I can't find any concrete example in which the algorithm runs in O(n^2) time.
    • I cannot find any clue suggesting this is a O(nlogn) algorithm.

    Can anyone help to analysis its time complexity? Thank you!

    /**
     *Idea:
     * Dynamic programming. For a bar with height h, calculate and record its farthest expansion (i.e. edges of rect) to left and right.
     * While calculating, make use of already calculated expansions.
     *Result:
     * 94 / 94 test cases passed.
     * Status: Accepted
     * Runtime: 6 ms
     * Your runtime beats 85.60% of javasubmissions.
     *Date:
     * 8/26/2016
     */
    
    import java.util.Arrays;
    
    public class Solution {
        private int[] lborder;    //lborder[i] is the index of the left border of the maximum rectangle whose height is heights[i], and bar i is in the rectangle.
        private int[] rborder;
        private int[] heights;
        public int largestRectangleArea(int[] heights) {
            if(heights==null || heights.length==0)
                return 0;
            this.heights = heights;
            lborder = new int[heights.length];
            rborder = new int[heights.length];
            Arrays.fill(lborder, -1);
            Arrays.fill(rborder, -1);
            lborder[0] = 0;
            rborder[heights.length-1]=heights.length-1;
            for(int i=0;i<heights.length;i++){
            	getLBorder(i);
            }
            int max = 0;
            for(int i=heights.length-1;i>=0;i--){
            	getRBorder(i);
            	int area = (rborder[i]-lborder[i]+1)*heights[i]; 
            	max = area>max?area:max;
            }
            return max;
        }
        int getLBorder(int index){
        	int border = index;
        	while(border>0 && heights[border-1]>=heights[index])
        		border = lborder[border-1];
        	lborder[index] = border;
        	return border;
        }
        int getRBorder(int index){
        	int border = index;
        	while(border<heights.length-1 && heights[border+1]>=heights[index])
        		border = rborder[border+1];
        	rborder[index] = border;
        	return border;
        }
    }
    111

Log in to reply
 

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