Largest Rectangle in Histogram Problem Statement

You are given an array/list HEIGHTS of length N, where each element represents the height of a histogram bar. The width of each bar is considered to be 1.

Your task is to compute the area of the largest rectangle that can be formed within the bounds of the given histogram.

Example:

Input:

{2, 1, 5, 6, 2, 3}

Output:

10

Explanation:

In the given histogram, the largest rectangle possible has an area of 10.

Input:

The first line contains a single integer 'T’, representing the number of test cases. For each test case, the first line contains a single integer 'N' representing the number of elements in the array/list. The second line contains 'N' single space-separated integers, denoting the elements of the array/list HEIGHTS.

Output:

For each test case, output an integer that represents the area of the largest rectangle possible in the given histogram.

Constraints:

1 ≤ T ≤ 10

1 ≤ N ≤ 10^6

0 ≤ HEIGHTS[i] ≤ 10^9

Time Limit: 1 sec.

Note:

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

Question

Largest Rectangle in Histogram Problem Statement

You are given an array/list HEIGHTS of length N, where each element represents the height of a histogram bar. The width of each bar is considered to be 1.

Your task is to compute the area of the largest rectangle that can be formed within the bounds of the given histogram.

Example:

Input:

{2, 1, 5, 6, 2, 3}

Output:

Explanation:

In the given histogram, the largest rectangle possible has an area of 10.

Input:

The first line contains a single integer 'T’, representing the number of test cases. For each test case, the first line contains a single integer 'N' representing the number of elements in the array/list. The second line contains 'N' single space-separated integers, denoting the elements of the array/list HEIGHTS.

Output:

For each test case, output an integer that represents the area of the largest rectangle possible in the given histogram.

Constraints:

1 ≤ T ≤ 10
1 ≤ N ≤ 10^6
0 ≤ HEIGHTS[i] ≤ 10^9
Time Limit: 1 sec.

Note:

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

Accepted Answer

The task is to find the largest rectangle possible in a given histogram and return its area.

Iterate through the histogram and maintain a stack to keep track of the indices of the bars in non-decreasing order of heights.
For each bar, calculate the area of the rectangle that can be formed using that bar as the smallest bar.
To calculate the area, pop the bars from the stack until a bar with a smaller height is encountered.
The width of the rectangle will be the difference between the current index and the index of the previous bar in the stack.
Calculate the area by multiplying the height of the popped bar with the width.
Keep track of the maximum area encountered so far and return it as the result.