50. Stack-3: Monotonic

Monotonic stack- when we store elements in a specific order in stack

--------------------------------------------------------------------------------------------------------------

1. Next Greater Element (nge)-1:

Brute Force-O(n2)

Optimal-O(2n)
intuition : at every element i want order of increasing elements to its right

Traverse from the back & fill map using stack
for answer array now do a front traversal and store answers using map

we are storing elements in decreasing order from bottom to top of stack

-----------------------------------------------------------------------------------------------------------------------------

2. Next Greater Element (nge)-2:

Ques- find nge for every element, given that array is circular
------------------------------------------------------------------

Brute force- 

------------------------------------------------------------------

Better-O(n2)
use concept of circular array:

(hypothetically double the array) by doing (i%n) instead of i & for each element just see first n elements forward

-------------------------------------------------------------------
Optimal-O(n)
do normal nge but start from (i  = 2n-1) instead of (n-1) & (ind = i%n)

only update the answer array for elements with ind < n

-----------------------------------------------------------------------------------------------------------------------------

3. number of nges to the right:

time: O(q*n)

---------------------------------------------------------------------------------------------------------------------------

NOTE- for nse, only >, < wali condition badlegi

             for pge, only >, < wali condition badlegi

---------------------------------------------------------------------------------------------------------------------------

4. (pse) Prev Smaller element:

kyuki mujhe har element pe uske piche walo mein curr se chota element dekhna hai toh main stack mein curr se piche ke elements ko st.top se bottom tak decreasing mein lagaunga

---------------------------------------------------------------------------------------------------------------------------

5. Trapping rainwater-1

Brute-                                           time: O(n)  space: O(n)

intuition- water will be stored only when there is a taller building to left & right of curr building

             - for every building height of water stored above it = curr height - min(leftMax, rightMax)

             - we will build prefixMax & suffixMax helper arrays

--------------------------------------------------------------------------
Optimal- O(1) space:    2 pointer⭐

instead of calculating all the left max & right max, for each element we just need min of these 2 not both

---------------------------------------------------------------------------------------------------------------------------

6. sum of subarray minimums-1

Brute Force- generate all subarrays & do the stuff

Optimal⭐- instead of generating all subarrays and finding min in all, we can find how much does each element of array contribute in final answer

contribution of each element can be found using nse and pse of that element

so for each element we need index of pse & nse 

contribution of curr element = currElement* [ (currIdx-pseIdx)*(nseIdx-currIdx) ]

------------------------------------------------

EDGE CASES handling-⭐⭐

make initial values of nse to n & for pse to -1,

make nse ko strictly ki jagah normal 

---------------------------------------------------------------------------------------------------------------

7. Asteroid collision

---------------------------------------------------------------------------------------------------------------

8. Sum of subarray ranges

Brute force-

Optimal-

--------------------------------------------------------------------------------------------------------------

9. Remove k digits⭐⭐

push elements into stack, while iterating from 0 to n-1

if, st.top < curr => we cannot pop out st.top since number will become larger if we pushed curr at place of st.top => push curr into stack & do no pop

if, while( st.top > curr ) => we can put curr in-place of st.top as curr is a smaller digit => pop st.top & when current condition starts to fail then push curr

-------------------------------------------------------
Edge cases🤯🔥-

1. if (k==n), return 0

2. if (k!=0 after whole traversal), then pop out remaining elements from stack's top
3. if final answer has leading zeros remove it
4. if final answer is empty string return "0"

---------------------------------------------------------------------------------------------------------------

10. Largest Rectangle area in histogram-

BRUTE- (2 pass soln)
for each rectangle, find nseIdx & pseIdx & calculate area = height*(nse-pse-1)

ans  = largest area

----------------------------------------
OPTIMAL- (1 pass solution)⭐⭐

we will do computation only for pse 

and during that traversal only we will try to get nse smartly

in pse, for popping condition, if u r popping means, curr < st.top() , so in a way we got nse of st.top() and hence we can calculate area of st.top() before popping it out

if, curr < st.top(), then pop it & find area = (el popped)*(nse-pse-1)    

where, nse=curr , pse=new st.top()

else, push curr into stack    

when i>n-1, then find areas for remaining bars in stack with nse = n & pse = prev

& for last element in stack nse being at n and pse at -1

---------------------------------------------------------------------------------------------------------------

11. Maximal Rectangle-

for each row, we will find max area out of all histogram of 1s from this row to top row
ans =  max of all areas u got

to find height of a bar for an element of current row, we will use prefix sum matrix which can be created by iterating column wise over the given matri

----------------------------------------------------------------------------------------------------------------------------