TLE for the 3000 consecutive 1s


  • 0
    J

    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);
    

Log in to reply
 

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