O(n) java solution beat 92.65%.


  • 2
    M

    Here is the general idea for the solution. At each point we must find an element to the left that is less than the current element and an element to the right that is also less than the current element. The total for that element is then value of the element * (number of elements to the left greater than itself + number of elements to the right greater than itself).
    So I went ahead and used two arrays. The low and high array.
    How do these arrays work?

    1. The high array. This stores the number of elements that are greater than equal to it from the end of the array.
    2. The low array. This stores the number of elements that are greater than equal to it from the left of it.

    The way to calculate these arrays is the key to reducing the algorithm from O(n^2) to O(n).
    Let's consider an example [2,1,5,6,2,3].
    high[0,0,0,0,0,0]
    To calculate the high array, we start from the element i=4 (element 2). The element 3>2 and there are 0(high[5]) elements that are greater than 3. How ever, there can be an element that can be equal to 2. So we go ahead and jump to the index high[5]+1 and we keep doing this until the index is less than the length of the array. So, now high[0,0,0,0,1,0].
    Next we calculate for index i=3 (element 6). We see that 2 is not greater than 6. So we don't go any further.
    So, now high[0,0,0,0,1,0].
    Keep doing this and the eventual value of high will be high[0,4,1,0,1,0].
    We do the same for the low array as well.

    The to find the area we just do the following calculation heights[i] * (low[i]+high[i]+1)

    The time complexity O(n) and not O(n^2), because we there can be atmost 1 element in which we check n previous values.
    Consider the array {4,5,6,7,8,9,10,3,2,1}.
    (Correct me if i am wrong. I am not really positive about it being O(n), but I am sure that it's not O(n^2)).

    Update: Looks like there are other threads that have a similar solution that explains it. For reference https://discuss.leetcode.com/topic/54866/detailed-explanation-of-this-problem-o-n

    public class Solution {
        public int largestRectangleArea(int[] heights) {
            if(heights==null||heights.length==0){
                return 0;
            }
            int max=0;
            int[] low = new int[heights.length];
            int[] high = new int[heights.length];
            
            for(int i=high.length-2; i>=0; i--){
                int j=i+1;
                while(j<high.length){
                    if(heights[j]>=heights[i]){
                        high[i]+=high[j]+1;
                    }else{
                        break;
                    }
                    j+=high[j]+1;
                }
            }
            for(int i=0; i<low.length; i++){
                int j=i-1;
                while(j>=0){
                    if(heights[j]>=heights[i]){
                        low[i]+=low[j]+1;
                    }else{
                        break;
                    }
                    int temp=(low[j]+1);
                    j=j-temp;
                }
            }
            for(int i=0; i<heights.length; i++){
                int area= heights[i]*(low[i]+high[i]+1);
                if(area>max) max=area;
            }
            
            return max;
        }
        
    }
    

Log in to reply
 

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