# [Largest Rectangle in Histogram] AC Java solution, what is the running time, is it O(n)?

• According to the OJ, the code seems run very fast, but I am not certain about its running time, is it O(n)?

``````public class Solution {

public int largestRectangleArea(int[] height) {
if (height.length ==0) return 0;

//right[[i]  calculates the number of  consecutive bars from left side of the i-th bar   whose heights are       larger or equal to height[i],   including the i-th bar;
int[] right = new int [height.length];

//left[[i]  calculates the number of  consecutive bars from right side of the i-th bar   whose heights are larger or equal to height[i],   excluding the i-th bar;
int[] left = new int [height.length];

// record[i]  is just right[i] * height[i]
int[] record = new int[height.length];

// max is used to  store the maximal area;
int max = 0;

// build the arrays  int[] right and  int[] record
for (int i = 0; i < height.length; i++){
if (height[i] > max) max = height[i];
}
right[0] = 1;
record[0] = height[0];
left[height.length-1] = 0;

for (int i = 1; i < height.length; i++){
if (height[i-1] < height[i]) right[i] = 1;
else{
int j = i - right[i-1] -1 ;
//  the following while loop  is the reason I am not sure the running time
while (j >= 0 && height[j] >= height[i]){
j-= right[j];
}// end while
right[i] = i - j;
}// end else
record[i]= right[i] * height[i];

}// end for

int area = 0;
// build the array int[] left, and find the maximal area
for (int i = height.length-2; i >= 0 ; i--){
if (height[i+1] < height[i]) left[i] = 0;
else{
int j = i + left[i+1] + 2 ;
//  the following while loop is the reason I am not sure the running time
while ( j < height.length && height[j] >= height[i]){
j+= left[j] + 1 ;
}// end while
left[i] = j - i -1;

}// end else
area = left[i] * height[i] + record[i];
if ( area > max) max =  area;

}// end for
if (record[height.length-1] > max) return record[height.length-1];
return max;

}// end largestRectangleArea
}// end Solution``````

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