🧩 TUF_coding_series_revision.txt

1. Inversion Count/ Reverse Pair ( both similar question )
- Basically we need to reduce complexity from O(N^2) to O(NlogN)
- And things could be little better we have have 2 sorted array where we can check the requirement
- And merge sort we have these arrays and hence we can easlily check it there
- 🌟 In Reverse Pair, the method where we check is important as that logic is little tricky yet easy!

2. Unique Path Problem (Google Interview)
- Use recursion for (2^N)
- Use DP for O(N^2)
- Use Optimised space in tabular
- 🌟 Use combinations - O(N) -> RRD, RDR...

3. Dutch National Flag Algorithm/ Sort colors/ Sort 0, 1, 2
- In a single pass it's required to be done, with constant space
- DNF says take 3 ptr - low, mid, high
- Low's left contains 0, high's right will contain 2
- swap mid[i] with left if 0, if 2-swap with high
- move ptr accordingly!

4. Linked List Cycle II 
- Important to understand algorithm (If not known cant do the question)
- Important to understand how the same algo can work for 'Duplicate Element Question'
- 2 things are stated in algo 1) if there is cycle 2) start point of cycle
- After finding merger of fast and slow, just take another slow from head & keep moving 1 step (merger will be start of cycle)

5. Maximum Product Subarray
- Important to understand that array can have both -ve and 0
- Logic is to carry smallest and largest number possible everytimes
- So that if other - comes we can change that lowest to bigest or bigest to lowest(so it can become largest later when - comes again)
- Understand recursive approach in order to understand iterative(exactly same as recursion)

6. Find Duplicate Number in 1+N, numbered from 1-N
- clearly all items will be pointing inside the array itself
- Hence we can go for floyds algo to check the starting of cycle
- The starting of cycle will signify the repeating number as more than 1 will be pointing to it.
- Same we can't implement in problem (7) as index may be out of array index

7. Find Missing/ Repeating Number (Given num from 1-n, one is missed and one is repeated)
- Can't use floyd's cycle as obviously one number may be pointing more than (n-1)
- Better way is to use algebra | Sum of 1 to N - > N* (N+1) / 2 | Find sum of given nums
- Find sum of sq. N * (N+1) * (2 N + 1) / 6  | Find sq of sum of given num
 x y z = A
 x y y = B
 ----------
 z - y = A - B
 ----------

 x2 + y2 + z2 = M
 x2 + y2 + y2 = N
 -------------
 z2 - y2 = M - N 
 OR
 (z+y) (z-y) = M-N
 OR
 z+y = (M-N)/(z-y)
 -------------
- We have both z-y & z+y both repeating(y) and missing(z) which can be found now

8. Russian doll Envelopes
- Clearly DP problem can be done using memoization - O(N^2)
- BUT! For large input O(N^2) will give TLE, hence use this trick to solve it
- Sort the width and now we can apply LIS to the height
- * Make sure to reverse sort the height when width is same (so we don't pick the same width)

9. Merge without extra space
- Q) [...],  [....] both are sorted and sort as if both were one
- ⭐️ Check first of 2nd and last of first ( and swap if 2nd has smaller item that last of 1st )
- Simple reason because we know 1st array will contain all smaller of both array's
- Now keep shifting index and keep swapping until not required, then sort both array

10. Set Matrix Zero (complete row/column turns 0 if item is 0)
- Q is easy if extra space allowed, as we can 2 vector - row/column representing row/column and turn 0 where required
- Same thing we can do if we treat first row/column as that extra vector
- Here it's just that we need to turn complete first row/column to zero at last when everything else is done
- For that we will need some flags to know if at last we need to convert 1st row/column to 0

11. Pascals Triangle
- Along with simple way of finding all rows in Pascals triangle
- We can make use of " nCr" to find nth row and rth column item in O(1)
- Also to find nth row complete, we see the simple patter of nCr, nCr+1, nCr+2...
- Which is basically multiplication to previous item & can be done in O(N)

12. Next Permutation
- Important to understand that 1,2,4,3 -> next permute is 1,3,2,4 and not 1,3,4,2
- First we are finding the index where value decreased as compared to it's next one
- This is the ind which can be replaced with any of the num from right, but which one?
- The one which is greater but closest to ind, Make sure to sort as values after swapping to the ind may not be ascending!

13. Inversion Counts
- If [5, 3, 2] -> 2 inversion counts are present -> {5, 3}, {3, 2}
- O(N^2) is simple, but we will be required to find better... basic comparisons are needed so motive is to reduce comparisons
- Now as we need to find where left>right, this is same thing we check in merge part of merge sort, and there ...
- If left>right, we can simply result+=(everything from left to mid) as all of them will form pair with right (Complexity remains same O(NlogN))

14. EASY(Best Time to buy/sell stocks, wolves of wolf street)
- Greedily approach this problem
- Keep minimum found at any point and keep checking with prices to get max

15. Rotate Image (2d Array)
- See solution first, it's nothing but transpose with rows reversed
- Must know how to transponse a matrix (changing rows to columns)

16. Search a 2d matrix
- Point to note is as things are sorted, we can go for binary search
- ... both from top to bottom and from left to right!
- BUT WE CAN DO IT IN SINGLE LOG N as well ! THAT's IMPORTANT TO UNDERSTAND!

17. Binary Exponentiation
- Point is that if power is even we can do (x^2)^(n/2) & if odd then x * (x)^ n-1
- Also point to note is the edge case where power is given negative - use long long int in that case
- Also for negative power just consider x as 1/x

18. Majority element II
- Similar to Majority Element I (Moores Voting Algo)
- Here rather than 1, 2 params needs to be checked
- Make sure at last to count manually if it's really > 1/3 (in ME I, it was given that it will exist, so there was no need to check)

19. 4 SUM
- Technique similar to 2 sum can be used
- We will use 2 pointer i, j to iterate and left/right to then move right and left ro remaining items
- NOTE: guys btw i & j doesn't need to be checked again by left/right (here I was confused) as it would already cover them before itself when i and j were present there
- Make sure to use lower_bound and upper_bound to skip the same values again (to prevent duplication)

20. Largest Subarray with Sum 0
- Logic is A1, A2, A3, A4, A5, A6 if (A1 - A4) sum is 5 and (A1-A6) sum is 5 then it's clear that A5-A6 sum is 0
- Also we need to keep index of first occurance (basic understanding) as to maximize subarray

21. Longest Common Subsequence
- Important to note that we use hashing and iterate over hash
- We check sequence forward only if previous doesn't exists (As the sequence will definitely contain num which has no preceding num)
- Also it prevents doing O(N^2) and acheiving O(N)

22. ⭐️ Number of subarrays with XOR as k
- Similar to count max subarray with sum as 0
- Here we need to understand that 1-4 ^ 4-8 = XOR of 1-8
- And we can do 1-4 = 1-8 ^ 4-8 (XORing 4-8 both sides) 
- So Y ^ taget = currPrefix => { Y(count how may times this prefix occured) ^ target }

23. Longest Substring without repeating character
- It can be simply done using unordered_set but that would give O(2N) !!
- A optimised version can be to use map and store index where char occured
- So that rather than traversing left all the way to right we can rather do index+1 whenever repetition occurs
- This will help to do it in O(N)- Important!

24. Remove nth from single pass
- Point to note is to use 2 ptr - slow and fast and help then create gap of n
- So that in single pass we can reach nth from last
- Got stuck in edge case - when it's the head to be removed(point was to check if fast is already NULL means remove head)

25. (Forgot) Intersection of 2 linked list
- We just need to find which is longer one and how much longer
- And can advance the head in that longer list
- Later can just start jumping one one step and see where they meet!
- ALTERNATIVE (I didn't like but should be known): Rather than counting, as seen as smaller one reaches null, we can immediately start from other list so that we don't have to do the counting of both

26. Linked List Cycle
- One will jump once, while other will jump twice
- At some time they will come at same point if cycle is there

27. Reverse linked list in k group
- First thing to know is how to reverse linked list - iterative/recursive
- Next is to iterate over the list and do it in group

28. Palindrome linked list
- Find middle and reverse the second half part
- Now just iterate in first and second half and see if same
- If same means palindrome
- If Q asks list shouldn't be changed, then reverse back again

29. Linked List Cycle II (Start point of cycle)
- Start point is where 2 nodes are pointing at
- Algo states that first find the meeting point of fast and slow
- Then take one one step from above point & head and return where they meet (that's start of cycle)
- CAN BE USED TO FIND DUPLICAT IN ARRAY ALSO !

30. Flatten Linked List
- Similar to merge 2 linked list
- Here we just need to do it recursively

31. Rotate Linked List (Basic Question, nothing complex)
- Just find the point from where to rotate
- Remove connection and join the end to head!

32. ⭐️ Copy list with random pointer
- 1) when space is not an issue - we can simply use map for storing <real node | corresponding node> And wire them!
- 2) when space is issue - we need to wire new list along with existing(using next)
- And update the random ( as random is nothing but random's next - for new list ) - that's how wiring both list together helps
- Once random updated, remove the wiring and separate out the new list

33. 3 SUM
- Problem similar to 2 sum, and similar logic is also used in 4 sum
- We majorly have to implement logic of 2 sum here
- just take index and use 2 sum for remainging right item to find the required sum

34. Trapping Rain Water (Just looks difficult/Easy)
- Point is to find left max height and right max height
- Now each index will find how much water it's going to store
- Sum those value up and return

35. N Meetings in one room
- We need to focus on ending time, hence sort using ending time as a pair so first is also sorted if ending is same
- Now we just need to pick using least ending point
- After this, pick the next least ending point which has starting pointer after current's ending point

36. ⭐️ Minimum Plaforms
- Q is different than "find max meetings which can happen"
- Here Q is simpler, is just asks you how many plaforms should be built so no train should wait
- We just need to sort both arrival and departure, and keep incrementing platform if arrival is before departure
- There is no need to keep arr/dep in pair as it's not required

37. Job Sequencing Problem (Imp, can be asked in multiple ways)
- Important to understand the problem - if deadline is 5, it can be done it at 5th, 4th, 3rd, 2nd, 1st hour
- As profit needs to be maximized we need to sort based on profit (use comparator if structure is given)
- Important is to use a deadline array to store which intervals are taken
- So, if deadline 4: profit 12 came and 4th was already filled, traverse from 4-1 and see which is remaining, if no remaining skip that work!

38. Minimum number of coins
- Basic question, as we need to minimize number of coins, we need to take the greater ones first
- And then move on to the next greater number and see how many of those can be accomodated

39. Fractional Knapsack
- value/weight is considered as priority for maximizing the values
- We take all wt till we reach a wt which would exceed the wt range given
- Hence for that we will take fraction (Hence Fractional Knapsack problem)
- This is not 0/1 Knapsack, that's different

40. Subset Sum
- V. Imp to understand how we are generating all the subsets here
- WE DON'T NEED TO DO 'FOR LOOPS', the two recursive calls takes care of generating all subsets

41. Subset sums 2
- Sorting + Recursion is major part here, why to sort? - so we can skip already taken data
- Use scratch for understanding, rest everything is same as subset (2 recursive calls)

42. Permutations
- Swapping back is the main logic, rest try in scratch to understand. Basic Q.

43. Combination Sum
- Basic Recursion

44. ⭐️ Combination Sum 2
- TOOK LONG TIME TO SOLVE! (Try your own)
- using set (extra space) may not work, so we can use sorting and then not recurse with already taken data twice

45. Permutation Sequence (Imp/ Repeating)
- Steps to find next permutation is important
- 1)Find i<i+1 then swap it with immediate greatest to right
- Now just sort all nums from swapped ind to right

46. 🌟 Permutation Sequence (MUST DO)
- Although we can do next_permutation k times but that won't be efficient solution
- Hence we make use of math trick i.e if we have 123 then 1 {2, 3} -> this will be total 2 sequence (0-1) and hence if we have k=1 we know it will be 132
- Hence we pick 1 and recursively take 2 {3} or 3 {2} based on remaining number

47. N Queens (Recursion)
- Basic recursion

48. Sudoku Solver (Recursion)
- "Always forgot" to *3 when checking for grid! i.e (i/3) * 3

49. M Coloring Problem (Graph Problem)
- It's a 2D Array given as edges, we just need to color each node such that no 2 adjacent node has same color
- We can take one 1D array to keep a check which node is colored what and then iterate over graph and check with adjacent nodes
- It's a basic recursion problem

50. Rat in a maze-I
- It's basic recursive problem
- Make sure to block the way(0) once you are taken it
- Make sure to unblock the way(1) once you are done with that grid

51. Nth root of a number (It's ok to do binary search even in decimals)
- Important to understand that logic of 1e-6 (right-left), and complexity because of it gets 10^6 (that many digits we will have)
- It's monotonic binary search problem

52. Single element in sorted array
- Based on observation only, The alternative is to do XOR of all and find the one whihch occurs only once
- Here we observed that if even index must have same item to next index
- And for odd index, similar item should be their in previous index

53. ⭐️ Search in Rotated Sorted Array
- 2 Ways of doing this
- 1) (logN + logN) Find the shifted pivot (using binary search) and then another binary search to find the num in required section
- 2)  (logN ) BETTER: after getting mid, either left or right of it must be perfectly sorted, check if target lies in that range
- If it doesn't then move to other section and start finding there

54. 🌟 🌟 (Extremely important) Median in a rowwise sorted matrix (Took too long to understand - how non existing nums are taken care)
- It's a monotonic BS Question as clearly there is a search space and solution is definitely exists somewhere there
- We can easily count the nums to the left of the number (& hence we can reach medium like this)
- Also we will just move right when left part is not enough and left when left part is more
- hence the left movement takes care of nums which doesn't exists in the range (as we will be stuck with the one which is existing) - IMPORTANT!

55. 🌟 🌟 (Extremely important) Median of 2 sorted Arrays (Took too long to understand - the point that we can pick the n/2 from first Array + second Array)
- Think about median. Before median there are n/2 items.
- And we are given 2 SORTED ARRAYS, hence make use of it to get those first n/2 items
- Take the smaller array and do binary search to place the limit till where you will consider the items (a part of that n/2) and the rest of the part from other array
- That's how using binary search you will get the items from array 1 and array 2 and at the end you can get simply find the median using items at last
- HOW TO SEE IF LIMIT IS THE ONE WE WANT? - The last item of both array limit taken must be smallest than the rest of the part!

56. 🌟 🌟 (Similar to 55.) kth element of two sorted array (Done because similar question 55. was done before)
- Instead of median (n/2 number on the left), here directly k is given
- We can implement similar logic like 55 here!
- Make sure to put edge conditions like - what if index to be taken for other array is > n or < 0

57. Power Set (Finding Subsequence using bits)
- Already know how to find using recursion
- This way is finding subsequence using bit as 000, 001, 010, 011, 100 ... are subsequnces btw for 3 digits(2^3 - 1)=8 ways in total
- "abc" -> for each 000, 001, 010, ... we can do & abc.
- To consider a -> 2^0 (001) & (011) must come 1.... 2^0 is (1<<0)=1 | Similarly for "b" 1<<1=2(010) & (011) = 1 yes take b as well.... that's how find subsequence

58. 🌟 Allocate Minimum number of pages (HAS TO BE PRACTICED!!)
- Minimize maximum number of items type question - binary search has to be used
- Think of range and picking every number to see if that can be taken as max pages which can be allocated to M number of students

59. 🌟 Aggresive Cows (Maximize the minimum -> similar to minimize the maximum)
- As these kind of questions will introduce a search space, hence we can make use of Binary search!
- Just pick 1, maxDistancePossible and keep checking if mid is possible
- If it's possible keep moving to right?Why? -> because we need to maximize it
- Moving right will automatic maximize the minimum as it will set on that x, y (rest all will just dwell in)

60. Implement Queue using Array
- Important to note that we move rear while insertion and not the front
- While removing we remove from front and increment front
- (IMPORTANT) Make sure to do "%size" so that after reaching end of array, both rear and front can again start picking indices from 0

61. Implement stack using queue
- Can be done using single queue, while insertion just reverse back the queue
- How reverse? - just push front to back till n-1. Now the queue acts like stack for pop, top operations!

62. Implement Queue using stack O(1)+
- We can make use of 2 stack! Use input for entering and output for pop and top
- Shift data from input to output only when pop or front required

63. Next greater element II
- Using stack to keep track of next greater is the best way of doing it. Pop out if next greater is smaller and insert if found greater one (think of poles)
- Also as we need  cyclic here, repeat the array of use %N

64. ⭐️ LRU Cache
- Use Doubly linked list as it will provide access to first, last and in btw data instantly
- For above to get in between data we can make use of hash map to store the node address to get the data instantly

65. Largest Rectangle in Histogram (HARD yet easy)
- We need to see the naive solution first, we basically are checking the next smallest num in left and right for each bar
- This can be done in O(N^2) but we can optimize it using the problem "NEXT SMALLER" - and doing it for both left and right side
- Hence complexity becomes O(N)

66. ⭐️ Sliding Window Maximum
- We need to find the max in the window, this can be done best by deque(as it provides add/remove from both front and back)
- In dq, we will add the item if current existing in back is larger
- If it's smaller, just start removing them -- as anyways current will be the max in the k items
- Don't forget to remove from front when you move forward with k

67. 🌟 Rotten Oranges (BFS!)
- We can implement BFS Here! (Use queue) in contrary to DFS and DFS is of no use here
- While using queue we can pick the rotten oranges and keep pushing more
- Which helps us to get the number of days to get the complete rotten oranges!