DSA Patterns you need to know !!!

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. Missing Number Find Missing Numbers Set Mismatch First Missing Positive 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. Reverse Linked List Reverse Nodes in k-Group Swap Nodes in Pairs 8. Matrix Manipulation Description: Problems involving 2D arrays (matrices) are often solved using row-column traversal or manipulation based on matrix properties. Rotate Image Spiral Matrix Set Matrix Zeroes Game of Life 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. Single Number Number of 1 Bits Power of Two Counting Bits 11. Backtracking Description: Backtracking is used to explore all possible solutions by trying out different possibilities and undoing incorrect choices. Generate Parentheses Permutations Combination Sum Sudoku Solver 12. Dynamic Programming Description: DP problems involve breaking problems into smaller subproblems and using memoization or tabulation to store computed values. Climbing Stairs House Robber Longest Palindromic Substring Longest Common Subsequence 13. Greedy Algorithms Description: The greedy approach involves making the best choice at each step to find the global optimum. Jump Game Gas Station Assign Cookies Partition Labels 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. Number of Islands Course Schedule Word Ladder Surrounded Regions 15. Topological Sorting Description: Used for scheduling tasks or finding dependency orders in Directed Acyclic Graphs (DAGs). Course Schedule II Alien Dictionary Find Eventual Safe States 16. Trie (Prefix Tree) Description: A Trie is a tree-like data structure used for fast searching of prefixes in words. Implement Trie (Prefix Tree) Word Search II Replace Words 17

Mar 5, 2025 - 16:05

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.

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 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.

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!