5ms O(n) Java solution explained (beats 96%)


  • 43
    A

    For any bar i the maximum rectangle is of width r - l - 1 where r - is the last coordinate of the bar to the right with height h[r] >= h[i] and l - is the last coordinate of the bar to the left which height h[l] >= h[i]

    So if for any i coordinate we know his utmost higher (or of the same height) neighbors to the right and to the left, we can easily find the largest rectangle:

    int maxArea = 0;
    for (int i = 0; i < height.length; i++) {
        maxArea = Math.max(maxArea, height[i] * (lessFromRight[i] - lessFromLeft[i] - 1));
    }
    

    The main trick is how to effectively calculate lessFromRight and lessFromLeft arrays. The trivial solution is to use O(n^2) solution and for each i element first find his left/right heighbour in the second inner loop just iterating back or forward:

    for (int i = 1; i < height.length; i++) {              
        int p = i - 1;
        while (p >= 0 && height[p] >= height[i]) {
            p--;
        }
        lessFromLeft[i] = p;              
    }
    

    The only line change shifts this algorithm from O(n^2) to O(n) complexity: we don't need to rescan each item to the left - we can reuse results of previous calculations and "jump" through indices in quick manner:

    while (p >= 0 && height[p] >= height[i]) {
          p = lessFromLeft[p];
    }
    

    Here is the whole solution:

    public static int largestRectangleArea(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        int[] lessFromLeft = new int[height.length]; // idx of the first bar the left that is lower than current
        int[] lessFromRight = new int[height.length]; // idx of the first bar the right that is lower than current
        lessFromRight[height.length - 1] = height.length;
        lessFromLeft[0] = -1;
    
        for (int i = 1; i < height.length; i++) {
            int p = i - 1;
    
            while (p >= 0 && height[p] >= height[i]) {
                p = lessFromLeft[p];
            }
            lessFromLeft[i] = p;
        }
    
        for (int i = height.length - 2; i >= 0; i--) {
            int p = i + 1;
    
            while (p < height.length && height[p] >= height[i]) {
                p = lessFromRight[p];
            }
            lessFromRight[i] = p;
        }
    
        int maxArea = 0;
        for (int i = 0; i < height.length; i++) {
            maxArea = Math.max(maxArea, height[i] * (lessFromRight[i] - lessFromLeft[i] - 1));
        }
    
        return maxArea;
    }

  • 7
    J

    The classic stack solution is simpler. However, using collection will be slower. Here is an implementation using int array to simulation a stack. The run time is 5 ms.

    public class Solution {
        public int largestRectangleArea(int[] h) {
            int n = h.length;
            int max = 0;
            int[] stack = new int[n + 1];
            int is = -1;
            for (int i = 0; i <= n; i++) {
                int height = (i == n) ? 0 : h[i];
                while (is != -1 && height < h[stack[is]]) {
                    int hh = h[stack[is--]];
                    int width = (is == -1) ? i : i - 1 - stack[is];
                    max = Math.max(max, hh * width);
                }
                stack[++is] = i;
            }
            return max;
        }
    }

  • 3
    W

    even you use p = lessFromLeft[p]; to jump quickly, I still do not think it is O(n) for the whole lessFromLeft array.


  • 0
    Y

    really nice solution


  • 1
    G

    @weihui Me too. I think it's still overall O(n^2) for worst case ([1,2,3,4,5,6,7...]). But the solution is great idea!


  • 2
    U

    @gtx108 This is still a O(N) solution. Try to compare it with Stack based solution. Both of these solutions are working in a similar manner but implemented in a different way. I hope @anton4 will second me.


  • 0
    C
    This post is deleted!

  • 0
    R

    @ufarooqi Could you explain more? Just like @gtx108 mentioned, worst case ([1,2,3,4,5,6,7...]) for lessFromLeft would be O(N^2), right?


  • 0
    A

    @River3 If we look attentively to the case, when it checks if the element from left is smaller than current element, it doesn't make a loop and steps into if. Therefore, it takes only O(n).
    A bit like KMP algo's implementation.


  • 0
    R

    @aybekko97 Say the previous result is [1,2,3,4,5,6,7], now given current element 0. then from 7 we jump to 6, then jump to 5, to 4, 3, 2, 1. Still need to compare N time for a single element right?


  • 2
    A

    @River3 Let's assume the array lessFromLeft calculated until now is [0,0,1,2,3,4,5] and heights array is [1,2,3,4,5,6,7,curr->1], yep it will loop until the element with index 0, but it makes this loop once for some range. Try to think on this example: [1,2,3,4,5,6,7,1,2,3,4,5,6,7] one loop from 7th to 0th elem., and from 14th to 7th. Then, if we sum these ranges it gives us O(n).


  • 0
    R

    @aybekko97 I think I get it. So it's amortized O(N).
    Thank you for your explanation!


  • 0
    L

    This by average is O(N) thanks to the quick jump.
    I use a similar idea, and it is pretty fast.


  • 0
    J

    The while loop runs at most 2N times, so its worst case O(N)


  • 0
    Y
    This post is deleted!

Log in to reply
 

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