# Java O(n) left/right arrays solution, 4ms beats 96%

• Basically, you run 3 passes:

1. Scan from left to right to compute left[], which represents the left most boundary of current height.

2. Scan from right to left to compute right[], which represents the right most boundary of current height.

3. Scan from left to right again to compute rectangle area based on the height of that each position.

``````public class Solution {
public int largestRectangleArea(int[] heights) {
// validate input
if(heights == null || heights.length == 0) {
return 0;
}

// init
int n = heights.length;
int[] left = new int[n];
int[] right = new int[n];
int result = 0;

// build left
left[0] = 0;
for(int i = 1; i < n; i++) {
int currentLeft = i-1;
while(currentLeft >= 0 && heights[currentLeft] >= heights[i]) {
currentLeft = left[currentLeft]-1;
}

left[i] = currentLeft+1;
}

// build right
right[n-1] = n-1;
for(int i = n-2; i >= 0; i--) {
int currentRight = i+1;
while(currentRight < n && heights[i] <= heights[currentRight]) {
currentRight = right[currentRight]+1;
}

right[i] = currentRight-1;
}

// compare height
for(int i = 0; i < n; i++) {
result = Math.max(result, (right[i]-left[i]+1)*heights[i]);
}

// return
return result;
}
}``````

• why not

``````left[0] = 0;
for(int i = 1; i < n; i++) {
left[i] = (height[i] > height[left[i - 1]]) ? i : left[i - 1];
}
``````

update : I see. Your are trying to find the element as left as possible, right?

• Genius idea. Something like dynamic programming. Store the left bound and right bound in the array. Greate implementation.

• You sure it is O(n)?
what about an ascending array or descending?

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