Does any one got an AC using sparse table.


  • 0
    W

    I use a sparse table to store min value of intervals, then I use O(nlogn) "divide and concur" to solve it.
    However, I still got TLE error.
    Does any one try sparse table or interval tree and got an AC?
    Can you share your code?
    Thank you !


  • 0
    S

    I believe using sparse table or interval tree is a way to solve this problem.

    Take a look at this answer. It might broaden your horizon.


  • 1
    M

    The idea is to find the base bar which gives the maximum area. Lowest bar is the option, divided by the lowest bar, the original vector is divided into 3 sections, [leftSide, lowestbar, rightSide], Recursively call leftSide and RightSide.

    Since find lowest Bar is O(n) generally, T(n) = T(k-1) + T(n-k) + n, in the worst case, T(n) = n^2, in order to optimise the performance to O(nlogn), segment tree is a good option since it costs O(n) construction and O(logn) query.

    The following is my Ac code, please feel free to comment it.

    class Solution {
    public:
        void buildMinRange(const vector<int>& height, int b, int e, int node, vector<int>& M)
        {
            if(b == e) M[node] = b;
            else
            {
                int mid = b + (e-b)/2;
                buildMinRange(height, b, mid, node*2, M);
                buildMinRange(height, mid+1, e, node*2+1, M);
                if(height[M[node*2]] <= height[M[node*2+1]])
                    M[node] = M[node*2];
                else
                    M[node] = M[node*2+1];
            }
        }
        
        int findMin(int i, int j, const vector<int>& height, int node, int b, int e, const vector<int>& M)
        {
            if(j < b || i > e) return -1;
            if(i<= b && j >= e) return M[node];
            int mid = b + (e-b)/2;
            int p = findMin(i, j, height, node*2, b, mid, M);
            int q = findMin(i, j, height, node*2+1, mid+1, e, M);
            if(p == -1) return q;
            if(q == -1) return p;
            if(height[p] <= height[q]) return p;
            else return q;
        }
        int largestRectangleArea(int i, int j, const vector<int>& height, const vector<int>& M)
        {
            if(i > j) return 0;
            if( i == j) return height[i];
            int lowest  = findMin(i, j, height, 1, 0, height.size()-1, M);
            int area = height[lowest]*(j-i+1);
            int leftArea = largestRectangleArea(i, lowest-1, height, M);
            int rightArea = largestRectangleArea(lowest+1, j, height, M);
            return max(area, max(leftArea, rightArea));
        }
        int largestRectangleArea(vector<int> &height) {
           if(height.empty()) return 0;
           int sz = height.size();
           int h = ceil(log2(sz));
           vector<int> M(1<<(h+1), -1);
           buildMinRange(height, 0, sz-1, 1, M);
           return largestRectangleArea(0, sz-1, height, M);
        }
    };

Log in to reply
 

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