Largest rectangle in a histogram
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.

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

Question

Largest rectangle in a histogram

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}.

alt text

The area of largest rectangle possible in the given histogram is 10.

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.

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.

Accepted Answer

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.

Space Complexity: O(1)Explanation:

O(1)

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

Time Complexity: O(n^2)Explanation:

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).

Java (SE 1.8)


/*
	Time Complexity = O(N^2)
	Space Complexity = O(1)
	
	Where N is the number of elements in the given array/list.
*/

import java.util.ArrayList;

public class Solution {
	public static int largestRectangle(ArrayList heights) {
		int n = heights.size();

		if (n <= 0) {
			return 0;
		}

		int maxArea = 0;

		for (int j = 0; j < n; j++) {
			// Store current index value as both min and max values.
			int minVal = heights.get(j), maxVal = heights.get(j);

			for (int i = j - 1; i >= 0; i--) {
				// If current index value is less than minVal.
				if (heights.get(i) < minVal) {
					minVal = heights.get(i);
				}

				/*
				 * If area of the current rectangle is greater than maxVal.
				 */
				if (minVal * (j - i + 1) > maxVal) {
					maxVal = minVal * (j - i + 1);
				}
			}

			// Store the maximum area of the rectangle.
			if (maxVal > maxArea) {
				maxArea = maxVal;
			}
		}

		// Return area of largest rectangle.
		return maxArea;
	}

}

C++ (g++ 5.4)

/*

    Time Complexity = O(N^2)

    Space Complexity = O(1)

    

    Where N is the number of elements in the given array/list.

*/



int largestRectangle(vector < int > & heights) {

    int n = heights.size();



    if (n <= 0) {

        return 0;

    }



    int maxArea = 0;



    for (int j = 0; j < n; j++) {

        // Store current index value as both min and max values.

        int minVal = heights[j], maxVal = heights[j];



        for (int i = j - 1; i >= 0; i--) {

            // If current index value is less than minVal.

            if (heights[i] < minVal) {

                minVal = heights[i];

            }



            /*

            	If area of the current rectangle 

                is greater than maxVal.

            */

            if (minVal * (j - i + 1) > maxVal) {

                maxVal = minVal * (j - i + 1);

            }

        }



        // Store the maximum area of the rectangle.

        if (maxVal > maxArea) {

            maxArea = maxVal;

        }

    }



    // Return area of largest rectangle.

    return maxArea;

}

Python (3.5)

'''

    Time Complexity = O(N^2)

    Space Complexity = O(1)

    

    Where N is the number of elements in the given array/list.

'''



def largestRectangle(heights):  

    n = len(heights)

    if n <= 0:

        return 0;



    maxArea = 0;

    

    for j in range(n):

        

        # Store current index value as both min and max values.

        minVal = heights[j]

        maxVal = heights[j]

        

        i = j - 1

        while i >= 0:

            # If current index value is less than minVal.

            if heights[i]  < minVal:

                minVal = heights[i]

            

            # If area of the current rectangle is greater than maxVal.

            if minVal * (j - i + 1) > maxVal:

                maxVal = minVal * (j - i + 1);



            # Store the maximum area of the rectangle.    

            if maxVal > maxArea:

                maxArea = maxVal;

            

            i -= 1

    

    # Return area of largest rectangle.

    return maxArea

Accepted Answer

Divide and Conquer

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.

The maximum area on the left side of the minimum value. Here we are trying to find the area of the rectangle towards the left side of the minimum value bar excluding the min value.
The maximum area on the right side of the minimum value. Here we are trying to find the area of the rectangle towards the right side of the minimum value bar excluding the min value.
The number of bars multiplied by the minimum value.

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.

Space Complexity: O(logn)Explanation:

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

The recursive stack can grow up to log N size, so the overall space complexity will be O(log N).

Time Complexity: O(nlogn)Explanation:

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

Since we are using a divide and conquer approach, we have to calculate the maximum area in both directions for N elements that takes O(N^2) time. So the overall time complexity will be O(N^2).

Python (3.5)

'''

    Time Complexity = O(N^2)

    Space Complexity = O(log N)

    

    Where N is the number of elements in the given array/list.

'''



def divideAndConquer(heights, l, r):



    # If we only have one element then return it.

    if l == r:

        return heights[l]



    mid = (l + r) // 2



    # Recur for left rectangle.

    lscore = divideAndConquer(heights, l, mid)



    # Recur for right rectangle.

    rscore = divideAndConquer(heights, mid + 1, r)



    lptr = mid 

    

    rptr = mid



    maxArea = 0



    minimum = heights[mid]



    while lptr >= l and rptr <= r:

        ''' 

            Take the minimum of lptr height and

            rptr height in comparsion to the minimum. 

        '''

        minimum = min(minimum,heights[lptr], heights[rptr])



        ''' 

            Take the maximum area for 

            the rectangle between lptr and rptr.

        '''

        maxArea = max(maxArea, minimum * (rptr - lptr + 1))



        if (lptr > l) and (rptr < r):

            if heights[rptr + 1] >= heights[lptr - 1]:

                rptr += 1



            else:

                lptr -= 1

        elif lptr > l:

            lptr -= 1



        elif rptr < r:

            rptr += 1



        else:

            rptr += 1

            lptr -= 1



    # Return the maximum area.

    return max(maxArea,lscore, rscore)



def largestRectangle(heights):

    if len(heights) == 0:

        return 0



    return divideAndConquer(heights, 0, len(heights) - 1)

Java (SE 1.8)

/*

    Time Complexity = O(N^2)

    Space Complexity = O(log N)



    Where N is the number of elements in the given array/list.

*/



import java.util.ArrayList;



public class Solution {

    private static int divideAndConquer(ArrayList < Integer > heights, int l, int r) {



        // If we only have one element then return it.

        if (l == r) {

            return heights.get(l);

        }



        int mid = (l + r) / 2;



        // Recur for left rectangle.

        int lscore = divideAndConquer(heights, l, mid);



        // Recur for right rectangle.

        int rscore = divideAndConquer(heights, mid + 1, r);



        int lptr = mid, rptr = mid;



        int maxArea = 0;



        int minimum = heights.get(mid);



        while (lptr >= l && rptr <= r) {

            /* 

                Take the minimum of lptr height and 

                rptr height in comparsion to the minimum.

            */

            minimum = Math.min(minimum, Math.min(heights.get(lptr), heights.get(rptr)));



            /* 

                Take the maximum area for the 

                rectangle between lptr and rptr.

            */

            maxArea = Math.max(maxArea, minimum * (rptr - lptr + 1));



            if (lptr > l && rptr < r) {



                if (heights.get(rptr + 1) >= heights.get(lptr - 1)) {

                    rptr++;

                } else {

                    lptr--;

                }

            } else if (lptr > l) {

                lptr--;

            } else if (rptr < r) {

                rptr++;

            } else {

                rptr++;

                lptr--;

            }

        }



        // Return the maximum area.

        return Math.max(maxArea, Math.max(lscore, rscore));

    }



    public static int largestRectangle(ArrayList < Integer > heights) {

        if (heights.size() == 0) {

            return 0;

        }



        return divideAndConquer(heights, 0, heights.size() - 1);

    }

}

C++ (g++ 5.4)

/*

    Time Complexity = O(N^2)

    Space Complexity = O(log N)

    

    Where N is the number of elements in the given array/list.

*/



int divideAndConquer(vector < int > & heights, int l, int r) {



    // If we only have one element then return it.

    if (l == r) {

        return heights[l];

    }



    int mid = (l + r) / 2;



    // Recur for left rectangle.

    int lscore = divideAndConquer(heights, l, mid);



    // Recur for right rectangle.

    int rscore = divideAndConquer(heights, mid + 1, r);



    int lptr = mid, rptr = mid;



    int maxArea = 0;



    int minimum = heights[mid];



    while (lptr >= l && rptr <= r) {

        /* 

            Take the minimum of lptr height and

            rptr height in comparsion to the minimum.

        */

        minimum = min(minimum, min(heights[lptr], heights[rptr]));



        // Take the maximum area for the rectangle between lptr and rptr.

        maxArea = max(maxArea, minimum * (rptr - lptr + 1));



        if (lptr > l && rptr < r) {

            if (heights[rptr + 1] >= heights[lptr - 1]) {

                rptr++;

            } else {

                lptr--;

            }

        } else if (lptr > l) {

            lptr--;

        } else if (rptr < r) {

            rptr++;

        } else {

            rptr++;

            lptr--;

        }

    }



    // Return the maximum area.

    return max(maxArea, max(lscore, rscore));

}



int largestRectangle(vector < int > & heights) {

    if (heights.size() == 0) {

        return 0;

    }



    return divideAndConquer(heights, 0, heights.size() - 1);

}

Accepted Answer

Segment Tree

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-:

The variables start and end store the starting and end of the current range.
The minimum variable min store the minimum index of the element in the range.
The variables left and right store the pointer to the nodes to the left and right subtree of the current node.

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-:

We will find the area from the range of start to minIndex - 1.
We will find the area from the range of minIndex + 1 to end.
Since the minimum element in the range from start to end is heights[minIndex]. We can choose the histogram with heights[minIndex]. The area of the histogram would be heights[minIndex] * (end - start + 1)
In the end, we will return the maximum area that we have obtained.

Algorithm:

Create a function query(root, heights, start, end)
- We will check if the current range of start to end is out of range of the current segment tree node root.
  - We will return -1
- We will check if the current range of start to end is in the range of the current segment tree node root.
  - We will return the min of root
- Set leftMin as the minimum index from the left subtree of the root,i.e, query(left node of root, heights, start, end)
- Set rightMin as the minimum index from the right subtree of the root,i.e, query(right node of root, heights, start, end)
- Return the index of minimum height element by comparing heights[leftMin] and heights[rightMin].
Create a function calculateMax(heights, root, start, end)
- Check if the current range only contains only one element
  - Return height[start]
- Set minIndex as the minimum element index in the range from start to end
- We will now find the maximum area of histogram from start to minIndex - 1. We will set leftMax as calculateMax(heights, root, start, minIndex - 1)
- We will now find the maximum area of histogram from minIndex + 1 to end. We will set leftMax as calculateMax(heights, root, minIndex + 1, end)
- The minimum element in the range from start to end is heights[minIndex]. We will find the area of the histogram with height heights[minIndex]. We will set minMax as heights[minIndex] * (end - start + 1).
- In the end, we will return the maximum of leftMax, rightMax, and minMax.
Create a function buildSegmentTree(heights, start, end)
- Create a segment tree node root for the current range
- Check if the current range only contains only one element
  - Set min of root as start
  - Return root
- Set middle as the average of start and end
- Set left subtree of root as buildSegmentTree(heights, start, middle)
- Set right subtree of root as buildSegmentTree(heights, middle + 1, end)
- Set min of the root as the index of the minimum element from both parts.
Set root as buildSegmentTree(heights, 0, size of heights - 1)
Set answer as calculateMax(heights, root, 0, size of heights - 1)
Return the variable answer

Space Complexity: O(1)Explanation:

O(N), where N is the number of elements in the given array.

We are creating a segment tree that takes O(N) space in the worst case. The recursion stack also takes O(N) space in the worst case. Hence, the overall space complexity is O(N).

Time Complexity: O(1)Explanation:

O(N*log(N))), where N is the number of elements in the given array.

The time complexity O(N * log(N)) is required to build the segment tree in the worst case. We are finding the maximum area using the segment tree that takes O(N * log(N)) in the worst case. Hence the overall time complexity is O(N * log(N)).

Java (SE 1.8)


/*
    Time Complexity = O(N*log(N))
    Space Complexity = O(N)
    
    Where N is the number of elements in the given array/list.
*/
import java.util.ArrayList;

class SegTreeNode {
	int start;
	int end;
	int min;
	SegTreeNode left;
	SegTreeNode right;

	SegTreeNode(int start, int end) {
		this.start = start;
		this.end = end;
		left = right = null;
	}
};

public class Solution {

	private static int query(SegTreeNode root, ArrayList heights, int start, int end) {
		// The range of current root is out of range
		if (root == null || end < root.start || start > root.end)
			return -1;

		// The range of current root is in the range
		if (start <= root.start && end >= root.end) {
			return root.min;
		}

		int leftMin = query(root.left, heights, start, end);
		int rightMin = query(root.right, heights, start, end);

		if (leftMin == -1)
			return rightMin;

		if (rightMin == -1)
			return leftMin;

		return heights.get(leftMin) < heights.get(rightMin) ? leftMin : rightMin;
	}

	private static int calculateMax(ArrayList heights, SegTreeNode root, int start, int end) {

		// Check if start is greater than end
		if (start > end) {
			return -1;
		}

		// If there is only one element in the histogram
		if (start == end) {
			return heights.get(start);
		}

		int minIndex = query(root, heights, start, end);
		int leftMax = calculateMax(heights, root, start, minIndex - 1);
		int rightMax = calculateMax(heights, root, minIndex + 1, end);
		int minMax = heights.get(minIndex) * (end - start + 1);

		return Math.max(Math.max(leftMax, rightMax), minMax);
	}

	private static SegTreeNode buildSegmentTree(ArrayList heights, int start, int end) {

		if (start > end) {
			return null;
		}

		// Creating a node for the current range
		SegTreeNode root = new SegTreeNode(start, end);

		if (start == end) {
			root.min = start;
			return root;
		} else {
			int middle = (start + end) / 2;

			// Creating recursive calls for left and right subtree
			root.left = buildSegmentTree(heights, start, middle);
			root.right = buildSegmentTree(heights, middle + 1, end);
			root.min = heights.get(root.left.min) < heights.get(root.right.min) ? root.left.min : root.right.min;

			return root;
		}
	}

	public static int largestRectangle(ArrayList heights) {
		if (heights.size() == 0)
			return 0;

		// Build a segment tree
		SegTreeNode root = buildSegmentTree(heights, 0, heights.size() - 1);

		// Calculate the maximum area recursively
		return calculateMax(heights, root, 0, heights.size() - 1);
	}

}

Python (3.5)

'''

    Time Complexity = O(N*log(N))

    Space Complexity = O(N)



    Where N is the number of elements in the given array/list.

'''





from typing import List





class SegTreeNode:



    def __init__(self, start: int, end: int):

        self.min = 0

        self.start = start

        self.end = end

        self.left = None

        self.right = None

        pass





def query(root: SegTreeNode, heights: List[int], start: int, end: int) -> int:



    # The range of current root is out of range

    if (root == None or end < root.start or start > root.end):

        return -1



    # The range of current root is in the range

    if (start <= root.start and end >= root.end):

        return root.min



    leftMin = query(root.left, heights, start, end)

    rightMin = query(root.right, heights, start, end)



    if leftMin == -1:

        return rightMin

    if rightMin == -1:

        return leftMin



    if heights[leftMin] < heights[rightMin]:

        return leftMin

    else:

        return rightMin





def calculateMax(heights: List[int], root: SegTreeNode, start: int, end: int) -> int:



    # Check if start is greater than end

    if (start > end):

        return -1



    # If there is only one element in the histogram

    if (start == end):

        return heights[start]



    minIndex = query(root, heights, start, end)

    leftMax = calculateMax(heights, root, start, minIndex - 1)

    rightMax = calculateMax(heights, root, minIndex + 1, end)

    minMax = heights[minIndex] * (end - start + 1)



    return max(max(leftMax, rightMax), minMax)





def buildSegmentTree(heights: List[int], start: int, end: int) -> SegTreeNode:



    if (start > end):

        return None



    # Creating a node for the current range

    root = SegTreeNode(start, end)



    if (start == end):

        root.min = start

        return root



    else:

        middle = (start + end) // 2



        # Creating recursive calls for left and right subtree

        root.left = buildSegmentTree(heights, start, middle)

        root.right = buildSegmentTree(heights, middle + 1, end)



        if heights[root.left.min] < heights[root.right.min]:

            root.min = root.left.min

        else:

            root.min = root.right.min

        return root





def largestRectangle(heights: List[int]) -> int:



    if len(heights) == 0:

        return 0



    # Build a segment tree

    root = buildSegmentTree(heights, 0, len(heights)-1)



    # Calculate the maximum area recursively

    return calculateMax(heights, root, 0, len(heights) - 1)

C++ (g++ 5.4)

/*

    Time Complexity = O(N*log(N))

    Space Complexity = O(N)

    

    Where N is the number of elements in the given array/list.

*/



// Segment Tree Class

class SegTreeNode 

{

    public:

    int start;

    int end;

    int min;

    SegTreeNode * left;

    SegTreeNode * right;



    SegTreeNode(int start, int end) 

    {

        this -> start = start;

        this -> end = end;

        left = right = NULL;

    }

};



int query(SegTreeNode *root, vector &heights, int start, int end) 

{ 

    // The range of current root is out of range

    if (root == NULL || end < root -> start || start > root -> end) 

      return -1;

    

    // The range of current root is in the range

    if (start <= root -> start && end >= root -> end) 

    {

        return root -> min;

    }

    

    int leftMin = query(root -> left, heights, start, end);

    int rightMin = query(root -> right, heights, start, end);

    

    if (leftMin == -1) 

      return rightMin;

    

    if (rightMin == -1) 

      return leftMin;

    

    return heights[leftMin] < heights[rightMin] ? leftMin : rightMin;

}



int calculateMax(vector &heights, SegTreeNode *root, int start, int end) 

{

  // Check if start is greater than end

    if (start > end) 

    {

        return -1;

    }

    

    // If there is only one element in the histogram

    if (start == end) 

    {

        return heights[start];

    }

    

    int minIndex = query(root, heights, start, end);

    int leftMax = calculateMax(heights, root, start, minIndex - 1);

    int rightMax = calculateMax(heights, root, minIndex + 1, end);

    int minMax = heights[minIndex] * (end - start + 1);

    

    return max(max(leftMax, rightMax), minMax);

}



SegTreeNode* buildSegmentTree(vector &heights, int start, int end) 

{

    if (start > end)

    { 

      return NULL;

    }

    

    // Creating a node for the current range

    SegTreeNode *root = new SegTreeNode(start, end);

    

    if (start == end) 

    {

        root -> min = start;

        return root;

    } 

    else 

    {

        int middle = (start + end) / 2;

        

        // Creating recursive calls for left and right subtree

        root -> left = buildSegmentTree(heights, start, middle);

        root -> right = buildSegmentTree(heights, middle + 1, end);

        root -> min = heights[root -> left -> min] < heights[root -> right -> min] ? root -> left -> min : root -> right -> min;

        

        return root;

    }

}



int largestRectangle(vector &heights) 

{

    if (heights.size() == 0)

        return 0;



    // Build a segment tree

    SegTreeNode *root = buildSegmentTree(heights, 0, heights.size() - 1);



    // Calculate the maximum area recursively

    return calculateMax(heights, root, 0, heights.size() - 1);

}

Accepted Answer

Stack Based Approach

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'.

Create an empty stack.
Start from the first histogram bar, and do the following for every bar ‘heights[i]’ where ‘I’ varies from 0 to ‘N’-1.

If the stack is empty or heights[i] is higher than the bar at top of the stack, then push ‘I’ to the stack.
If this bar is smaller than the top of the stack, then keep removing the top of the stack while the top of the stack is greater. Let the removed bar be heights[tp]. Calculate the area of the rectangle with heights[tp] as the smallest bar. For heights[tp], the ‘left index’ is the previous (previous to tp) item in the stack and the ‘RIGHT_INDEX' is ‘I’ (current index).
If the stack is not empty, then one by one remove all bars from the stack and do step 4 for every removed bar.

Space Complexity: O(n)Explanation:

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

Stack size can group up to the size of ‘N’, so the overall space complexity is O(N).

Time Complexity: O(n)Explanation:

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

Since every bar is pushed and popped only once, so the overall total time complexity will be O(N).

Java (SE 1.8)

/*

    Time Complexity = O(N)

    Space Complexity = O(N)



    Where N is the number of elements in the given array/list.

*/



import java.util.Stack;

import java.util.ArrayList;

import java.util.LinkedList;



public class Solution {

    public static int largestRectangle(ArrayList < Integer > heights) {



        int n = heights.size();



        /*

            The stack holds indexes of heights[] array. 

            The bars stored in stack are always in 

            increasing order of their heights.

        */

        Stack < Integer > s = new Stack < Integer > ();



        // Initialize max area.

        int maxArea = 0;



        // To store top of stack.

        int topOfStack;



        // To store area with top bar as the smallest bar.

        int areaWithTop;



        // Run through all bars of given histogram.

        int i = 0;



        while (i < n) {

            /* 

              If this bar is higher than 

              the bar on top stack, push it to stack.

            */

            if (s.isEmpty() || heights.get(s.peek()) <= heights.get(i)) {

                s.push(i++);

            }

            /* 

              If this bar is lower than top of stack, 

              then calculate area of rectangle with stack top.

            */

            else {

                topOfStack = s.peek();

                s.pop();



                /* 

                  Calculate the area with heights[topOfStack] 

                  stack as smallest bar.

                */

                if (s.isEmpty()) {

                    areaWithTop = heights.get(topOfStack) * i;

                } else {

                    areaWithTop = heights.get(topOfStack) * (i - s.peek() - 1);

                }



                // Update max area, if needed.

                if (maxArea < areaWithTop) {

                    maxArea = areaWithTop;

                }

            }

        }



        /*

            Now pop the remaining bars from stack and calculate 

            area with every popped bar as the smallest bar.

        */

        while (s.isEmpty() == false) {

            topOfStack = s.peek();

            s.pop();



            if (s.isEmpty()) {

                areaWithTop = heights.get(topOfStack) * i;

            } else {

                areaWithTop = heights.get(topOfStack) * (i - s.peek() - 1);

            }



            if (maxArea < areaWithTop) {

                maxArea = areaWithTop;

            }

        }



        return maxArea;

    }

}

C++ (g++ 5.4)

/*

    Time Complexity = O(N)

    Space Complexity = O(N)

    

    Where N is the number of elements in the given array/list.

*/



#include 



int largestRectangle(vector < int > & heights) {



    int n = heights.size();



    /* 

      The stack holds indexes of heights[] array.

      The bars stored in stack are always in 

      increasing order of their heights.

    */

    stack < int > s;



    // Initialize max area.

    int maxArea = 0;



    // To store top of stack.

    int topOfStack;



    // To store area with top bar as the smallest bar.

    int areaWithTop;



    // Run through all bars of given histogram.

    int i = 0;

    while (i < n) {

        /* 

            If this bar is higher than the bar on top stack, 

            push it to stack

        */

        if (s.empty() || heights[s.top()] <= heights[i]) {

            s.push(i++);

        }

        /* 

            If this bar is lower than top of stack, 

            then calculate area of rectangle with stack top.

        */

        else {

            topOfStack = s.top();

            s.pop();



            /*

                Calculate the area with heights[topOfStack] 

                stack as smallest bar.

            */

            if (s.empty()) {

                areaWithTop = heights[topOfStack] * i;

            } else {

                areaWithTop = heights[topOfStack] * (i - s.top() - 1);

            }



            // Update max area, if needed.

            if (maxArea < areaWithTop) {

                maxArea = areaWithTop;

            }

        }

    }



    /* 

      Now pop the remaining bars from stack and calculate

      area with every popped bar as the smallest bar.

    */

    while (s.empty() == false) {

        topOfStack = s.top();

        s.pop();



        if (s.empty()) {

            areaWithTop = heights[topOfStack] * i;

        } else {

            areaWithTop = heights[topOfStack] * (i - s.top() - 1);

        }



        if (maxArea < areaWithTop) {

            maxArea = areaWithTop;

        }

    }



    return maxArea;

}

Python (3.5)

'''

    Time Complexity = O(N)

    Space Complexity = O(N)

    

    Where N is the number of elements in the given array/list.

'''



def largestRectangle(heights):



    n = len(heights)



    ''' 

        The stack holds indexes of heights[] array. 

        The bars stored in stack are always in increasing 

        order of their heights.

    '''

    stack = list()



    # Initialize max area.

    maxArea = 0



    # To store top of stack.

    topOfStack = 0



    # To store area with top bar as the smallest bar.

    areaWithTop = 0



    # Run through all bars of given histogram.

    i = 0

    while i < n:

        ''' 

            If this bar is higher than the bar on top stack, 

            push it to stack.

        '''

        if len(stack) == 0 or (heights[stack[-1]] <= heights[i]):

            stack.append(i)

            i += 1

    

        else:

            topOfStack = stack.pop()



            ''' 

                Calculate the area with heights[topOfStack] 

                stack as smallest bar.

            '''

            if len(stack) == 0:

                areaWithTop = heights[topOfStack] * i

        

            else:

                areaWithTop = heights[topOfStack] * (i - stack[-1] - 1)

        



            # Update max area, if needed.

            if maxArea < areaWithTop:

                maxArea = areaWithTop

    

    ''' 

        Now pop the remaining bars from stack and 

        calculate area with every popped 

        bar as the smallest bar.

    '''

    while len(stack) != 0:

        topOfStack = stack.pop()



        if len(stack) == 0:

            areaWithTop = heights[topOfStack] * i

    

        else:

            areaWithTop = heights[topOfStack] * (i - stack[-1] - 1)



        if maxArea < areaWithTop:

            maxArea = areaWithTop

    



    return maxArea

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 :

Input format :

Output format :

Note :

Constraints :

Top Texas Instruments Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern