c++

3. Flatten LL✅ 4. Clone LL with random pointer & next pointer✅ --------------------------------------------------------------------------------------------------------------- 1. Reverse in groups of size K⭐ Do not alter node's values, instead only change links ---------------------------- Approach - Check if k nodes exist & reverse one group at a time ----------------------------------------------------------------------------------------------------------------------------- 2. Rotate a LL Brute - time: O(n)   space:O(n) store all elements in an array & then rotate the array & then over write the LL with this rotated array elements -------------- Better - time: O(nk)  space: O(1) do this k times- remove last node and add it to the front before this do (k = k % n) so we can reduce extra iterations ---------------- Optimal - time: O(n)  space: O(1) just change link of (n-k)th node and point it to null the nodes from (n-k+1)th node to the last ...

1. reverse DLL 2. delete given element occurrences in dll 3. find pairs with given sum in sorted dll 4. remove duplicates from sorted dll --------------------------------------------------------------------------------------------------------------- 1. Reverse a DLL- Brute- use stack and do data over write Better- use start and end pointer and swap values doing (start  = start-->next) & (end = end-->prev) Optimal- ⭐⭐ changing links instead of over writing data  --------------------------------------------------------------------------------------------------------------- 2. Delete all occurrences of key in DLL- ------------------------------------------------------------------------------------------------------------ 3. Find pairs with given sum in sorted DLL- Brute - (similar to brute force of subarray traversal ) temp1 rakho start pe aur temp2 ko tab tak traverse karao from start+1 till jaha tak  temp2 + temp1 <= k fir temp1 ko start+1 pe rakho and firse t...

# Representation:- ----------------------------------------------------------------------------------------------------------------------------- # Converting array to doubly LL:- ---------------------------------------------------------------------------------------------------------------------------- # Deletions in DLL:- 1. Deleting head- 2. deleting tail- 3. deleting Kth node-⭐⭐ 4. Delete given node- ---------------------------------------------------------------------------------------------------------------------------- # Insertions in DLL:- 1. before head- 2. before tail- 3. before Kth node- 4. before given node- -----------------------------------------------------------------------------------------------------------------------------

1. Add 2 LL Brute - 1. use a variable to store number represented by LL-1 (e.g., 3-->5 means 53) 2. use another variable to store number represented by LL-2 3. add these 2 variables and store in third variable 4. create a new LL using this third variable --------------------------------------------- Optimal - using concept of Dummy node 1. start a new LL using dummy node 2. traverse both LL simultaneously using 2 pointers and add elements along with carry at each iteration 3. if sum<9 => good, else set new node to 0 with carry being 1 4. repeat till end 5. if carry remains at end, add 1 to the end of new LL --------------------------------------------------------------------------------------------------------------- 2. POI of 2 LL Brute- time: O(n)   space: O(n) Using hashing 1. traverse one LL and hash the nodes 2. Now, when u traverse the other LL, the first visited node you visit is poi -------------------------------------------------- Better-  time: O(n)...

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 ...