This article will help you to explore 15 most important patterns I learned during my DSA journey.
Not only this, I’ll share when to use each pattern along with a sample problem and provide links to LeetCode problems you can practice to learn these patterns better.
- For all new updates: Subscribe
1. Prefix Sum
Prefix Sum involves preprocessing an array to create a new array where each element at index i represents the sum of the array from the start up to i. This allows for efficient sum queries on subarrays.
Use this pattern when you need to perform multiple sum queries on a subarray or need to calculate cumulative sums.
Sample Problem:
Given an array nums, answer multiple queries about the sum of elements within a specific range [i, j].
Example:
- Input:
nums = [1, 2, 3, 4, 5, 6],i = 1,j = 3 - Output:
9
Explanation:
- Preprocess the array
Ato create a prefix sum array:P = [1, 3, 6, 10, 15, 21]. - To find the sum between indices
iandj, use the formula:P[j] - P[i-1].
LeetCode Problems:
Next
- For all new updates: Subscribe
2. Two Pointers
The Two Pointers pattern involves using two pointers to iterate through an array or list, often used to find pairs or elements that meet specific criteria.
Use this pattern when dealing with sorted arrays or lists where you need to find pairs that satisfy a specific condition.
Sample Problem:
Find two numbers in a sorted array that add up to a target value.
Example:
- Input:
nums = [1, 2, 3, 4, 6],target = 6 - Output:
[1, 3]
Explanation:
- Initialize two pointers, one at the start (
left) and one at the end (right) of the array. - Check the sum of the elements at the two pointers.
- If the sum equals the target, return the indices.
- If the sum is less than the target, move the left pointer to the right.
- If the sum is greater than the target, move the right pointer to the left.
LeetCode Problems:
In case you want to solve all two pointers problems
- For all new updates: Subscribe
Majority of two pointers problems are in easy or medium section in LeetCode so, if you understand the basic ideas then it should be solvable without much hints and editorials.
I see 4 bigger categories and many sub categories in it, and marked the typical example problems with (*). My recommendation is to start solving these example problems(*), and apply the knowledge to the other problems.
1. Left & Right Pointer (Approaching from both ends of Array)
2 Sum problem
(*) https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
https://leetcode.com/problems/3sum/
https://leetcode.com/problems/4sum/
https://leetcode.com/problems/number-of-subsequences-that-satisfy-the-given-sum-condition/
https://leetcode.com/problems/two-sum-iv-input-is-a-bst/
https://leetcode.com/problems/sum-of-square-numbers/
https://leetcode.com/problems/boats-to-save-people/
https://leetcode.com/problems/minimize-maximum-pair-sum-in-array/
https://leetcode.com/problems/3sum-with-multiplicity/Trapping Water
(*) https://leetcode.com/problems/trapping-rain-water/
https://leetcode.com/problems/container-with-most-water/Next Permutation
(*) https://leetcode.com/problems/next-permutation/
https://leetcode.com/problems/next-greater-element-iii/
https://leetcode.com/problems/minimum-adjacent-swaps-to-reach-the-kth-smallest-number/Reversing / Swapping
https://leetcode.com/problems/valid-palindrome/
(*) https://leetcode.com/problems/reverse-string/
https://leetcode.com/problems/reverse-vowels-of-a-string/
https://leetcode.com/problems/valid-palindrome-ii/
https://leetcode.com/problems/reverse-only-letters/
https://leetcode.com/problems/remove-element/
https://leetcode.com/problems/sort-colors/
https://leetcode.com/problems/flipping-an-image/
https://leetcode.com/problems/squares-of-a-sorted-array/
https://leetcode.com/problems/sort-array-by-parity/
https://leetcode.com/problems/sort-array-by-parity-ii/
https://leetcode.com/problems/pancake-sorting/
https://leetcode.com/problems/reverse-prefix-of-word/
https://leetcode.com/problems/reverse-string-ii/
https://leetcode.com/problems/reverse-words-in-a-string/
https://leetcode.com/problems/reverse-words-in-a-string-iii/Others
https://leetcode.com/problems/bag-of-tokens/
https://leetcode.com/problems/di-string-match/
https://leetcode.com/problems/minimum-length-of-string-after-deleting-similar-ends/
https://leetcode.com/problems/sentence-similarity-iii/
https://leetcode.com/problems/find-k-closest-elements/
https://leetcode.com/problems/shortest-distance-to-a-character/
NEXT
2. Slow & Fast Pointers
Using two pointers with different speed of movement. Typically they starts from the left end, then the first pointer advances fast and give some feedback to the slow pointer and do some calculation.
Linked List Operations
(*) https://leetcode.com/problems/linked-list-cycle/
https://leetcode.com/problems/linked-list-cycle-ii/
https://leetcode.com/problems/remove-nth-node-from-end-of-list/
https://leetcode.com/problems/rotate-list/
https://leetcode.com/problems/reorder-list/
https://leetcode.com/problems/palindrome-linked-list/Cyclic Detection
(*) https://leetcode.com/problems/find-the-duplicate-number/
https://leetcode.com/problems/circular-array-loop/Sliding Window/Caterpillar Method
(*) https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/
https://leetcode.com/problems/find-k-th-smallest-pair-distance/
https://leetcode.com/problems/moving-stones-until-consecutive-ii/
https://leetcode.com/problems/count-pairs-of-nodes/
https://leetcode.com/problems/count-binary-substrings/
https://leetcode.com/problems/k-diff-pairs-in-an-array/Rotation
(*) https://leetcode.com/problems/rotating-the-box/
https://leetcode.com/problems/rotate-array/String
(*) https://leetcode.com/problems/string-compression/
https://leetcode.com/problems/last-substring-in-lexicographical-order/Remove Duplicate
(*) https://leetcode.com/problems/remove-duplicates-from-sorted-array/
https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/
https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
https://leetcode.com/problems/duplicate-zeros/Others
https://leetcode.com/problems/statistics-from-a-large-sample/
https://leetcode.com/problems/partition-labels/
https://leetcode.com/problems/magical-string/
https://leetcode.com/problems/friends-of-appropriate-ages/
https://leetcode.com/problems/longest-mountain-in-array/
https://leetcode.com/problems/shortest-subarray-to-be-removed-to-make-array-sorted/
3. Merging 2 Arrays | Running from beginning of 2 Arrays
Given 2 arrays or lists, then you have to process them with individual pointers.
Sorted arrays
(*) https://leetcode.com/problems/merge-sorted-array/
https://leetcode.com/problems/heaters/
https://leetcode.com/problems/find-the-distance-value-between-two-arrays/Intersections/LCA like
(*) https://leetcode.com/problems/intersection-of-two-linked-lists/
https://leetcode.com/problems/intersection-of-two-arrays/
https://leetcode.com/problems/intersection-of-two-arrays-ii/SubString
(*) https://leetcode.com/problems/implement-strstr/
https://leetcode.com/problems/longest-word-in-dictionary-through-deleting/
https://leetcode.com/problems/long-pressed-name/
https://leetcode.com/problems/longest-uncommon-subsequence-ii/
https://leetcode.com/problems/compare-version-numbers/
https://leetcode.com/problems/camelcase-matching/
https://leetcode.com/problems/expressive-words/Median Finder
(*) https://leetcode.com/problems/find-median-from-data-stream/Meet-in-the-middle / Binary Search
(*) https://leetcode.com/problems/partition-array-into-two-arrays-to-minimize-sum-difference/
https://leetcode.com/problems/closest-subsequence-sum/
https://leetcode.com/problems/ways-to-split-array-into-three-subarrays/
https://leetcode.com/problems/3sum-closest/
https://leetcode.com/problems/valid-triangle-number/Others
https://leetcode.com/problems/shortest-unsorted-continuous-subarray/
https://leetcode.com/problems/most-profit-assigning-work/
https://leetcode.com/problems/largest-merge-of-two-strings/
https://leetcode.com/problems/swap-adjacent-in-lr-string/
4. Divide & Conquer | Split & Merge of Array
Divide & conquer is similar to Split & Merge but there is one thing added. First, you need to split the given list into 2 separate lists and then do two pointers approach to merge or unify them. There aren’t many problems.
Partition
(*) https://leetcode.com/problems/partition-list/Sorting
(*) https://leetcode.com/problems/sort-list/
Next
- For all new updates: Subscribe
3. Sliding Window
Sliding Window pattern is used to find a sub-array or sub-string that satisfies a specific condition, optimizing the time complexity by maintaining a window of elements.
Use this pattern when dealing with problems involving contiguous sub-arrays or sub-strings.
Sample Problem:
Find the maximum sum of a subarray of size k.
Example:
- Input:
nums = [2, 1, 5, 1, 3, 2],k = 3 - Output:
9
Explanation:
- Start with the sum of the first
kelements. - Slide the window one element at a time, subtracting the element that goes out of the window and adding the new element.
- Keep track of the maximum sum encountered.
LeetCode Problems:
Next
- For all new updates: Subscribe
4. Fast & Slow Pointers
The Fast & Slow Pointers (Tortoise and Hare) pattern is used to detect cycles in linked lists and other similar structures.
Sample Problem:
Detect if a linked list has a cycle.
Explanation:
- Initialize two pointers, one moving one step at a time (slow) and the other moving two steps at a time (fast).
- If there is a cycle, the fast pointer will eventually meet the slow pointer.
- If the fast pointer reaches the end of the list, there is no cycle.
LeetCode Problems:
Next
- For all new updates: Subscribe
5. LinkedList In-place Reversal
In-place Reversal of a LinkedList pattern reverses parts of a linked list without using extra space.
Use this pattern when you need to reverse sections of a linked list.
Sample Problem:
Reverse a sublist of a linked list from position m to n.
Example:
- Input:
head = [1, 2, 3, 4, 5],m = 2,n = 4 - Output:
[1, 4, 3, 2, 5]
Explanation:
- Identify the start and end of the sublist.
- Reverse the nodes in place by adjusting the pointers.
LeetCode Problems:
Next
- For all new updates: Subscribe
6. Monotonic Stack
The Monotonic Stack pattern uses a stack to maintain a sequence of elements in a specific order (increasing or decreasing).
Use this pattern for problems that require finding the next greater or smaller element.
Sample Problem:
Find the next greater element for each element in an array. Output -1 if the greater element doesn’t exist.
Example:
- Input:
nums = [2, 1, 2, 4, 3] - Output:
[4, 2, 4, -1, -1]
Explanation:
- Use a stack to keep track of elements for which we haven’t found the next greater element yet.
- Iterate through the array, and for each element, pop elements from the stack until you find a greater element.
- If the stack is not empty, set the result for index at the top of the stack to current element.
- Push the current element onto the stack.
LeetCode Problems:
Next
- For all new updates: Subscribe
7. Top ‘K’ Elements
The Top ‘K’ Elements pattern finds the top k largest or smallest elements in an array or stream of data using heaps or sorting.
Sample Problem:
Find the k-th largest element in an unsorted array.
Example:
- Input:
nums = [3, 2, 1, 5, 6, 4],k = 2 - Output:
5
Explanation:
- Use a min-heap of size k to keep track of the k largest elements.
- Iterate through the array, adding elements to the heap.
- If the heap size exceeds k, remove the smallest element from the heap.
- The root of the heap will be the k-th largest element.
LeetCode Problems:
Next
- For all new updates: Subscribe
8. Overlapping Intervals
Overlapping Intervals pattern is used to merge or handle overlapping intervals in an array.
In an interval array sorted by start time, two intervals [a, b] and [c, d] overlap if b >= c (i.e., the end time of the first interval is greater than or equal to the start time of the second interval).
Sample Problem:
Problem Statement: Merge all overlapping intervals.
Example:
- Input:
intervals = [[1, 3], [2, 6], [8, 10], [15, 18]] - Output:
[[1, 6], [8, 10], [15, 18]]
Explanation:
- Sort the intervals by their start time.
- Create an empty list called
mergedto store the merged intervals. - Iterate through the intervals and check if it overlaps with the last interval in the
mergedlist. - If it overlaps, merge the intervals by updating the end time of the last interval in
merged. - If it does not overlap, simply add the current interval to the
mergedlist.
LeetCode Problems:
Next
- For all new updates: Subscribe
9. Modified Binary Search
Modified Binary Search pattern adapts binary search to solve a wider range of problems, such as finding elements in rotated sorted arrays.
Use this pattern for problems involving sorted or rotated arrays where you need to find a specific element.
Sample Problem:
Find an element in a rotated sorted array.
Example:
- Input:
nums = [4, 5, 6, 7, 0, 1, 2],target = 0 - Output:
4
Explanation:
- Perform binary search with an additional check to determine which half of the array is sorted.
- We then check if the target is within the range of the sorted half.
- If it is, we search that half; otherwise, we search the other half.
LeetCode Problems:
Next
- For all new updates: Subscribe
10. Binary Tree Traversal
Binary Tree Traversal involves visiting all the nodes in a binary tree in a specific order.
- PreOrder:
root -> left -> right - InOrder:
left -> root -> right - PostOrder:
left -> right -> root
Sample Problem:
Problem Statement: Perform inorder traversal of a binary tree.
Example:
- Input:
root = [1, null, 2, 3] - Output:
[1, 3, 2]
Explanation:
- Inorder traversal visits nodes in the order: left, root, right.
- Use recursion or a stack to traverse the tree in this order.
LeetCode Problems:
- PreOrder → Binary Tree Paths (LeetCode #257)
- InOrder → Kth Smallest Element in a BST (LeetCode #230)
- PostOrder → Binary Tree Maximum Path Sum (LeetCode #124)
Next
- For all new updates: Subscribe
11. Depth-First Search (DFS)
Depth-First Search (DFS) is a traversal technique that explores as far down a branch as possible before backtracking.
Use this pattern for exploring all paths or branches in graphs or trees.
Sample Problem:
Find all paths from the root to leaves in a binary tree.
Example:
- Input:
root = [1, 2, 3, null, 5] - Output:
["1->2->5", "1->3"]
Explanation:
- Use recursion or a stack to traverse each path from the root to the leaves.
- Record each path as you traverse.
LeetCode Problems:
Next
- For all new updates: Subscribe
12. Breadth-First Search (BFS)
Breadth-First Search (BFS) is a traversal technique that explores nodes level by level in a tree or graph.
Use this pattern for finding the shortest paths in unweighted graphs or level-order traversal in trees.
Sample Problem:
Perform level-order traversal of a binary tree.
Example:
- Input:
root = [3, 9, 20, null, null, 15, 7] - Output:
[[3], [9, 20], [15, 7]]
Explanation:
- Use a queue to keep track of nodes at each level.
- Traverse each level and add the children of the current nodes to the queue.
LeetCode Problems:
Next
- For all new updates: Subscribe
13. Matrix Traversal
Matrix Traversal involves traversing elements in a matrix using different techniques (DFS, BFS, etc.).
Use this pattern for problems involving traversing 2D grids or matrices horizontally, vertically or diagonally.
Sample Problem:
Perform flood fill on a 2D grid. Change all the cells connected to the starting cell to new color.
Example:
- Input:
image = [[1,1,1],[1,1,0],[1,0,1]],sr = 1,sc = 1,newColor = 2 - Output:
[[2,2,2],[2,2,0],[2,0,1]]
Explanation:
- Use DFS or BFS to traverse the matrix starting from the given cell.
- Change the color of the connected cells to the new color.
LeetCode Problems:
Next
- For all new updates: Subscribe
14. Backtracking
Backtracking explores all possible solutions and backtracks when a solution path fails.
Use this pattern when you need to find all (or some) solutions to a problem that satisfies given constraints. For example: combinatorial problems, such as generating permutations, combinations, or subsets.
Sample Problem:
Generate all permutations of a given list of numbers.
Example:
- Input:
nums = [1, 2, 3] - Output:
[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
Explanation:
- Use recursion to generate permutations.
- For each element, include it in the current permutation and recursively generate the remaining permutations.
- Backtrack when all permutations for a given path are generated.
LeetCode Problems:
Next
- For all new updates: Subscribe
15. Dynamic Programming Patterns
Dynamic Programming (DP) involves breaking down problems into smaller subproblems and solving them using a bottom-up or top-down approach.
Use this pattern for problems with overlapping subproblems and optimal substructure.
DP itself has multiple sub-patterns. Some of the most important ones are:
- Fibonacci Numbers
- 0/1 Knapsack
- Longest Common Subsequence (LCS)
- Longest Increasing Subsequence (LIS)
- Subset Sum
- Matrix Chain Multiplication
Sample Problem:
Calculate the n-th Fibonacci number.
Example:
- Input:
n = 5 - Output:
5(The first five Fibonacci numbers are 0, 1, 1, 2, 3, 5)
Explanation:
- Use a bottom-up approach to calculate the n-th Fibonacci number.
- Start with the first two numbers (0 and 1) and iterate to calculate the next numbers like
(dp[i] = dp[i - 1] + dp[i - 2]).
LeetCode Problems:
For all new updates: Subscribe
— — — — — — — — — —
If you like the article and would like to support me, make sure to:
- 👏 Clap for the story (1000 claps) to help this featured — I will add more information on 1000+1 clap
- For all new updates: Subscribe
- 📰 View more content on my medium profile
- 🔔 Follow Me: LinkedIn | Youtube | GitHub | Website
— — — — — — — — — —
