# Beats 93%, Java, no stack

• thanks to @zerobased, the idea of copying heights to another array with one more element is great.

``````public int largestRectangleArea(int[] heights) {
// The basic idea is below:
// if (heights[i] <= heights[i + 1]), continue. Because the area contains heights[i + 1] will definitely larger than heights[i].

// copy the array, the idea copies from @zerobased
int[] newHeights = new int[heights.length + 1];

// newHeights[newHeights.length - 1] = 0, easier to handle the edge cases.
for (int i = 0; i < heights.length; i++) {
newHeights[i] = heights[i];
}

int res = 0;

for (int i = 0; i < newHeights.length - 1; i++) {
if (newHeights[i] <= newHeights[i + 1]) {
continue;
}

int lowest = newHeights[i];

for (int j = i; j >= 0; j--) {
lowest = Math.min(lowest, newHeights[j]);
int area = lowest * (i - j + 1);
res = Math.max(res, area);
}
}

return res;

}``````

• I don't understand why this solution is so fast. It seems an O(n^2) to me. I used a stack and an O(n) solution but is far slower than this one. Could anyone explain to me?

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