50. Stack-3: Monotonic

# Monotonic stack & queue invariant-
- for every element in a given array, you want to find, nearest element satisfying a condition

- Brute: for every element scan left & right side until you find 1st feasible answer

- Optimal:
--> Keep only those elements which are still useful for future
--> Do this by enforcing a monotonic order.
--> Hence, we store elements in stack, in a monotonic order

- Patterns:
1. nge
2. nse
3. pge
4. pse
---------------------------------------------------------------------------------------------------------------

1. Next Greater Element (nge)-I:

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

Brute- time: O(n^2)

using linear search for nge of every element

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

Optimal- time: O(n)

At every element, I want order of increasing elements, to its right
Hence, we store elements in increasing order from top to bottom of stack

1. traverse from right to left
2. if stack is empty push current element into stack
3. else, if stack is filled & st.top > curr => st.top is ans
4. else, if stack is filled & st.top < curr => pop out elements from stack till you meet cond-3

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

2. Next Greater Element (nge)-II:

Find nge for every element, if array is circular
--------------------------------------------------------------

Brute- time: O(n^2)

using two loops to take fwd elements & then backward elements for any element

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

Better- time: O(n^2)

to take both fwd & backward elements, we take j from i+1 to i+(n-1) & do (j%n)

-------------------------------------------------------------
Optimal- time: O(n)⭐

in normal nge code

- start i from (2n-1) instead of (n-1) & do (idx = i%n)

- only update the answer array for elements with ind < n

- till then this helps us to build the required stack for the circular array

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

3. Count NGEs to the right:

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

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

             for pge, only >, < wali condition badlegi

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

4. Find Previous Smaller element: (pse)

since for every element we care only about elements smaller than current element and to its left. Hence, we store elements inside stack in the decreasing order from top to bottom

Also, we will prefer traversing from left to right

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

5. Trapping Rainwater

Brute- time: O(n^2)  space: O(1)

For every index i, we find left max and right max and then calculate,
height of water that can be stored at (i) as :
min(LeftMax, RightMax) - height

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

max left height at any index i = max height at (i-1) or height at index i

---------------------------------------------------------------
Optimal- time: O(n)  space: O(1)    ⭐

( 2 pointers )
instead of using 2 arrays, we realise that at every index i, we just need best height to its left & best height to its right

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

6. Sum of Subarray Minimums-I

Brute- time: O(n^2)      space: O(1)

generate all subarrays & do the stuff
------------------------------------------------------
Optimal- time: O(n)  space: O(n) ⭐

Contribution technique
(to optimise subarray problem)

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

contribution of each element in reqd sum = (currElmt * count)

where, count =  (i-pseIdx) * (nseIdx-i)

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

Important-⭐

1. make initial values of (pse to -1) & (nse to n)  
2. to avoid duplicate case , we take = sign in one out of pse or nse. e.g., here we do:

in pse: nums[st.top()] >= nums[i] 
in nse: nums[st.top()] > nums[i] 

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

7. Asteroid Collision

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

8. Sum of Subarray Ranges

Brute- time: O(n^2) 

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

Optimal- time: O(n)

just be careful of putting default values of nge, nse to -1 and pge, pse to n
also of taking equality only in one out of pse, nse and similarly for pge,nge

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

9. Remove k digits from given number &
return smallest possible number🔥

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

To get the smallest number,
the digits should be in increasing order from left to right.
So if a digit is bigger than the next digit, then it is blocking a smaller number → remove it.
--------------
push elements into stack, while iterating from 0 to n-1

if ( st.top < curr) => we cannot pop => push d into stack

while ( st.top > curr ) => we can put curr in-place of st.top as a smaller digit => pop st.top

---------------------------------------
Edge case-

if (k!=0 after whole traversal), then it means number was increasing e.g., "123456" & k=2
hence, we remove last remaining k digits from number in this case
( so, pop out remaining elements from stack's top )

do this before ans

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

10. Largest Rectangle area in histogram-

Brute- time: O(n^2)

For each bar , we find smallest bar on left and right of it and calculate area

-----------------------------------------------------------
Better- time: O(n) 

(2 pass soln)
for each rectangle, find nseIdx & pseIdx & calculate, A = H*(nse-pse-1)
ans  = max A

---------------------------------------------------------
Optimal- Extra⭐
(1 pass solution)

we will do computation only for pse 

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

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

in pse, popping means ( curr < st.top() ) , so in a way we got nse of st.top()
hence we 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= n) & (pse= -1)

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

11. Maximal Rectangle-⭐

Ques- In a binary matrix, find area of maximal rectangle having all 1s in it
---------------------------------------------------
Approach-
for each row, form make histogram of 1s
and find area (A) of largest rectangle in this row's histogram 
ans =  max of all areas (A)

Thus, for each row, we have a set of heights
So question reduces to passing R queries to largest rectangle in histogram problem
--------------------------------------------------

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 matrix

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