After solving many DSA problems, I've noticed some key patterns that are important for coding interviews.
At the end of this article, I have also included links to some of the best LeetCode articles that I found helpful for better understanding.
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.
- Linked List Cycle II
- Remove nth Node from the End of List
- Find the Duplicate Number
- Palindrome Linked List
2. Overlapping Intervals
Description: Intervals are often manipulated through sorting and merging based on their start and end times.
- Merge Intervals
- Insert Interval
- My Calendar II
- Minimum Number of Arrows to Burst Balloons
- Non-overlapping Intervals
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.
- Find the Middle Index in Array
- Product of Array Except Self
- Maximum Product Subarray
- Number of Ways to Split Array
- Range Sum Query 2D
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
- Maximum Sum Subarray of Size K
- Number of Subarrays Having Average Greater or Equal to Threshold
- Repeated DNA Sequences
- Permutation in String
- Sliding Subarray Beauty
- Sliding Window Maximum
Variable Size
- Longest Substring Without Repeating Characters
- Minimum Size Subarray Sum
- Subarray Product Less Than K
- Max Consecutive Ones
- Fruits Into Baskets
- Count Number of Nice Subarrays
- Minimum Window Substring
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.
- Two Sum II - Input Array is Sorted
- Dutch National Flag: Sort Colors
- Next Permutation
- Bag of Tokens
- Container With Most Water
- Trapping Rain Water
6. Cyclic Sort (Index-Based)
Description: Cyclic sort is an efficient approach to solving 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. Merge Intervals
Description: Problems that involve merging overlapping intervals require sorting the intervals first and then merging them based on conditions.
- Merge Intervals
- Interval List Intersections
- Meeting Rooms II
- Minimum Number of Arrows to Burst Balloons
10. Bit Manipulation
Description: Bitwise operations are useful for solving problems that involve binary representation, toggling bits, and checking for power-of-two numbers.
11. Backtracking
Description: Backtracking is used to explore all possible solutions by trying out different possibilities and undoing incorrect choices.
12. Dynamic Programming
Description: DP problems involve breaking problems into smaller subproblems and using memoization or tabulation to store computed values.
13. Greedy Algorithms
Description: The greedy approach involves making the best choice at each step to find the global optimum.
14. Graphs (BFS & DFS)
Description: Graph traversal techniques like Breadth-First Search (BFS) and Depth-First Search (DFS) are widely used in problems involving paths, cycles, and connectivity.
15. Topological Sorting
Description: Used for scheduling tasks or finding dependency orders in Directed Acyclic Graphs (DAGs).
16. Trie (Prefix Tree)
Description: A Trie is a tree-like data structure used for fast searching of prefixes in words.
17. Heap (Priority Queue)
Description: Min-heaps and max-heaps are used to efficiently get the smallest/largest elements in a dataset.
18. Union-Find (Disjoint Set)
Description: The Union-Find data structure helps in solving problems related to connectivity and cycles in graphs.
19. Monotonic Stack
Description: A stack where elements are pushed or popped based on increasing or decreasing order constraints.
Conclusion
These patterns are fundamental for solving a variety of DSA problems efficiently. If you understand these well, you'll be well-prepared for coding interviews! 🚀
Also, check out these amazing LeetCode resources for further reading:
Happy coding! 🎯
Top comments (0)