54. DLL-2

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 and firse temp2 chalao
and repeat this for all nodes being temp1 in an iteration
--------------------------------------------------
Optimal-
use 2 pointer
---------------------------------------------------------------------------------------------------------------

4. Remove duplicates from sorted DLL-

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





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