Leetcode Pattern Recognition Cheat Sheet
Uploaded by
Harshvardhan SinghLeetcode Pattern Recognition Cheat Sheet
Uploaded by
Harshvardhan SinghCommon questions
Powered by AIIn problems with small n (≤ 20), brute force approaches are viable due to the manageable number of combinations or permutations possible. Backtracking and recursion are appropriate as exponential time complexity, such as 2^n or n!, is acceptable under these constraints .
Islands problems in 2D grids or matrices are ideally tackled using DFS or BFS, which explore each land cell and connect them with adjacent ones to form a whole island. Union Find can also be employed to efficiently manage connected regions by tracking and merging parent nodes without exploring each cell individually .
Union Find is instrumental in managing connected components by efficiently handling union and find operations that signify group connections. It's particularly useful in dynamic connectivity to manage disjoint sets without repeatedly traversing each element, enabling fast checks and updates to the subset mappings, which is crucial in large graphs for determining component territories .
Sliding window techniques are preferred for substring or subarray problems because they provide a streamlined way to handle fixed or variable section lengths within a dataset. This method efficiently tracks elements that satisfy given conditions without redundant recalculations, thus reducing computational complexity compared to restarting checks after each element shift .
For medium n (10^3 to 10^6), greedy algorithms are suitable because they often provide linear O(n) or nearly linear O(n log n) solutions that efficiently handle the allowed input size. They make the locally optimal choice at each step with the hope of finding a global optimum .
Tree problems typically involve traversals like DFS for all paths or BFS for shortest unweighted path, focusing on parent-child relationships and predefined traversal orders like preorder, inorder, or postorder. Graph problems, on the other hand, use BFS for shortest path, DFS for connected components, and additional techniques like Union Find and topological sorting to handle more generalized structures like dependencies or disjoint sets .
Bit manipulation is highly efficient for large datasets due to its constant time operations. Problems like finding a 'single number' or checking 'power of 2' solve complex bitwise operations using limited computational resources. Given constraints that preclude linear time solutions for large n, bit manipulation's O(1) operations effectively address performance requirements .
The two pointers technique is versatile in solving problems involving strings and arrays. For strings, it can be applied to check palindromes by comparing characters from both ends towards the center. In arrays, it can efficiently solve sorted array problems by moving one pointer from the start and one from the end to meet specific conditions, such as computing target sums or removing duplicates .
While backtracking is largely infeasible for medium n (10^3 to 10^6) due to its generally exponential nature, it remains ideal for specific scenarios that involve combinatorial generation with constraints where brute force is necessary to explore possibilities. However, large n (≥ 10^7) requires more efficient algorithms, like O(log n) or constant time solutions, because the computational load of backtracking becomes prohibitive .
Dynamic programming techniques efficiently solve 'number of ways' problems by breaking them down into smaller, manageable subproblems and storing results to avoid redundant computations. This approach allows the solution to explore multiple paths or combinations, ideal for counting variations like subsets, paths, or sequences .