JB TAK FODEGA NHI .... TB TK CHODEGA NHI .... (MAANG)

SQP11 Largest Rectangle in Histogram

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Example 1:
Input:heights = [2,1,5,6,2,3]
Output: 10

Explanation:
The above is a histogram where width of each bar is 1. The largest rectangle is shown in the red area, which has an area = 10 units.
Constraints:
- 1 <= heights.length <= 10^5
- 0 <= heights[i] <= 10^4

Notes

Note: Zoom for Better Understanding

Brute Force Approach

Intuition: The intuition behind the approach is taking different bars and finding the maximum width possible using the bar.

Always try to Strat your Interview with the Brute Force Approach and then go with the Optimal Solution

first we find out the Seperately Area for every partation Rectangular Box that are consitive for the left to right hand side

All Areas

Box 2: 2 cover only one box next box is < then 2 so my max Area is Area = 2*1 = 2

Box 1: 1 cover all the rectangular box becouse 1 is the smallest unit inthis Histograme Area = 1 * 6 = 6

Box 5: 5 cover only two box so my max Area is Area = 2 * 5 = 10 (Max)

Box 6: 6 cover only one box so my max Area is Area = 6 * 1 = 6

Box 2: 2 cover only 4 box so my max Area is Area = 2 * 4 = 8

Box 3: 3 cover only one box so my max Area is Area = 3 * 1 = 3

Now the Question is How to find out the Left and Right all the Rectangualar box that Comes under the particular Rectangular box

Assume that we are Standing on the Box = 2, Index = 4 finding the all box that are comes under tha Range

For Left Hand Side: finding the first block that is < to the block 2

For Right Hand Side: finding the first block that is < to the block 2

Formula: last Index and first Index of the first Smaller box for the particular box + 1

count = LastIndex-FirstIndex + 1
ans = count * arr[i]

Example:
Box = 2
firstIndex = 2
lastIndex = 5

count = 5-2 + 1
ans = 4 * 2
ans = 8

Code Zone!

Before Loking the Code...
Try by Your Self ...

BruteForce Python Code

BruteForce C++ Code

BruteForce Java Code

Sb Mai He Kru ...

Khud Bhi Kr le Khuch ..... Nalayk

Time Complexity:O(N*N) Nexted Iteration for the left and Rigth Index Finding and calculate the max Area
Space Complexity:O(1) Constant Space.

Optimized Approch

During the BruteForce Approch we finding the formula for finding the left and right index thatt is (LastIndex-FirstIndex) * arr[i] + 1

So how can i Finding the Right Smaller and Left Smaller Index

Now here we used the Concept that we learned the Prevesoly that if Next Grtaest Element on the Basis on these Concept

Next Smallest Element
Prevesoly Smaller Element

we creating the left small Index and rigth small Index array with the Size of the Rectangular box

Maintain the Stack data Structure for the Carring the Index of the Rectanglar Box

Let's Understand

Inilisized the array with the empty stack and start iteation from -> side

Steps

if stack is empty then put the that particular Index into the leftarray and also put the Index into the Stack

Check if any element that if >= to the arr[i] then removed all the element Index from the Stack and put the last Index that is < then arr[i] into the leftarray

check if not any element >= present into the stack then in tis case stack.top()+1 index put ito the leftarray and put index into the stack

if stack become empty() that means put the 0 into the leftIndex array

Similler way to find out the rigthArray Index <- only direction is changed and remaing things are same

After finding the left adn rigtth small Index we iterate linearly and appy the formula that we find out (LastIndex-FirstIndex) * arr[i] + 1

Optimized Python Code

BruteForce C++ Code

Optimized Java Code

Sb Mai He Kru ...

Khud Bhi Kr le Khuch ..... Nalayk

Time Complexity:O(N) + O(N) + O(N) ~ O(N) for left array, for rigtth array and finding the Maximum ans
Space Complexity:O(N) + O(N) + O(N) ~ O(N) for left array, for rigtth array and Stack

Most Optimized Approch

As our Prevesoly approch we sued the formula that is (LastIndex-FirstIndex) * arr[i] + 1 that take 2 passes

one for the leftSmall Index

and one for the rightSmall Index

Now in this Approch our task is Convert 2 Passes into the 1 Pass

Thought Process

Prevesoly we learned to finding the hole left and rigtth Index and store that Index into the stack

in this approch we not finding the hole left and rigth array we finding the Area as well as that is my Intuation

Dry Run inthe Notes Please Checkout the Notes and try to Dry run and understand the Concept

Most Optimized Python Code

Most Optimized C++ Code

Most Optimized Java Code

Sb Mai He Kru ...

Khud Bhi Kr le Khuch ..... Nalayk

Time Complexity:O(N) + O(N) forf Linear Iteration and Maintain the Stack [ Every time we not Removed the Every element from the stack ]
Space Complexity:O(N) Only for the Stack No need to required another data structure.

Interview Docs File "All the Best" Team @DSAwithPrinceSingh

~ It's All About Consistency📈 Dedication🎯 HardWork💪 Happy Coding❤️ ~