Problem

Submissions

Hints & solutions

Discuss

Largest rectangle in a histogram

Hard

0/120

Average time to solve is 25m

163 upvotes

Asked in companies

Problem statement

You have been given an array/list 'HEIGHTS' of length ‘N. 'HEIGHTS' represents the histogram and each element of 'HEIGHTS' represents the height of the histogram bar. Consider that the width of each histogram is 1.

You are supposed to return the area of the largest rectangle possible in the given histogram.

For example :

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.

Detailed explanation ( Input/output format, Notes, Images )

Input format :

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.

Output format :

For each test case, print an integer denoting the area of the largest rectangle possible in the given histogram.

Note :

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints :

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.

Sample Input 1 :

2
10
1 0 1 2 2 2 2 1 0 2 
10
1 2 1 0 1 1 0 0 2 2

Sample Output 1 :

8
4

Explanation For Sample Input 1 :

In the first test case, the area of the largest rectangle of the given histogram is 8 in the rectangle starting from index 4 to index 7 in the given array/list.

In the second test case, the area of the largest rectangle of the given histogram is 4 in the rectangle starting from index 9 to index 10 in the given array/list.

Sample Input 2 :

2
10
8 6 3 5 0 0 4 10 2 5 
10
6 1 8 10 5 7 0 4 5 8

Sample Output 2 :

12
20

Explanation For Sample Input 2 :

In the first test case, the area of the largest rectangle of the given histogram is 12.

In the second test case, the area of the largest rectangle of the given histogram is 20.

Hint 1

Hint 2

Hint 3

Hint 4

Consider all bars as starting points and calculate areas of all the corresponding rectangles.

Approaches (4)

Approach 1

Approach 2

Approach 3

Approach 4

Brute Force

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.

Time Complexity

O(N^2), where ‘N’ is the number of elements in the given array/list.

We are considering each bar as the starting point and hence iterating to the whole array for each bar accounting to N^2 iterations. So the overall time complexity will be O(N^2).

Space Complexity

O(1)

Since no extra space is required, the overall space complexity will be O(1).

(75% EXP penalty)

(100% EXP penalty)

Largest rectangle in a histogram

Console