# Does any one got an AC using sparse table.

• 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?
Thank you !

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

• 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);
}
};``````

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