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. Sliding window maximum⭐⭐

return max element from each of the k-sized sliding window
----------------------------------------------------
Brute- time: O(nk)

For each window, scan k elements and take max
--------------------------------------------------------
Optimal- time: O(n)

we need to do below operations as required :
- get max element in a window in O(1)
- delete last element & add new at the same time in O(1)
- traverse in O(n)
--------
So, we maintain a DEQUE storing indices, elements in monotonic decreasing order (from bottom to top) because if a new element is bigger than the previous one , then all previous ones can't be maximum ones in future...
---------
if ( st.size()<k ) :-

1. while ( st.top() < curr ) => remove top
2. if ( st.top() > curr ,or st.empty() ) =>  push curr at top
3. store st.front() 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-

a[i][j] = 1, means ith person knows jth person
Return index of celebrity ( known by all & knows none )
-----------------------------------------------------------
Brute- time: O(n^2)  space: O(n)

Celebrity is the person who is known by exactly n-1 people & he knows 0 people 

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

Using Stack

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

Single Pass (optimised stack soln)

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

Comments

Post a Comment

Popular posts from this blog

30.) DP on subsequences

Image
Subset sum = target✅⭐ Partition equal subset sum✅ Partition array into 2 subsets with min abs [sum(v1)-sum(v2) ]✅ Count subsets with sum k✅⭐ Count partitions with given diff✅ target sum✅ 0/1 knapsack✅⭐ min coins✅---->count min coins to be taken coin change-2--->count n(ways) of taking coins⭐✅ unbounded knapsack✅ rod cutting problem✅ ----------------------------------------------------------------------------------------------------------------------------- 2 ways to generate all subsequences- Power Set, or Recursion subset means subsequence in dsa ----------------------------------------------------------------------------------------------------------------------------- 1. Target Sum- QUES- return true if there exists a subset with sum equal to the target in the array... Soln assuming all array elements are positive  here f(n-1,target) will tell if there's a subsequence till n-1 index with sum = target 1.) RECURSIVE SOLN-        ( time: 2^n    ...
Read more

36. Graphs-2 (traversal problems)

Image
1. No. of provinces Count total components in a graph, using any traversal technique ----------------------------------------------------------------------------------------------------------------------------- 2. Rotten oranges⭐     Multi source BFS time: O(n*m)   space: O(n*m) -------------- - count all fresh at start and then count if these many will rot in the process or not - here we do not need a visited matrix since we can modify given - we update time each time there rots atleast one orange in a BFS cycle --------------------------------------------------------------------------------------------------------------------------- 3. No. of Islands Count no. of islands (land surrounded by water in 4 directions) ---------------------------------------------------- time: O(n^2)  space: O(n^2) No. of islands = no. of graph components ----------------------------------------------------------------------------------------------------------------------------- 4. ...
Read more

35. Graphs-1 (basics)

Image
# Note -  1. it has nodes/vertices (N) connected by edges (E) 2. d egree(N)  = n(edges) connected to a node 3. in-degree(N) = no. of in-going edges  4. out-degree(N) = no. of out-going edges  5.  Total degree of undirected graph = (2*E) 6.  DAG - directed acyclic graph 7.  Path -  a sequence of nodes where all  adj nodes have a direct edge b/w them -------------------------------------------------------------------------------------------------------------------------- 1. Representation- 1. Adjacency Matrix:  space: O(n^2) store info about presence of edges between 2 nodes -------------------------------------------------------- 2. Adjacency list:   space: O(n) - store info about adjacent neighbours of a node - for unweighted graph instead of a pair we will store them as integer array ----------------------------------------------------------------------------------------------------------------------------- 2. BFS- time: O(N+...
Read more