36. Largest rectangle in Histogram

36. Largest rectangle in Histogram

Problem link :- click here

package programs;

import java.util.*;

public class Array__36
{

	/*
	    If we solve this problem manually we may observe that, every maximum rectangle
	    		has at least one element which is fully involved in that rectangle
	    So the approach is we will find the maximum rectangle that can be formed
	    		involving each element fully
	    		and we will take the maximum of these values
	    		
	    The HEIGHT largest rectangle involving an element fully will be the VALUE of that element
	    		so we need width to find the area
	    Width ---> we need to know up-to how much element it is spread
	    			that rectangle can occupy all the consecutive elements who's height >= element's height
	    			so it stop occupying if it finds an element of height < element's height
	    
	    So lets use some data structures to do our work
	    		arrays --> lets take 2 arrays to store the INDICES of left-most and right-most element that 
	    				  is occupied in the rectangle ( width = right-most[i] - left-most[i] )
	    		Stack  --> We need a stack to find the left-most and right-most
	    
	    FINDING LEFT_MOST
	    		left-most[ 0 ]  will be '0' itself because there is no other element to its left
	    		we will push '0'(index of first element) to the stack 
	    			1) while iterating we will check if ( height[stack.peek()] >= height[i]  )
	    				*) then the rectangle involves    stack.peek()   element so pop that 
	    				*) do this until you find an element of height < height[i]
	    			2) while loop fails if stack becomes empty
	    							then left-most[i] = 0  (no element of height < height[i] )
	    					or if     height[ stack.peek() ] < height[i]
	    							then left-most[i] = stack.peek() -1
	    			 3)push 'i'
	    				(while finding the left-most of next element if it involves 'i' 
	    				then it will automatically involves the element that we pop till now)
	    
	    similarly find the right-most starting from last element 
	*/
	
	static int largestRectangle(int height[], int n)
	{
		Stack<Integer>  my_stack = new Stack<>();
		
		int left[] = new int[n];
		int right[] = new int[n];
		
		//Initializing left array
		left[0] = 0;
		my_stack.push(0);
		for(int i=0; i<n; i++)
		{
			while( !my_stack.empty()  &&   height[my_stack.peek()] >= height[i] )
				my_stack.pop();
			if( my_stack.empty() )
				left[i] = 0;
			else if(  height[my_stack.peek()] <  height[i] )
				left[i] = my_stack.peek()+1;
			
			my_stack.push(i);
		}
		
		//clear the stack before using it for initialization of right array
		while( !my_stack.empty() )
			my_stack.pop();
		
		//initializing the right array
		right[n-1] = n-1;
		my_stack.push(n-1);
		for(int i=n-1; i>=0; i--)
		{
			while( !my_stack.empty()   &&   height[my_stack.peek()] >= height[i])
				my_stack.pop();
			if( my_stack.empty() )
				right[i] = n-1;
			else
				right[i] = my_stack.peek()-1;
			
			my_stack.push(i);
		}
		
		//finding the maximum rectangle
		int max_area = 0;
		for(int i=0; i<n; i++)
		{
			int area = height[i] * (right[i] - left[i] + 1);
			max_area = Math.max(max_area, area);
		}
		
		return max_area;
	}
	
	public static void main(String[] args)
	{
		int i, n;
		
		Scanner s = new Scanner(System.in);
		System.out.print("Enter the size of the  array : ");
		n = s.nextInt();
		int array[] = new int[n];
		System.out.println("Enter the elements of the array : ");
		for(i=0; i<n; i++)
			array[i] = s.nextInt();
		System.out.println("Given array : ");
		printArray(array);

		int ans = largestRectangle(array, n);
		System.out.println("\n\nMaximum area is : " + ans);
	}

	static void printArray(int arr[])
	{
		for(int i=0; i<arr.length; i++)
			System.out.print(arr[i] + " ");
	}
}

Time complexity :- O(n)
Space complexity :- O(n)