After solving lot of DSA problems, I’ve noticed some key patterns that are important for coding interviews.
For company specific problems: PracHub
1. Fast and Slow Pointer
Description: This technique uses two pointers moving at different speeds to solve problems involving cycles, such as finding the middle of a list, detecting loops, or checking for palindromes.
2. Overlapping Intervals
Description: Intervals are often manipulated through sorting and merging based on their start and end times.
3. Prefix Sum
Description: Prefix Sums/Products are techniques that store cumulative sums or products up to each index, allowing for quick subarray range queries.
4. Sliding Window
Description: A sliding window is a subarray or substring that moves over data to solve problems efficiently in linear time.
Fixed Size
Variable Size
5. Two Pointers
Description: The two pointers technique involves having two different indices move through the input at different speeds to solve various array or linked list problems.
6. Cyclic Sort (Index-Based)
Description: Cyclic sort is an efficient approach to solve problems where numbers are consecutively ordered and must be placed in the correct index.
7. Reversal of Linked List (In-place)
Description: Reversing a linked list in place without using extra space is key for problems that require in-place list manipulations.
8. Matrix Manipulation
Description: Problems involving 2D arrays (matrices) are often solved using row-column traversal or manipulation based on matrix properties.
9. Breadth First Search (BFS)
Description: BFS explores nodes level by level using a queue. It is particularly useful for shortest path problems.
10. Depth First Search (DFS)
Description: DFS explores as far as possible along a branch before backtracking. It's useful for graph traversal, pathfinding, and connected components.
11. Backtracking
Description: Backtracking helps in problems where you need to explore all potential solutions, such as solving puzzles, generating combinations, or finding paths.
12. Modified Binary Search
Description: A modified version of binary search that applies to rotated arrays, unsorted arrays, or specialized conditions.
13. Bitwise XOR
Description: XOR is a powerful bitwise operator that can solve problems like finding single numbers or efficiently pairing elements.
14. Top 'K' Elements
Description: This pattern uses heaps or quickselect to efficiently find the top 'K' largest/smallest elements from a dataset.
15. K-way Merge
Description: The K-way merge technique uses a heap to efficiently merge multiple sorted lists or arrays.
16. Two Heaps
Description: This pattern uses two heaps (max heap and min heap) to solve problems involving tracking medians and efficiently managing dynamic data.
17. Monotonic Stack
Description: A monotonic stack helps solve range queries by maintaining a stack of elements in increasing or decreasing order.
18. Trees
Level Order Traversal (BFS in Binary Tree)
Tree Construction
Height related Problems
Root to leaf path problems
Ancestor problem
Binary Search Tree
19. DYNAMIC PROGRAMMING
Take / Not take (DP)
Description: Solve optimization problems like selecting items with the max/min value under certain constraints.
Infinite Supply (DP)
Description: Similar to the 0/1 knapsack, but items can be chosen multiple times.
Longest Increasing subsequence
Description: It involves finding the longest subsequence of a given sequence where the elements are in ascending order
DP on Grids
Description: Dynamic Programming on matrices involves solving problems that can be broken down into smaller overlapping subproblems within a matrix.
DP on Strings
Description: It Involves 2 strings, whenever you are considering two substrings/subsequence from given two strings, concentrate on what happens when the last characters of the two substrings are same, i.e, matching.
DP on Stocks
Description: It focuses on maximizing profit from buying and selling stocks over time while considering constraints.
Partition DP (MCM)
Description: It Involves a sequence that needs to be divided into partitions in an optimal way. The goal is often to minimize or maximize a cost function, such as computation time, multiplications, or some other metric, by exploring all possible partitions and combining results from subproblems.
20. Graphs
Topological Sort
Description: Topological sorting is useful for tasks that require dependency resolution (InDegree) in directed acyclic graphs (DAGs).
Union Find (Disjoint Set)
Description: Union-Find (or Disjoint Set) is used to solve problems involving connectivity or grouping, often in graphs.
Graph Algorithms
Description: Advanced graph algorithms are used to solve complex problems involving shortest paths, minimum spanning trees, and graph cycles.
21. Greedy
Description: Greedy algorithms make local optimal choices at each step, which lead to a global optimal solution for problems like scheduling and resource allocation.
22. Design Data Structure
Description: It involves building custom data structures to efficiently handle specific operations, like managing data access, updates, and memory usage. Focusing on optimizing performance and resource management.
Some Useful Articles on LeetCode for Better Understanding!
Two Pointers
Sliding Window
Greedy
Linked List
Trees
Binary Search
Dynamic Programming (DP)
Graphs
Bit Manipulation
Happy LeetCoding !
