51. Stack-4: implementation

 1. Stock Span Problem-

for a stream of data we have to tell no. of elements before curr which are <= curr , including curr.

Method-1: storing price, span in stack

Method-2: storing price, index in stack


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

 2. max element from each k-sized sliding window-⭐
(Google)

Brute force-

--------------------------------
Optimal-
to reduce quadratic time complexity to linear, we need to get max element in a window & be able to delete last element and add new at the same time, so we must use a data structure to do so, we linear time is only consumed while traversing & not in any operation.

So, we need a deque- 

we will store elements in monotonic decreasing order (starting from bottom to top of dequeue)

SUMMARY-

1. pehle first window se deque bhardo
2. ab har next element k liye is element ki window ke alawa faaltu elements hatado
3. aur har window mein <= wali condition ke according pop push ka dekhlo

-------------------------------------
if ( st.size()<k ) :-
1. while, [ curr > st.Top() ] => st.popTop()
2. if, [ curr < st.Top()  or st.empty() ] =>   st.pushTop(curr)
store st.front()  (largest of that window) in ans vector after every element analysis

when you are at an element & window is already full => pop out element from bottom & do above stuff
---------------------------------------

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

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

3. Celebrity Problem-(not stack ques)

------------------------------------------------------------------
Brute Force-
--------------------------------------------------------------
Optimal- Use 2 pointer at 0 and n-1
if idx1 knows idx2 then idx1 can't be celebrity
using this concept we move pointers from top and bottom row & reach final row 
to confirm if this row is our answer we can check its row & its corresponding column

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

4. LRU cache-



















Comments

Post a Comment

Popular posts from this blog

18. greedy algorithm

Image
assign greedily  like sabse kam distribute kro starting mein bade number last k liye bacha k rakho we use 2 pointer here ---------------------------------------------------------------------------------------------------------------------------- if smj ni aara ki konsa stl use kru, u can even solve ques with few varibles also. ----------------------------------------------------------------------------------------------------------------------------- Shortest Job First Problem Jump game 1 Jump game 2 Job Sequencing problem N Meetings in a room Insert Intervals Min platforms Valid parenthesis Candy Fractional Knapsack ------------------------------------------------------------------------------------------------------------------------ Shortest Job First Problem- --------------------------------------------------------------------------------------------------------------------------- JUMP GAME-1 --------------------------------------------------------------------------------------...
Read more

19. strings (LB)

Image
strings are 1d character array. e.g., char ch[10]; cin>>ch; string ends with '\0' cin with string works only if till space, tab or new line is absent in input... ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- STRING- dynamic size no null termination in built functions --------------------------------------------------- ------------------------------------------------------------------------- --------...
Read more

17. BINARY SEARCH on 2d arrrays

Image
 1.)   ROW WITH MAX 1s- given each row is sorted. BRUTE - simple 2 loops OPTIMAL - binary search lagalo to find index of 1st occurence of 1 in a row -------------------------------------------------------------------------------------------------------------- 2.) Search in 2d Matrix-(sorted rows consecutive) BRUTE - use 2 loops BETTER - check for only that row jisme target is between a[i][0] and a[i][c-1]  OPTIMAL - 2d array ko hypothetically 1d me karke binary search lagalo --------------------------------------------------------------------------------------------------------------- 3.) Search in matrix(sorted row and col but not consecutive) BETTER- use binary search for every row OPTIMAL -(time: N+M) --------------------------------------------------------------------------------------------------------------- 4.) Peak elements in matrix- BRUTE- 1.) we can do linear search and for each element compare with its 4 neighbours 2.) Or, we can find max element in matrix BET...
Read more