In the below histogram where array/list elements are {2, 1, 5, 6, 2, 3}.
The area of largest rectangle possible in the given histogram is 10.
The first line contains a single integer ‘T’ denoting the number of test cases.
The first line of each test case contains a single integer ‘N’ denoting the number of elements in the array/list.
The second line contains ‘N’ single space-separated integers denoting the elements of the array/list.
For each test case, print an integer denoting the area of the largest rectangle possible in the given histogram.
You do not need to print anything; it has already been taken care of. Just implement the given function.
1 <= T <= 10
1 <= N <= 10^6
0 <= HEIGHTS[i] <= 10^9
Where ‘T’ is the number of test cases.
'N' is the length of the given array/list.
And, HEIGHTS[i] denotes the height of the 'ith' histogram bar.
Time Limit: 1 sec.
Our intuition is to consider each and every rectangle once so that we can calculate which rectangle has the maximum area.
A simple solution to this problem is to one by one consider all bars as starting points and calculate the area of all rectangles starting with every bar and iterating towards the end of the array/list. Finally, return the maximum of all possible areas.
The idea is to find the minimum value in the given array/list which comes out to be the lowest histogram bar. Now once we have an index of the minimum value, the max area is the maximum of the following three values.
We use a loop with two pointers named “LPTR” and “RPTR” and at each iteration, we advance the one that has a higher neighbour until I reach the end in both directions.
In this approach, we will create a segment tree. In each node of the segment tree, we will maintain a range of elements and the index of the minimum element in the range. We will create a class SegTreeNode which contains the following members-:
After creating the tree, we will use the segment tree to find the maximum area of the histogram. We will find the index of the minimum element in the range from start to end and let take the variable name as minIndex. At each step, we have three possibilities-:
Algorithm:
For every bar ‘X’, we calculate the area with ‘X’ as the smallest bar in the rectangle. If we calculate such an area for every bar ‘X’ and find the maximum of all areas, our task is done. How to calculate the area with ‘X’ as the smallest bar? We need to know the index of the first smaller (smaller than ‘X’) bar on the left of ‘X’ and the index of the first smaller bar on the right of ‘X’. Let us call these indexes ‘LEFT_INDEX' and ‘RIGHT_INDEX’ respectively.
We traverse all histograms from left to right, maintaining a stack of histograms. Every histogram is pushed to stack once. A histogram is popped from the stack when a histogram of smaller height is seen. When a histogram is popped, we calculate the area with the popped histogram as the smallest histogram. How do we get the left and right indexes of the popped histogram – the current index tells us the ‘RIGHT_INDEX’ and the index of the previous item in the stack is the ‘LEFT_INDEX'.
Longest Subarray With Zero Sum
Merge Two Sorted Arrays Without Extra Space
Merge Two Sorted Arrays Without Extra Space
Ninja And The Strictly Increasing Array
Negative To The End
Find Duplicate in Array