similar_problems.txt

1. Sticker Thief (Array, DP) & Max Subset Sum (Tree)
    > Inclusion/Exclusion principle used in both

2. One Edit distance & Levenshtein problem
    > Both can be done using Levenshtein but one edit can be optimised

3. Merge sort & count inversions problem - both uses merge sort algo
    - important to understand why count inversions uses merge sort for optimization
    - smallest string: logic to understand is how we used merge sort here & why simple sort didn't work!
    - Reverse Pairs Problem (Similar to Inversion count)

4. Quick Sort & kth largest item in array - both uses Quick Sort
    - important to understand how partitioning algo is reducing the complexity. (by not picking on half)

5. Monotonic Binary Search (Maximize the minimum subarray/distance/something)
    - Angry Birds
    - Game of Greed
    Minimize the Maximum
    - Reading Books (*)

6. Backtracking(Must do)
    - longest_possible_route
    - NQueens
    - rat_maze
    - sudoku_solver

7. Stack Questions (What is first Max on left?)
    - Next greater element
    - online stock span 
    important to understand why we used stack- simple cause we need to pop when it's smaller!

8. Heap/Priority Queue (k smallest/largest)
    - k nearest cabs
    - k largest number/ k smallest number
    - min cost to merge rope (uses PQ - reason is it needs min each time)

9. Hashing
    - Find number of rectangles
    - Find number of triangles

10. Floyd Algorithm
    - Linked List Cycle II
    - Duplicate element (array but used linked list floyd algo)

11. Using Some Math
    - Find max subarrays with sum 0 (property used was that if 1-3 & 1-10 has same sum means 4-10 is 0)
    - Find no of subarrays with xor as k (property used is Y ^ target = currPrefix so, Y = currPrefix ^ target ) and we can count occurance of Y now

12. ⭐️ Range Questions (THESE LOOK SIMILAR & ARE DIFFERNT)
    - Maximum Number of meetings which could happen (just focus ending time of meeting - sort and do some op)
    - Minimum number of plaforms (here just increment plaform if arrival is smaller than departure | sort both arrival & departure and do op)
    - Job Sequencing problem

13. ⭐️ (Must try once) Median Questions (Logic is simple- before median there exists n/2 items)
    - Median of 2 sorted Arrays
    - Median in a rowwise sorted matrix
    - kth element of two sorted array

14. Wiggle Subsequence & LIS (Similar DP Logic in both of them/ Important to try once)
    - As multiple ways possible do recursion
    - Make sure to do top down and return the result all the way up (like return fn() + 1) rather than sending result to next stack fn(x, result+1) XXX
    
15. Jump Game, Jump Game 2 
    - Jump Game implements DP, while Jump Game 2(finding min jumps) we can do using greedy