Coding Patterns: A Comprehensive Guide
Published:
This post includes some popular problems sorted according to the different patterns. This list excludes tree or graph related BFS and DFS, and dynamic programming. I feel that those topics require their own posts!
- Backtracking
- Greedy
- Bit Manipulation
- Two Pointers
- Trie
- 2 Heaps
- Cyclic Sort
- In-place reversal of LinkedList
- K way merge
- Merge Intervals
- Sliding Window
- Binary Search
- Monotonic Stack
Greedy Algorithmic Paradigm
Greedy algorithms make locally optimal choices at each step with the hope of finding a global optimum. They are often used when a problem can be solved by making a series of decisions that look best in the short term.
- Valid Palindrome II
- Reorganize String
- Container With Most Water
- Meeting Rooms II
- Valid Parenthesis String
- Bag of Tokens
- Wildcard Matching
- Strong Password Checker
- Largest Palindromic Number
- Frequency of the Most Frequent Element
- Best Time to Buy and Sell Stock II
- Boats to Save People
- Minimum Increment to Make Array Unique
- Largest Number
- Remove K Digits
Fixed Sliding Window
Sliding Window problems are useful when you need to calculate something over a range of elements in an array or string. In the fixed sliding window pattern, the window size is constant.
- Sliding Window Maximum
- Find All Anagrams in a String
- Permutation in String
- Maximum Average Subarray I
- Maximum Sum of Distinct Subarrays with Length K
Variable Sliding Window
In the variable sliding window pattern, the window size can change dynamically depending on the conditions of the problem.
- Longest Substring Without Repeated Characters
- Fruit Into Baskets
- Minimum Size Subarray Sum
- Subarray Product Less Than K
- Max Consecutive Ones III
Top K elements
Top K Elements problems typically require finding the Kth largest or smallest elements in a data structure. These problems are often solved using heaps, which allow for efficient extraction of the Kth largest or smallest elements.
- Kth Smallest element in a BST
- Kth Largest element in an Array
- Top K frequent elements
- Find K closest elements
- Reorganize String
- Sort characters by frequency
- Maximum frequency Stack
- Course Schedule III
K-Way merge
K-Way Merge problems typically involve merging K sorted lists or arrays. These problems are commonly solved using a min-heap, which allows for efficiently merging sorted data structures.
- Find K pairs with Smallest Sums
- Merge Two sorted Lists
- Merge K sorted Lists
- Kth smallest element in a sorted Matrix
- Smallest range covering elements from K lists
Merge Intervals
Merge Intervals problems involve working with intervals or ranges. The goal is often to merge overlapping intervals or find a range that satisfies specific criteria. These problems are generally solved by first sorting the intervals and then iterating through them.
- Merge Intervals
- Insert Interval
- Interval List Intersections
- Non-overlapping Intervals
- Meeting Rooms
- Meeting Rooms II
Cyclic Sort
Cyclic Sort is a pattern that involves sorting a list of numbers that range from 1 to n. The approach is based on placing each number at its correct index (i.e., number i at index i-1). This pattern is efficient for finding missing numbers, duplicates, or corrupt numbers in a given range.
- Cyclic Sort
- Find All Numbers Disappeared in an Array
- Find the Duplicate Number
- Find All Duplicates in an Array
- Set Mismatch
- First Missing Positive
In-Place Reversal of LinkedList
In-Place Reversal of LinkedList is a pattern where the linked list is reversed or modified without using extra space (in place). This pattern is useful for reversing a sublist, rotating the linked list, or detecting and removing cycles in the list.
- Reverse Linked List
- Reverse Linked List II
- Rotate List
- Reverse Nodes in k-Group
- Linked List Cycle
- Linked List Cycle II
Bit Manipulation
Bit Manipulation is a powerful technique used to solve problems by directly manipulating bits. This pattern is often used in problems involving sets, subsets, and certain arithmetic operations.
Binary Search
Binary Search is a pattern that involves dividing the search space in half with each step, typically used in sorted arrays or search problems. It’s a highly efficient way to solve problems with logarithmic time complexity.
- Binary Search
- Search in Rotated Sorted Array
- Find Minimum in Rotated Sorted Array
- Find Peak Element
- Median of Two Sorted Arrays
- Search a 2D Matrix
- Kth Smallest Element in a Sorted Matrix
Monotonic Stack
Monotonic Stack is a pattern where you maintain a stack with elements that are either entirely non-increasing or non-decreasing. This technique is useful for problems that require tracking the nearest larger or smaller elements.
- Largest Rectangle in Histogram
- Trapping Rain Water
- Daily Temperatures
- Next Greater Element I
- Next Greater Element II
- Sum of Subarray Minimums
Two Pointers
Two Pointers is a pattern that uses two pointers to traverse an array or list. It is often used in problems where you need to find pairs of elements that satisfy a certain condition, such as finding the pair of numbers that add up to a given sum.
- Two Sum
- 3Sum
- Container With Most Water
- Remove Nth Node From End of List
- Valid Palindrome
- Sort Colors
- Move Zeroes
Trie
A Trie is a specialized tree-like data structure used to store associative arrays where the keys are usually strings. Tries are used for efficient information retrieval, such as prefix searching.
- Implement Trie (Prefix Tree)
- Word Search II
- Replace Words
- Add and Search Word - Data structure design
- Maximum XOR of Two Numbers in an Array
- Design Search Autocomplete System
- Map Sum Pairs
2 Heaps
The 2 Heaps pattern is useful for solving problems where you need to find the median of a data stream or maintain the smallest/largest K elements in a dataset. Typically, a min-heap and a max-heap are used together.
- Find Median from Data Stream
- Sliding Window Median
- IPO
- Smallest Range Covering Elements from K Lists
- Kth Largest Element in a Stream
- Find Right Interval
Backtracking
Backtracking is a technique for solving problems recursively by building a solution incrementally, one piece at a time, and removing those solutions that fail to satisfy the problem’s constraints.