52. Linked-List: (LL medium-2)

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)  space: O(1)

1. move pointer of Longer LL till it reaches starting posn of shorter LL
2. Then we start simultaneous traversal of both

---------------------------------------------------
Optimal-⭐

1. Move both ptrs starting from the respective heads of 2 LLs.
2. Whenever a ptr reaches last node, reset that ptr to head of other linked list & continue traversal of both pointers
3. Repeat
4. At a point, both ptrs will be vertically aligned, so then they would simultaneously reach common poi

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

3. Merge 2 sorted LL

Brute - time: O(nlogn)    space: O(n)

1. store all elements in a vector
2. sort them
3. convert this array into a LL
-------------

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

using 2 pointers (merge step of merge sort algorithm)

use a dummy node to start new LL

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

4. Merge K sorted LL

Brute- time: O(NlogN) space: O(n),  where n = total elements

1. store all elements in an array
2. sort array
3. convert array to a new LL
----------------------------------------------
Better- time: O(N*k)   space: O(1)

repeatedly do merge 2 sorted LL in pairs of 2 over all k LL's

---------------------------------------------
Optimal- time: O(N*logK)⭐  space: O(k)

use min-heap

1. store all heads in a priority queue as {val, node}
2. create a dummy node as start point for final answer LL

3. Append min value node (out of pq) to dummy-->next
4. pop this node from pq & add its .next to pq at the same time
5. repeat 


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

5. Sort a LL

Brute- time: O(nlogn)       space: O(n)

store all elements in a vector => sort them => over write the LL
------------------------------
Optimal- time: O(nlogn)    space: O(1) 

Merge Sort

1. find middle 
2. left LL start from head & right LL start from (middle-->next)
3. separate the 2 LL (left LL is from head to mid, so update mid so it points to NULL) and call merge sort again, recursively for these 2 LL
4. merge these 2 sorted LL

Edge case- ⭐⭐
- Tortoise hare algo returns 2nd middle in case of even length LL, but we want 1st middle in even length LL for split, so modify that algo
- so we will start fast from (head--->next) instead of head, in even length LL
--------------------------------------------------------------------------------------------------------------

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 (grid/traversal problems)

Image
 PROBLEMS ON BFS/ DFS:- no. of provinces          ✅ components rotten oranges            ⭐✅ multi source BFS no. of islands              ✅ BFS/ DFS flood fill                     ✅ BFS/ DFS no. of enclaves           ⭐✅ multi source   BFS/DFS no. of distinct islands ⭐✅ shape storing   BFS/ DFS surrounded regions    ✅ multi source   BFS/DFS 0/1 Matrix                  ⭐⭐✅ multi source BFS word ladder-1 , 2 ---------------------------------------------------------------------------------------------------------------------------- 1. No. of provinces Count total components in a graph time- O(N + V+2E)               space: O(N) --------------------------------------------------------------------------------...
Read more

19. Strings (LB)

Image
Character Array- 1. We use  1d character array  to simulate strings, e.g., char ch[10]; cin>>ch; 2. string ends with '\0' 3. cin with string works only if till space, tab or new line is absent in input... 4. work with character array just like a normal array, here only datatype is changed to char, else wise it is just an array -------------------------------------------- 5. In-Built functions- - int n = strlen(ch)   - strcmp(s1,s2)            // gives 0 if both strings are equal  - strcpy(dest,source)   // copies a string from dest to source -------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- STRING- It is a C++ STL 1. has dynamic size (can dynamically increase size when needed) 2. null terminator (\0) NOT required 3. Has built-in functions : - return s.size() - return s == "hello" - return s + "wor...
Read more