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


  • 38
    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;
        }
    }

  • 2
    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)


Log in to reply
 

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