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

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

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

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

• really nice solution

• @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!

• @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.

• This post is deleted!

• @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?

• @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.

• @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?

• @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).

• @aybekko97 I think I get it. So it's amortized O(N).

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

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

• This post is deleted!

• The setting of lessFromLeft and lessFromRight loops in a triangular series per index which gives this solution an overall runtime of O(n^2). The advantage of a stack-based approach is that you can skip over indexes that you've already processed which gives even the worst case of O(n). For example here's my solution:

``````class Solution {
public int largestRectangleArea(int[] heights) {

Deque<Integer> stack = new ArrayDeque<>(heights.length);
int last_h = 0;
int max = 0;

for (int i = 0; i <= heights.length; i++) {
int height = i == heights.length ? 0 : heights[i];

if (height < last_h) {
int j = stack.peekLast();
int prev_j = j;
int prev_h = heights[j];
while (prev_h > height) {
prev_j = j;
stack.removeLast();
int area = prev_h * (i - j);
max = Math.max(max, area);
if (stack.isEmpty()) {
break;
}

j = stack.peekLast();
prev_h = heights[j];
}

heights[prev_j] = height;

} else {