Home » Interview coding problems/challenges

Largest rectangle area in a histogram

Here, we are going to find the largest rectangular area possible in a given histogram – this problem has been featured in coding rounds of many companies such as amazon, Maq Software, snapdeal, paytm, etc. Submitted by Divyansh Jaipuriyar, on May 12, 2020

Problem statement

Find the largest rectangular area possible in a given histogram where the largest rectangle can be made of a number of contiguous bars. For simplicity, assume that all bars have the same width and the width is 1 unit.

Input

The first line contains an integer T denoting the total number of test cases. T test-cases follow. In each test case, the first line contains an integer N denoting the size of the array. The second line contains N space-separated integers A1, A2, ..., AN denoting the elements of the array. The elements of the array represent the height of the bars.

Output

For each test-case, in a separate line, the maximum rectangular area possible from the contiguous bars.

Examples

    Input:	
    T = 1
    N = 7
    [6,2,5,4,5,1,6]
    
    Output: 
    12 
    Covering from index 2 to 4 with height 4 units and width 3 units.

    Input:
    T = 1
    N = 4
    [6,3,4,2]
    
    Output: 
    9 
    Covering 3 units of width and 3 unit of height.

Solution Approach

1) Brute Force Approach

We will check for each element the maximum distance up to which it can be extended, we will check for its left and right maximum distance than it can be extended then we will take the difference between the right and left distance and multiply it with the height of the current element, we will follow the same procedure for all elements and take the maximum of them for our answer.

To get the left and right distance we will use the array index.

Pseudo Code:

maxarea(int height[], int n)
{
    int maxArea = 0;
    for (int i = 0; i < n; ++i) {
        int minHeight = height[i];
        //check maximum of current area and area due
        //to single height and one unit width.
        maxArea = max(maxArea, minHeight * 1);

        //check for min height than the current element
        //in right side.
        for (int j = i + 1; j < height.size(); ++j) {
            minHeight = min(minHeight, height[j]);
            // area is calculated as (j-i+1)*minHeight.
            maxArea = max(maxArea, minHeight * (j - i + 1));
        }
    }
    return maxArea; //return maximum area.
}

• Time complexity for above approach is: O(n*n)
• Space Complexity for above approach is: O(1)

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main()
{

    ll t;

    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        ll n; //size of height array.

        cout << "Enter size : ";
        cin >> n;

        ll arr[n];

        cout << "Enter heights: ";
        for (ll i = 0; i < n; i++)
            cin >> arr[i];

        ll maxArea = 0;

        for (int i = 0; i < n; ++i) {
            ll minHeight = arr[i];
            maxArea = max(maxArea, minHeight * 1);
            for (int j = i + 1; j < n; ++j) {
                minHeight = min(minHeight, arr[j]);
                maxArea = max(maxArea, minHeight * (j - i + 1));
            }
        }

        cout << "Maximum area possible: ";
        cout << maxArea << "\n";
    }

    return 0;
}

Output

Enter number of test cases: 3     
Enter size : 6
Enter heights: 5 6 7 8 9 10
Maximum area possible: 30
Enter size : 6
Enter heights: 5 4 5 6 8 2
Maximum area possible: 20
Enter size : 3
Enter heights: 4 5 6
Maximum area possible: 12

2) Stack Method

Here we will use stack with pair, the stack will store array element and index of that array element. We will use two vectors for storing the index of left minimum value just before the current element and right minimum value just after the current element.

Since the current element width can vary only from left min to right min of the current element.

The maximum area covered by this array element will be the width*height.

Here the array arr[] is taken as the height of the histogram.

Pseudo Code:

maxarea(int arr[], int n)
{
    //declare stack with pair as its elements.
    stack > st;

    //declare vector to store index of left min element
    //to left and right minm element to right.
    vector left, right;

    //push initial element as INT_MIN at index -1 since
    //first element is taken from index 0 and we are considering
    //width of the rectangle as (right-left-1),
    //to make it valid in all cases we take as -1 based minimum
    //element.
    st.push({ INT_MIN, -1 });

    //iterate through all element of the array.
    for (int i = 0; i < n; i++) {
        //check if stack is empty or not.
        while (!st.empty()) {
            //check the top of stack as less than current element
            //if less than store it in the left vector.
            if (st.top().first < arr[i]) {
                //if less than push it into the left vector and break
                // from while loop(first min element to left of current element).
                left.push_back(st.top().second);
                break;
            }
            else //if top of element is not smaller than pop it from stack.
                st.pop();
        }
        //push the current pair of array element and index into stack.
        st.push({ arr[i], i });
    }
    //after traversing for left minimum element now check if stack is empty or not.
    while (!st.empty())
        st.pop();

    //we push INT_MIN at nth index beacase we take right minimum element
    //from (n-1)th element and there is no element which is smaller to it
    //in the right side,hence to make it valid we take it at nth index.
    st.push({ INT_MIN, n });
    //iterate through the array element right right to left manner.
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty()) //check if stack is empty or not.
        {
            //is stack top element is smaller than the current
            //element than push it into right vector.
            if (st.top().first < arr[i]) {
                right.push_back(st.top().second);
                break;
            }
            else //if top of element is not smaller than pop it from stack.
                st.pop();
        }
        //push the current pair of array element and index into stack.
        st.push({ arr[i], i });
    }

    //reverse the vector elements as we filled it in reverse manner.
    reverse(right.begin(), right.end());
    int ans = 0; //initialise ans as minm value

    for (int i = 0; i < n; i++) //iterate through array elements.
        //keep calculating area and simultaneoulsy
        //checking its max area,(area=width*height).
        ans = max(ans, (right[i] - left[i] - 1) * arr[i]);
    //(-1)is subtracted from width because of 0 based index.
    return ans; //return final ans.
}

• Time Complexity for above approach is: O(n)
• Space Complexity for above approach is: O(n)

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main()
{

    ll t;
    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        ll n; //size of height array.
        cout << "Enter size : ";
        cin >> n;

        ll arr[n];

        cout << "Enter heights: ";
        for (ll i = 0; i < n; i++)
            cin >> arr[i];

        //stack with pairs.
        stack<pair<ll, ll> > st;

        //initial minimum at index -1 since left of
        // index have no element and
        //we are considering width as (right-left-1)
        st.push({ INT_MIN, -1 });

        //declare left and right vector for storing index.
        vector<ll> left, right;

        //iterate through loop.
        for (ll i = 0; i < n; i++) {
            //check if stack is empty or not.
            while (!st.empty()) {
                //compare array elements with top of stack for
                // storing first left mimimum element.
                if (st.top().first < arr[i]) {
                    left.push_back(st.top().second);
                    break;
                }
                //if stack top is element not less than
                //current element then pop.
                else
                    st.pop();
            }
            //push curret element with its index.
            st.push({ arr[i], i });
        }

        //if some elements is still in the
        //stack then pop elements.
        while (!st.empty())
            st.pop();

        //push mimimum right element at index n as there is
        //no right element with last element.
        st.push({ INT_MIN, n });

        //iterate through loop.
        for (ll i = n - 1; i >= 0; i--) {
            //check if stack is empty or not.
            while (!st.empty()) {
                //compare array elements with top of stack for
                //storing first left mimimum element.
                if (st.top().first < arr[i]) {
                    right.push_back(st.top().second);
                    break;
                }
                //if stack top is element not less than
                //current element then pop.
                else
                    st.pop();
            }
            //push curret element with its index.
            st.push({ arr[i], i });
        }
        //reverse right index vector since it is
        //filled from n-1 to 0.
        reverse(right.begin(), right.end());
        //initial ans as 0 and then compare with the areas.
        ll ans = 0;

        for (ll i = 0; i < n; i++) {
            //area is calculated as ((right[i]-left[i]-1)*height(i)),width*height.
            ans = max(ans, (right[i] - left[i] - 1) * arr[i]);
        }
        cout << "Maximum area possible: ";
        cout << ans << "\n";
    }
    return 0;
}

Output

Enter number of test cases: 3
Enter size : 5
Enter heights: 9 7 5 2 4
Maximum area possible: 15
Enter size : 7
Enter heights: 6 2 5 4 5 1 6
Maximum area possible: 12
Enter size : 5
Enter heights: 10 8 12 8 8
Maximum area possible: 40

---

Problem reference: https://leetcode.com/problems/largest-rectangle-in-histogram/