common patterns
Data structures --
Arrays
Prefix Sum: Used for efficiently querying the sum of elements in a subarray
Sliding Window: Optimizes problems involving subarrays with constraints.
Two Pointers: Useful for searching pairs, merging, or removing duplicates in sorted arrays.
Binary Search: Efficiently finds elements or conditions in sorted arrays.
Kadane Algorithm: Finds the maximum sum subarray in linear time.
Merge Intervals: Helps in problems involving overlapping intervals.
Linked list
Fast and Slow Pointers: A variant of the two-pointer approach, useful for detecting cycles in linked lists.
Linked List In-Place Reversal: Focuses on modifying linked lists without using extra space
Merge Two Sorted Lists: Frequently used in sorting-related linked list problems.
Detect and Remove Loop: Detects and removes cycles using Floyd’s Cycle Detection.
Hashing
HashMap for Counting Frequency: Efficiently counts occurrences of elements.
Two Sum using HashMap: Finds pairs in an array that sum to a target.
Longest Subarray with Given Sum: Uses prefix sum and hashing.
Anagram Grouping: Groups words with the same frequency of letters.
Stack/Queues
Monotonic Stack: Finds the next greater or smaller element in an array.
Stack for Balanced Parentheses: Validates expressions containing parentheses.
Queue for Sliding Window Maximum: Uses a deque to maintain maximum values efficiently.
Min/Max Stack: Stack that supports retrieving min/max in O(1) time.
Binary tree
DFS (Depth-First Search): Visits all nodes by going deep first, commonly used in tree traversals.
BFS (Breadth-First Search): Explores all nodes level by level, useful for shortest path problems.
Recursive Tree Traversals: Preorder, Inorder, Postorder traversals.
Lowest Common Ancestor (LCA): Finds the lowest common ancestor of two nodes.
Binary seacrh tree
Inorder Traversal for Sorted Order: Retrieves elements in sorted order.
Insert/Delete/Search in O(log n): Uses the BST properties for efficient operations.
Kth Smallest/Largest Element: Uses inorder traversal for ranking elements.
Heap
Top K Elements: Identifies the K largest, smallest, or most frequent elements.
Priority Queue for Scheduling: Useful for scheduling tasks with priority.
Heap Sort: Sorting using a heap.
Median of a Stream: Uses two heaps to efficiently find the median.
Graph
DFS (Depth-First Search): Explores paths deeply before backtracking.
BFS (Breadth-First Search): Explores neighbors first, used for shortest path problems.
Dijkstra’s Algorithm: Finds the shortest path in weighted graphs.
Topological Sorting: Used for ordering tasks based on dependencies.
Union-Find (Disjoint Set Union - DSU): Detects cycles and connected components.
Tries
Auto-Complete System: Efficiently suggests words based on prefixes.
Word Search & Dictionary Problems: Stores words efficiently for searching.
Longest Common Prefix: Finds the common prefix of a set of words.
Counting Prefixes: Counts how many words start with a given prefix.
Algorithms --
Sorting —
Merge Sort: Efficient divide-and-conquer sorting algorithm with O(n log n) complexity.
Quick Sort: Uses partitioning to sort an array efficiently.
Counting Sort: Works well for sorting integers with a known range.
Bucket Sort: Useful when the input is uniformly distributed over a range.
Radix Sort: Sorts numbers digit by digit for efficiency.
Sort by Custom Comparator: Sorting based on custom rules, useful in problems with sorting constraints.
Binary search --
use (this stops the stack overflow)
happend only in sorted arrays
Common pattern
based on the greater than equal condition change the if condition and point the left and right value to different value
Overlapping Intervals: Useful for problems involving intervals or ranges that may overlap, such as merging intervals
Search in a Sorted Array: Classic application of binary search.
Finding Lower/Upper Bound: First occurrence (lower bound) or next larger element (upper bound).
Search in Rotated Sorted Array: Modified binary search for rotated arrays.
Binary Search on Answer: Used in optimization problems, e.g., minimum maximum value.
Search in 2D Matrix: Applying binary search in a row-wise and column-wise sorted matrix.
Recursion
Divide and Conquer: Solving problems by recursively dividing into subproblems (e.g., Merge Sort, Quick Sort).
Recursive Tree Traversals: Inorder, Preorder, Postorder traversals.
Subset Generation: Generating all subsets using recursion.
Tower of Hanoi: Classic recursion problem.
Fibonacci Series: Simple example of recursion with memoization for optimization.
Backtracking:
Explores all potential solution paths, backtracking when a path doesn't lead to a valid solution
Subset Sum: Finding subsets that sum up to a target.
N-Queens Problem: Placing N queens on an N×N chessboard without attacking each other.
Sudoku Solver: Filling a Sudoku board using backtracking.
Word Search in Grid: Searching for a word in a matrix using DFS.
Permutations and Combinations: Generating permutations and combinations of elements.
Topological Sort:
Arranges elements based on dependencies [04:32], helpful for prerequisite chains
Task Scheduling: Ordering tasks based on dependencies.
Course Schedule: Determining if courses can be completed based on prerequisites.
Alien Dictionary: Finding the order of letters in an alien language.
Dependency Resolution: Used in build systems to determine the order of compilation.
Bit-manipulation
Checking if a Number is Power of Two: Using bitwise AND.
Counting Set Bits: Counting the number of 1s in a binary representation.
XOR Tricks: Finding the unique element in a list where others appear twice.
Bit Masking for Subsets: Generating all subsets using bitwise operations.
Swapping Numbers Without a Temporary Variable: Using XOR.
Greedy algorithm
Activity Selection Problem: Selecting the maximum number of non-overlapping intervals.
Huffman Coding: Building an optimal prefix-free encoding.
Minimum Coins to Make Change: Finding the minimum number of coins for a target sum.
Fractional Knapsack: Choosing items to maximize profit with fractional choices.
Job Scheduling with Deadlines: Scheduling tasks with the highest profit.
Sliding window
Maximum Sum Subarray of Fixed Size: Finding the max sum of any k-length subarray.
Variable Size Sliding Window: Used in problems like longest substring with k distinct characters.
Minimum Window Substring: Finding the smallest substring containing all characters of another string.
Longest Substring Without Repeating Characters: Maintaining a window with unique characters.
Maximum of Every K-Size Subarray: Using a deque for efficiency.
DP
Knapsack Problem: 0/1 Knapsack and Fractional Knapsack.
Longest Common Subsequence (LCS): Finding the longest common sequence between two strings.
Longest Increasing Subsequence (LIS): Finding the longest increasing subsequence in an array.
Matrix Chain Multiplication: Parenthesizing a matrix multiplication sequence for minimal cost.
Coin Change Problem: Finding the minimum number of coins to make a target sum.
Fibonacci with Memoization: Optimized recursion using memoization.
DP on Trees: Solving tree-based DP problems.
Subset Sum Problem: Checking if a subset with a given sum exists.
Two-Pointer:
Iterates through a sorted array using two pointers effective for problems like finding pairs that sum to a target
Pair Sum in Sorted Array: Finding a pair that sums to a target in a sorted array.
Three Sum Problem: Finding triplets with a given sum.
Container with Most Water: Maximizing area between two heights in an array.
Sort Colors (Dutch National Flag Algorithm): Sorting an array with three distinct values.
Trapping Rain Water: Calculating trapped rainwater between heights efficiently.
Last updated