# TLE for the 3000 consecutive 1s

• My program gets TLE on the last test case. I heavily optimized it specifically for this case, but it still gets TLE. It basically just executes a tight loop, so I don't see how there could be a faster solution for this particular case. With custom test case run code it executes in 3ms. This is the code:

``````class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n = heights.size();

if(n==0) {
return 0;
}

vector<int> lowest_height(2);
vector<int> lowest_height_index(2);
lowest_height_index[0] = -1;
lowest_height_index[1] = 0;
lowest_height[1] = heights[0];

int l_h_start_index = 1, l_h_end_index = 1;

int left = 0, rect_height = heights[0];
int largest_size = rect_height, cur_size = rect_height;
int prev = rect_height;

for(int i=1; i<n; i++) {
int h = heights[i];

if(h == prev) {
lowest_height_index[l_h_end_index] = i;
if(l_h_start_index < l_h_end_index) {
maximize(
lowest_height, lowest_height_index,
l_h_start_index+1, l_h_end_index,
i,
left, rect_height, cur_size, l_h_start_index
);
}
continue;
}

int index = binarySearch(lowest_height, 1, l_h_end_index+1, h);

l_h_end_index = index;
if(index == lowest_height.size()) {
lowest_height.push_back(0);
lowest_height_index.push_back(0);
}
int ph = lowest_height[index];
lowest_height[index] = h;
lowest_height_index[index] = i;

if(index < l_h_start_index || (index == l_h_start_index && h < ph)) {
cur_size = (i - left) * rect_height;
largest_size = max(largest_size, cur_size);

l_h_start_index = index;
left = lowest_height_index[index-1]+1;
rect_height = h;

if(l_h_end_index > 1) {
maximize(
lowest_height, lowest_height_index,
1, l_h_end_index-1,
i,
left, rect_height, cur_size, l_h_start_index
);
}
}
else if(l_h_start_index < l_h_end_index) {
maximize(
lowest_height, lowest_height_index,
l_h_start_index+1, l_h_end_index,
i,
left, rect_height, cur_size, l_h_start_index
);
}

prev = h;
}

cur_size = (n - left) * rect_height;
return max(largest_size, cur_size);
}

private:
// find index in range [left, right) of first value greater than or equal to x
// if no such index exists, return right
inline int binarySearch(const vector<int>& xs, int left, int right, const int x) const {
do {
int mid = (left + right)/2;
int x_ = xs[mid];
if(x_ >= x) {
right = mid;
}
else {
left = mid+1;
}
} while(left < right);
return right;
}

void maximize(
const vector<int>& lowest_height, const vector<int>& lowest_height_index,
int l_h_start, const int l_h_end,
int i,
int& left, int& rect_height, int& cur_size, int& l_h_start_index
) const {
cur_size = (i - left + 1) * rect_height;
do {
int new_left = lowest_height_index[l_h_start-1]+1;
int new_height = lowest_height[l_h_start];
int new_size = (i - new_left + 1) * new_height;
if(new_size > cur_size) {
left = new_left;
rect_height = new_height;
cur_size = new_size;
l_h_start_index = l_h_start;
}
l_h_start++;
} while (l_h_start <= l_h_end);
}
};
``````

Note that for the all 1s test case it basically just executes the following code:

``````int n = heights.size();

if(n==0) {
return 0;
}

vector<int> lowest_height(2);
vector<int> lowest_height_index(2);
lowest_height_index[0] = -1;
lowest_height_index[1] = 0;
lowest_height[1] = heights[0];

int l_h_start_index = 1, l_h_end_index = 1;

int left = 0, rect_height = heights[0];
int largest_size = rect_height, cur_size = rect_height;
int prev = rect_height;

for(int i=1; i<n; i++) {
int h = heights[i];

if(true) {
lowest_height_index[l_h_end_index] = i;
if(false);
continue;
}
}

cur_size = (n - left) * rect_height;
return max(largest_size, cur_size);
``````

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