Posts

Sub-arrays

Image
  1.  Find maximum sum of a subarray Brute - time: O(n^2) go through each subarray and thus find the maximum sum --------------------- Optimal - time: O(n) use Kadane Algorithm at each element either extend old subarray or start a new one. Handles negatives as well as positives ----------------------------------------------------------------------------------------------------------------------------- 2. Find maximum sum of subarray of size K only positives - use sliding window of fix size K, and move both pointers simultaneously thus simulating fix window traversing array   ----------------------------------------------------------------------------------------------------------------------------- 3. Find maximum sum of distinct subarray of size K Brute -  time: O(nK)    space: O(n) Use hashing , after each expansion and shrinking of sub array, check if this subarray contains duplicates or not. ----------------------------- Optimal - time: O(n)  ...
Post a Comment
Read more

55. LL- hard

Image
1. Flatten LL✅ 2. Rotate LL✅ 3. reverse LL in groups of size K✅ 4. Clone LL with random pointer & next pointer✅ 5. Design Browser History✅ 6. LRU cache✅ 7. LFU cachešŸ”„✅ ----------------------------------------------------------------------------------------------------------------------------- 1. Reverse in groups of K step-1: put temp at head step-2: figure out kth node step-3: point kth node's next to null but before it preserve the next node step-4: reverse this group of LL step-5: do , head = kth node & prvNode = temp  step-6: do, temp = next node (which we preserved in step 3)  step-7: repeat from step 2 step-8: if for a group there are < k elements, then attach all elements of such group starting from temp to the previous node. ----------------------------------------------------------------------------------------------------------------------------- 2. Rotate a LL -----------------------------------------------------------------------------------------------...
Post a Comment
Read more

54. DLL-2

Image
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 5.  --------------------------------------------------------------------------------------------------------------- 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 an...
Post a Comment
Read more

53: Doubly Linked List-1

Image
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- -----------------------------------------------------------------------------------------------------------------------------
Post a Comment
Read more