Leetcode patterns
- Prefix sum
Prefix Sum involves preprocessing an array to create a new array where each element at index
irepresents the sum of the array from the start up toi. 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.
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].
- 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.
Explanation:
Initialise 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.
- Sliding window
The Sliding Window pattern is used to find a subarray or substring that satisfies a specific condition, optimising the time complexity by maintaining a window of elements.
Use this pattern when dealing with problems involving contiguous subarrays or substrings.
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.
- Fast and slow pointers
The Fast & Slow Pointers (Tortoise and Hare) pattern is used to detect cycles in linked lists and other similar structures.
Explanation:
Initialise 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.
- Linked list in place reversal
The 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.
Explanation:
Identify the start and end of the sublist.
Reverse the nodes in place by adjusting the pointers.
- Monotonic stack
Find the next greater element for each element in an array. Output -1 if the greater element doesn’t exist.
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.
- Top K element
The Top 'K' Elements pattern finds the top k largest or smallest elements in an array or stream of data using heaps or sorting.
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.
- Overlapping intervals
The 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 ifb >= c(i.e., the end time of the first interval is greater than or equal to the start time of the second interval).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.
- Modified binary search
The 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.
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.
- Binary tree traversal
Binary Tree Traversal involves visiting all the nodes in a binary tree in a specific order.
PreOrder:
root -> left -> rightInOrder:
left -> root -> rightPostOrder:
left -> right -> root
Problem Statement: Perform inorder traversal of a binary tree.
Explanation:
Inorder traversal visits nodes in the order: left, root, right.
Use recursion or a stack to traverse the tree in this order.
- Dept first search
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.
Explanation:
Use recursion or a stack to traverse each path from the root to the leaves.
Record each path as you traverse.
- Breadth first search
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.
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.
- 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.
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.
- 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.
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.
- 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
- DP patterns
- Fibonacci Sequence
The Fibonacci sequence pattern is useful when the solution to a problem depends on the solutions of smaller instances of the same problem.
There is a clear recursive relationship, often resembling the classic Fibonacci sequence
F(n) = F(n-1) + F(n-2).LeetCode Problems:
- Kadane Algorithm
Kadane's Algorithm is primarily used for solving the Maximum Subarray Problem and its variations where the problem asks to optimize a contiguous subarray within a one-dimensional numeric array
LeetCode Problems:
- 0/1 Knapsack
The 0/1 Knapsack pattern is useful when:
You have a set of items, each with a weight and a value.
You need to select a subset of these items.
There's a constraint on the total weight (or some other resource) you can use.
You want to maximize (or minimize) the total value of the selected items.
Each item can be chosen only once (hence the "0/1" - you either take it or you don't).
LeetCode Problems:
- Unbounded Knapsack
The Unbounded Knapsack pattern is useful when:
You have a set of items, each with a weight and a value.
You need to select items to maximize total value.
There's a constraint on the total weight (or some other resource) you can use.
You can select each item multiple times (unlike 0/1 Knapsack where each item can be chosen only once).
The supply of each item is considered infinite.
LeetCode Problems:
- Longest Common subsequence (LCS)
The Longest Common Subsequence pattern is useful when you are given two sequences and need to find a subsequence that appears in the same order in both the given sequences.
LeetCode Problems:
Questions
longest common substring
print LCS
Shortes common subsequences
print SCS
Min # of insertion and deletions a -->b
largest repeating subsequences
Lengths of largest subsequence of a string which is substring in b.
Susbseqence pattern matching
count how many tries appear as subsequence in b.
largest palindromic susequence
largest palindromic substring
Count of palindromic substring
min no of deletion in a string to make it a palindrome
min no of insertions in a string to make it a palindrome.
- Longest Increasing Subsequence (LIS)
The Longest Increasing Subsequence pattern is used to solve problems that involve finding the longest subsequence of elements in a sequence where the elements are in increasing order.
LeetCode Problems:
- Palindromic subsequence
The Palindromic Subsequence pattern is used when solving problems that involve finding a subsequence within a sequence (usually a string) that reads the same forwards and backwards.
LeetCode Problems:
- EDIT distance
The Edit Distance pattern is used to solve problems that involve transforming one sequence (usually a string) into another sequence using a minimum number of operations.
The allowed operations typically include insertion, deletion, and substitution.
LeetCode Problems:
- Subset sum
The Subset Sum pattern is used to solve problems where you need to determine whether a subset of elements from a given set can sum up to a specific target value.
LeetCode Problems:
- String partition
The String Partition pattern is used to solve problems that involve partitioning a string into smaller substrings that satisfy certain conditions.
It’s useful when:
You're working with problems involving strings or sequences.
The problem requires splitting the string into substrings or subsequences.
You need to optimize some property over these partitions (e.g., minimize cost, maximize value).
The solution to the overall problem can be built from solutions to subproblems on smaller substrings.
There's a need to consider different ways of partitioning the string.
LeetCode Problems:
- Catalan Numbers
The Catalan Number pattern is used to solve combinatorial problems that can be decomposed into smaller, similar subproblems.
Some of the use-cases of this pattern include:
Counting the number of valid parentheses expressions of a given length
Counting the number of distinct binary search trees that can be formed with
nnodes.Counting the number of ways to triangulate a polygon with
n+2sides.
LeetCode Problems:
- Matrix chain multiplication
This pattern is used to solve problems that involve determining the optimal order of operations to minimize the cost of performing a series of operations.
It is based on the popular optimization problem: Matrix Chain Multiplication.
It’s useful when:
You're dealing with a sequence of elements that can be combined pairwise.
The cost of combining elements depends on the order of combination.
You need to find the optimal way to combine the elements.
The problem involves minimizing (or maximizing) the cost of operations of combining the elements.
LeetCode Problems:
Questions
MCM
printing MCM
evaluate exp to tree/boolean presentation
min/max value of an exp
palindrome partitioning
scramble string
egg droping problem
- Count distinct ways
This pattern is useful when:
You need to count the number of different ways to achieve a certain goal or reach a particular state.
The problem involves making a series of choices or steps to reach a target.
There are multiple valid paths or combinations to reach the solution.
The problem can be broken down into smaller subproblems with overlapping solutions.
You're dealing with combinatorial problems that ask "in how many ways" can something be done.
LeetCode Problems:
- DP on grids
The DP on Grids pattern is used to solve problems that involve navigating or optimizing paths within a grid (2D array).
For these problems, you need to consider multiple directions of movement (e.g., right, down, diagonal) and solution at each cell depends on the solutions of neighboring cells.
LeetCode Problems:
- DP on trees
The DP on Trees pattern is useful when:
You're working with tree-structured data represented by nodes and edges.
The problem can be broken down into solutions of subproblems that are themselves tree problems.
The problem requires making decisions at each node that affect its children or parent.
You need to compute values for nodes based on their children or ancestors.
LeetCode Problems:
QUESTIONS --
How DP can be applied to trees
Diameter of a binary tree
maximum path sum from any node to any
maximum path sum from leaf to leaf
diameter of n-ary tree
- DP on graphs
The DP on Graphs pattern is useful when:
You're dealing with problems involving graph structures.
The problem requires finding optimal paths, longest paths, cycles, or other optimized properties on graphs.
You need to compute values for nodes or edges based on their neighbors or connected components.
The problem involves traversing a graph while maintaining some state.
LeetCode Problems:
- Digit DP
The Digit DP Pattern is useful when:
You're dealing with problems involving counting or summing over a range of numbers.
The problem requires considering the digits of numbers individually.
You need to find patterns or properties related to the digits of numbers within a range.
The range of numbers is large (often up to 10^18 or more), making brute force approaches infeasible.
The problem involves constraints on the digits.
LeetCode Problems:
- Bit masking DP
The Bitmasking DP pattern is used to solve problems that involve a large number of states or combinations, where each state can be efficiently represented using bits in an integer.
It’s particularly useful when:
You're dealing with problems involving subsets or combinations of elements.
The total number of elements is relatively small (typically <= 20-30).
You need to efficiently represent and manipulate sets of elements.
The problem involves making decisions for each element (include/exclude) or tracking visited/unvisited states.
You want to optimize space usage in DP solutions.
LeetCode Problems:
- Probability DP
This pattern is useful when:
You're dealing with problems involving probability calculations.
The probability of a state depends on the probabilities of previous states.
You need to calculate the expected value of an outcome.
The problem involves random processes or games of chance.
LeetCode Problems:
- State machine DP
The State Machine DP Pattern is useful when when:
The problem can be modeled as a series of states and transitions between these states.
There are clear rules for moving from one state to another.
The optimal solution depends on making the best sequence of state transitions.
The problem involves making decisions that affect future states.
There's a finite number of possible states, and each state can be clearly defined.
LeetCode Problems:
Last updated