Algorithm Patterns Roadmap
36 sections • 696 topics
- 1. Fixed-size Window Techniques
- Example: Maximum sum of k consecutive elements
- 2. Variable-size Window Optimization
- Example: Smallest subarray with sum ≥ target
- 3. Maximum/Minimum Subarray Problems
- Example: Sliding Window Maximum
- Example: Maximum Product Subarray
- 4. Longest Substring Without Repeating Characters
- Example: Longest substring without repeating characters
- Example: Longest substring with k distinct characters
- 5. Two-pointer Sliding Window Hybrid Approach
- Example: Container with most water (opposite direction)
- 6. Time Complexity O(n) Analysis
- Sliding Window Pattern Summary
- 1. Opposite Ends Technique (left and right pointers)
- Example: Two sum in sorted array
- Example: Valid palindrome
- 2. Fast and Slow Pointers (Floyd's Cycle Detection)
- Example: Detect cycle in linked list
- Example: Find middle of linked list
- Example: Find cycle start position
- 3. In-place Array Manipulation O(1) Space
- Example: Remove duplicates from sorted array
- Example: Move zeros to end
- Example: Sorted squares with negative numbers
- 4. Partitioning and Sorting Techniques
- Example: Dutch National Flag (Sort colors)
- Example: Partition array around pivot
- 5. Collision Detection Patterns
- Example: Remove nth node from end of list
- 6. Space Optimization O(1) Complexity
- Example: Reverse string in-place
- Two Pointers Pattern Summary
- 1. Basic Prefix Sum Implementation
- Example: Range sum query using prefix sum
- Example: Subarray sum equals k (prefix sum with HashMap)
- 2. 2D Prefix Sum for Matrix Range Queries
- Example: 2D range sum query (immutable matrix)
- 3. Difference Array for Range Updates
- Example: Range addition using difference array
- Example: Corporate flight bookings
- 4. Range Query Optimization Techniques
- Immutable Range Queries
- Mutable Range Queries
- Example: Product of array except self (prefix/suffix product)
- 5. Prefix XOR and Bitwise Operations
- Example: XOR queries of a subarray
- Example: Count triplets with XOR equal to zero
- 6. Memory-efficient Prefix Sum Calculations
- Example: Running sum with O(1) space
- Example: Max sum with rolling variables
- Prefix Sum Pattern Summary
- 1. Classic Binary Search Template O(log n)
- Example: Classic binary search (find exact target)
- Example: Recursive binary search
- 2. Lower Bound and Upper Bound Implementation
- Example: Lower bound (first >= target)
- Example: Upper bound (first > target)
- Example: Find first and last position of element
- 3. Search in Rotated Sorted Array
- Example: Search in rotated sorted array
- Example: Find minimum in rotated sorted array
- 4. Binary Search on Answer Space Pattern
- Example: Koko eating bananas (minimize eating speed)
- Example: Capacity to ship packages within D days
- 5. Floating Point Binary Search Precision
- Example: Square root with precision
- Example: Find peak element with fixed iterations
- 6. Binary Search Edge Cases and Debugging
- Example: Debugging template with invariant comments
- Binary Search Pattern Summary
- 1. Cycle Detection in Linked Lists
- Example: Floyd's cycle detection algorithm
- Example: Alternative with HashSet (for comparison)
- 2. Find Middle of Linked List
- Example: Find middle node
- Example: Delete middle node
- 3. Palindrome Linked List Verification
- Example: Check if linked list is palindrome
- 4. Intersection of Two Linked Lists
- Example: Find intersection node (elegant two-pointer)
- Example: Intersection with length calculation
- 5. Duplicate Detection in Arrays O(1) Space
- Example: Find duplicate number using Floyd's algorithm
- 6. Find Starting Point of Cycle
- Example: Find cycle start position
- Example: Find cycle length
- Floyd's Algorithm Variations
- Why Floyd's Algorithm Works
- 1. Merge Overlapping Intervals Pattern
- Example: Merge overlapping intervals
- 2. Insert Interval Optimization
- Example: Insert interval into sorted intervals
- 3. Interval Intersection Logic
- Example: Interval list intersections (two sorted lists)
- 4. Meeting Rooms Scheduling Problem
- Example: Can attend all meetings?
- Example: Minimum meeting rooms needed
- Example: Meeting rooms II with min heap (alternative)
- 5. Non-overlapping Intervals Greedy Approach
- Example: Minimum number of intervals to remove
- Example: Maximum non-overlapping intervals (activity selection)
- 6. Timeline Event Processing Pattern
- Example: Employee free time (flatten and find gaps)
- Example: Sweep line for maximum concurrent events
- Merge Intervals Pattern Summary
- 1. Place Elements in Correct Index
- Example: Cyclic sort for range [1, n]
- Example: Cyclic sort for range [0, n-1]
- 2. Find Missing Numbers O(n) Time
- Example: Find missing number (single)
- Example: Find all missing numbers
- 3. Find Duplicates O(1) Space Complexity
- Example: Find duplicate number
- Example: Find all duplicates
- Example: Find duplicates without modification (index marking)
- 4. Corrupt Pairs Detection Pattern
- Example: Find corrupt pair (set mismatch)
- 5. First Missing Positive Integer Problem
- Example: First missing positive integer
- 6. Range Validation Techniques
- Example: Safe cyclic sort with validation
- Example: Validation for edge cases
- Cyclic Sort Pattern Summary
- 1. Kth Largest Element (QuickSelect Algorithm)
- Example: Kth largest using min heap
- Example: Kth largest using QuickSelect
- 2. K Closest Points to Origin
- Example: K closest points using max heap
- 3. Top K Frequent Elements (HashMap + Heap)
- Example: K frequent using min heap
- Example: K frequent using bucket sort
- 4. QuickSelect Partition Algorithm O(n) Average
- Example: QuickSelect with random pivot
- Example: QuickSelect with median-of-3 pivot
- 5. Merge K Sorted Lists (Min Heap)
- Example: Merge K sorted lists
- Example: K pairs with smallest sums
- 6. Bucket Sort for Top K Elements
- Example: Top K frequent using bucket sort
- Example: Sort characters by frequency using buckets
- Top K Elements Pattern Summary
- 1. Level Order Traversal (Queue-based BFS)
- Example: Binary tree level order traversal
- Example: Graph level order BFS
- Example: Right side view of tree
- 2. Multi-source BFS Pattern
- Example: Rotting oranges (multi-source BFS)
- Example: 0-1 matrix (distance to nearest 0)
- 3. Shortest Path in Unweighted Graph (BFS)
- Example: Shortest path in unweighted graph
- Example: Word ladder (shortest transformation)
- 4. Cycle Detection Using DFS (Graph Coloring)
- Example: Detect cycle in directed graph (DFS coloring)
- Example: Course schedule (cycle detection)
- 5. Bidirectional BFS Optimization
- Example: Bidirectional BFS for shortest path
- 6. DFS Iterative Implementation (Stack)
- Example: DFS recursive
- Example: DFS iterative with stack
- Example: DFS iterative with pre/post-order tracking
- 7. Flood Fill Algorithm Pattern
- Example: Flood fill DFS
- Example: Flood fill BFS
- Example: Number of islands (flood fill variant)
- BFS DFS Graph Traversal Summary
- 1. Generate All Subsets (Powerset)
- Example: Subsets using backtracking
- Example: Subsets using bit manipulation
- Example: Subsets with duplicates
- 2. Permutations and Next Lexicographic Order
- Example: Permutations using backtracking
- Example: Permutations with swap
- Example: Next lexicographic permutation
- 3. N-Queens Problem Solution
- Example: N-Queens solution
- Example: N-Queens count only
- 4. Sudoku Solver Backtracking
- Example: Sudoku solver
- 5. Combination Sum Problem
- Example: Combination sum (unlimited reuse)
- Example: Combination sum II (use once)
- 6. Word Search in 2D Grid (DFS Backtracking)
- Example: Word search in grid
- Example: Word search II (multiple words with Trie)
- 7. Palindrome Partitioning Problem
- Example: Palindrome partitioning
- Example: Palindrome partitioning with DP optimization
- Backtracking Pattern Summary
- 1. Merge Sort Algorithm O(n log n)
- Example: Merge sort implementation
- Example: Count inversions using merge sort
- 2. Quick Sort Partition Strategy
- Example: Quick sort with Lomuto partition
- Example: Quick sort with Hoare partition
- Example: 3-way partition (Dutch National Flag)
- 3. Binary Tree Divide and Conquer
- Example: Tree height/depth
- Example: Balanced binary tree
- Example: Binary tree diameter
- Example: Lowest common ancestor (LCA)
- 4. Closest Pair of Points Problem
- Example: Closest pair of points
- 5. Maximum Subarray (Divide and Conquer)
- Example: Maximum subarray divide and conquer
- 6. Karatsuba Multiplication Algorithm
- Example: Karatsuba multiplication
- Example: String-based Karatsuba for very large numbers
- Divide and Conquer Summary
- 1. Tree Recursion Patterns
- Example: Binary tree recursion
- Example: N-ary tree recursion
- Example: Tree recursion with return value
- 2. Tail Recursion Optimization
- Example: Non-tail recursive factorial
- Example: Tail recursive factorial
- Example: Converting to iterative (guaranteed O(1) space)
- 3. Recursion Tree Complexity Analysis
- Example: Fibonacci recursion tree analysis
- Example: Master Theorem applications
- 4. Memoization (Top-Down DP)
- Example: Fibonacci with memoization
- Example: Climbing stairs memoized
- Example: Longest increasing subsequence (LIS) memoized
- 5. Recursive Data Structures
- Example: Recursive linked list operations
- Example: Recursive tree construction
- 6. Mutual Recursion Patterns
- Example: Even/odd mutual recursion
- Example: Expression parser mutual recursion
- Example: State machine mutual recursion
- Recursion Patterns Summary
- 1. 0/1 Knapsack Problem (Space Optimization)
- Example: 0/1 Knapsack 2D DP
- Example: 0/1 Knapsack 1D optimized
- Example: Partition equal subset sum (0/1 knapsack variant)
- 2. Unbounded Knapsack (Bottom-Up DP)
- Example: Unbounded knapsack
- Example: Coin change (ways to make amount)
- Example: Rod cutting problem
- 3. Longest Common Subsequence (LCS Algorithm)
- Example: Longest common subsequence
- Example: LCS with path reconstruction
- Example: Space-optimized LCS O(min(m,n))
- 4. Longest Increasing Subsequence (LIS O(n log n))
- Example: LIS with O(n²) DP
- Example: LIS with binary search O(n log n)
- Example: LIS with reconstruction
- 5. Coin Change Minimum Coins Problem
- Example: Coin change minimum coins
- Example: Coin change with path
- Example: Coin change II (count ways)
- 6. Palindromic Substrings (Expand Around Centers)
- Example: Count palindromic substrings
- Example: Longest palindromic substring
- Example: Palindromic substrings DP approach
- 7. Edit Distance (Levenshtein Distance Algorithm)
- Example: Edit distance (Levenshtein distance)
- Example: Space-optimized edit distance
- Example: One edit distance
- 8. Maximum Subarray Sum (Kadane's Algorithm)
- Example: Kadane's algorithm
- Example: Kadane with indices
- Example: Circular array maximum subarray
- 9. House Robber Problem (DP State Transitions)
- Example: House robber I
- Example: House robber II (circular)
- Example: House robber III (binary tree)
- 1. 0/1 Knapsack Problem (Space Optimization)
- Example: Binary tree diameter
- Example: Binary tree maximum path sum
- Example: Count good nodes in tree
- 1. 0/1 Knapsack Problem (Space Optimization)
- Example: Traveling salesman problem (TSP)
- Example: Minimum cost to connect all points (Steiner tree)
- Example: Partition into k equal sum subsets
- 1. 0/1 Knapsack Problem (Space Optimization)
- Example: Matrix chain multiplication
- Example: Burst balloons
- Example: Palindrome partitioning II
- 1. Activity Selection Problem (Interval Scheduling)
- Example: Activity Selection
- 2. Jump Game Reachability Problem
- Example: Jump Game I - Can Reach End
- Example: Jump Game II - Minimum Jumps
- 3. Gas Station Problem (Circular Array)
- Example: Gas Station Circuit
- 4. Interval Scheduling Maximization
- Example: Minimum Interval Removals
- Example: Minimum Meeting Rooms
- 5. Job Sequencing with Deadlines
- Example: Job Sequencing Problem
- Example: Job Sequencing with Disjoint Set (Optimized)
- 6. Greedy Choice Property Proof
- Example: Proving Greedy Choice - Fractional Knapsack
- When Greedy Works
- Example: Huffman Coding (Greedy Correctness)
- Summary: Greedy Algorithm Pattern
- 1. Bitmasking for Subset Enumeration
- Example: Generate All Subsets Using Bitmask
- 2. Generate All Subsets Using Bits
- Example: Iterate All Submasks of a Mask
- Example: DP with Bitmask - Traveling Salesman Problem
- 3. Counting Set Bits (Brian Kernighan's Algorithm)
- Example: Brian Kernighan's Algorithm
- Example: Count Bits for All Numbers 0 to n (DP)
- 4. XOR Patterns (Single Number Problem)
- Example: Single Number - Find Unique Element
- Example: Single Number II - Element Appears Thrice
- Example: Single Number III - Two Unique Elements
- 5. Bit Manipulation Tricks and Fast Operations
- Example: Common Bit Tricks
- Example: Fast Modulo and Multiplication
- 6. Hamming Distance (Bit Difference Count)
- Example: Hamming Distance Between Two Numbers
- Example: Total Hamming Distance of Array
- 7. Check Power of Two Using Bits
- Example: Power of Two Variations
- Example: Find Missing Power of Two
- 8. Gray Code Generation Algorithm
- Example: Generate Gray Code Sequence
- Example: Gray Code Conversion
- 9. Gosper's Hack (Next Combination with Same Set Bits)
- Example: Gosper's Hack - Enumerate k-Combinations
- Example: Apply Gosper's Hack to Array
- 1. Bitmasking for Subset Enumeration
- Example: Reverse 32-bit Integer
- Example: Bit Reversal Variants
- Summary: Bit Manipulation Pattern
- 1. Spiral Matrix Traversal Pattern
- Example: Spiral Matrix Traversal
- Example: Generate Spiral Matrix
- 2. Search in 2D Sorted Matrix (Staircase Algorithm)
- Example: Search in Row and Column Sorted Matrix
- Example: Search in Fully Sorted Matrix (2D Binary Search)
- Staircase Search Visualization
- 3. Number of Islands (DFS/BFS)
- Example: Number of Islands (DFS)
- Example: Number of Islands (BFS)
- Example: Max Area of Island
- 4. Rotate Matrix 90 Degrees In-place
- Example: Rotate Matrix 90° Clockwise
- Example: Rotate 90° Counter-Clockwise
- Example: Layer-by-Layer Rotation
- Rotation Formulas
- 5. Shortest Path in Grid (A* Algorithm)
- Example: Shortest Path in Binary Grid (BFS)
- Example: A* Search with Manhattan Heuristic
- 6. Diagonal Traversal of Matrix
- Example: Diagonal Traversal (Zigzag)
- Example: Process All Diagonals
- Example: Check Diagonal and Anti-Diagonal Sums
- Summary: Matrix Traversal Pattern
- 1. Longest Substring Without Repeating Characters
- Example: Longest Substring Without Repeating Characters
- Example: Alternative Using Set
- 2. Longest Palindromic Substring (Manacher's Algorithm)
- Example: Expand Around Center
- Example: Manacher's Algorithm (Linear Time)
- 3. Minimum Window Substring (Sliding Window)
- Example: Minimum Window Substring
- Example: Simplified Version with Character Array
- Window Validity Criteria
- 4. Group Anagrams Pattern
- Example: Group Anagrams Using Sorted Key
- Example: Using Character Count as Key
- Example: Related Problems - Valid Anagram
- 5. String Permutation in String Check
- Example: Check Permutation in String
- Example: Generate All Permutations
- 6. Longest Repeating Character Replacement Problem
- Example: Longest Repeating Character Replacement
- Example: Alternative with Explicit Max Count Update
- Summary: String Matching Pattern
- 1. Next Greater Element (Stack Pattern)
- Example: Next Greater Element
- Example: Next Greater Element II (Circular Array)
- Example: Next Greater Element I (Subset Problem)
- 2. Next Smaller Element Pattern
- Example: Next Smaller Element
- Monotonic Stack Patterns
- 3. Largest Rectangle in Histogram
- Example: Largest Rectangle in Histogram
- Example: Using Previous and Next Smaller Arrays
- Example: Maximal Rectangle in Binary Matrix
- 4. Sliding Window Maximum (Deque)
- Example: Sliding Window Maximum Using Deque
- Example: Min and Max in Sliding Window
- 5. Stock Span Problem
- Example: Stock Span
- Example: Online Stock Span (Class Design)
- 6. Trapping Rain Water Problem
- Example: Trapping Rain Water (Two Pointers)
- Example: Trapping Rain Water (Monotonic Stack)
- Example: Trapping Rain Water II (2D Grid)
- Summary: Monotonic Stack Queue Pattern
- 1. Interval Merging Using Sweep Line
- Example: Merge Overlapping Intervals
- Example: Insert Interval
- 2. Meeting Rooms with Multiple Events
- Example: Meeting Rooms I - Can Attend All
- Example: Meeting Rooms II - Minimum Rooms
- Example: Employee Free Time
- 3. Skyline Problem (Event Points)
- Example: Skyline Problem
- 4. Rectangle Overlap Detection
- Example: Rectangle Overlap (2 Rectangles)
- Example: Rectangle Area (Union of Two Rectangles)
- Example: Rectangle Area II (Union of Multiple Rectangles)
- 5. Event-driven Processing Pattern
- Example: Task Scheduler with Cooldown
- Example: Car Fleet (Event-driven)
- Example: The Earliest Moment When Everyone Becomes Friends
- Summary: Line Sweep Scanline Pattern
- 1. Two Array Sum Combination Problem
- Example: Find if subset sum equals target using two arrays
- 2. Subset Sum Using Split Search
- Example: Count number of subsets with given sum
- 3. Closest Subset Sum Problem
- Example: Find subset sum closest to target
- 4. 4Sum Problem Optimization
- Example: 4Sum using Meet in the Middle
- Example: 4Sum using Two Pointers (Optimal)
- 5. Exponential to Polynomial Time Reduction
- Example: Partition array into two subsets with minimum difference
- Example: Comparison of complexities
- Summary: Meet in the Middle Pattern
- 1. Range Query Using Block Division
- Example: Range sum query with updates
- 2. Mo's Algorithm (Query Ordering)
- Example: Mo's Algorithm - Distinct elements in ranges
- 3. Update vs Query Time Trade-off
- Example: Range minimum with updates
- Complexity Comparison
- 4. Sqrt Decomposition on Arrays
- Example: Range GCD queries
- 5. Block-wise Processing Pattern
- Example: Range add with lazy propagation
- Example: Mo's Algorithm with modifications
- Summary: Square Root Decomposition Pattern
- 1. Reverse Linked List (Iterative and Recursive)
- Example: Iterative reversal
- Example: Recursive reversal
- Example: Reverse sublist [m, n]
- 2. Merge Two Sorted Linked Lists
- Example: Merge iterative with dummy
- Example: Merge recursive
- 3. Remove Nth Node From End of List
- Example: Remove Nth from end (one pass)
- 4. Reorder Linked List Pattern
- Example: Reorder list (L0→Ln→L1→Ln-1...)
- 5. Copy List with Random Pointer (Deep Copy)
- Example: Copy using hash map
- Example: Copy with O(1) space (interleaving)
- 6. Flatten Multilevel Doubly Linked List
- Example: Flatten doubly linked list with child pointer
- Example: Flatten recursive approach
- Summary: Linked List Manipulation Patterns
- 1. Morris Inorder Traversal O(1) Space
- Example: Morris inorder traversal
- Example: Morris preorder and postorder
- 2. Level Order Traversal Bottom-Up
- Example: Bottom-up level order (BFS + reverse)
- Example: Bottom-up using DFS
- 3. Vertical Order Traversal of Binary Tree
- Example: Vertical order traversal with sorting
- 4. Boundary Traversal of Binary Tree
- Example: Binary tree boundary traversal
- 5. Zigzag Level Order Traversal
- Example: Zigzag with BFS and reverse
- Example: Zigzag with two stacks
- 6. Serialize and Deserialize Binary Tree
- Example: Serialize/deserialize with preorder
- Example: Serialize/deserialize with BFS
- Summary: Tree Traversal Patterns
- 1. Search in 2D Matrix (Binary Search)
- Example: Search in fully sorted 2D matrix
- Example: Search in row/col sorted matrix
- 2. Find Peak Element Problem
- Example: Find peak element
- 3. Search in Rotated Sorted Array
- Example: Search in rotated sorted array
- 4. Find Minimum in Rotated Sorted Array
- Example: Find minimum (no duplicates)
- Example: Find minimum (with duplicates)
- 5. Search Insert Position in Array
- Example: Search insert position (lower bound)
- Example: Lower and upper bound templates
- 6. Find First and Last Position in Sorted Array
- Example: Find first and last position
- Example: Using lower/upper bound approach
- Summary: Modified Binary Search Patterns
- 1. Reverse Linked List In-place O(1) Space
- Example: Reverse entire linked list iteratively
- 2. Reverse Linked List Sublist Pattern
- Example: Reverse between positions m and n
- 3. Reverse Nodes in K-Group
- Example: Reverse nodes in k-group
- Example: Reverse k-group iteratively
- 4. Rotate Linked List Pattern
- Example: Rotate list right by k places
- 5. Swap Nodes in Pairs (Linked List)
- Example: Swap pairs iteratively
- Example: Swap pairs recursively
- Example: General swap every k nodes
- Summary: In-place Reversal Patterns
- 1. Generate All Subsets (Powerset)
- Example: Backtracking approach
- Example: Iterative build approach
- Example: Bit manipulation approach
- 2. Subsets with Duplicate Elements
- Example: Subsets with duplicates
- 3. Combinations of K Elements
- Example: Combinations C(n, k)
- Example: Pascal's triangle approach
- 4. Combination Sum Problem Variations
- Example: Combination Sum I (unlimited reuse)
- Example: Combination Sum II (each once, has duplicates)
- Example: Combination Sum IV (order matters - DP)
- 5. Letter Combinations of Phone Number
- Example: Backtracking approach
- Example: Iterative build approach
- Example: BFS queue approach
- Summary: Subsets and Combinations Patterns
- 1. Course Schedule Problem (Kahn's Algorithm)
- Example: DFS cycle detection
- Example: Kahn's algorithm (BFS)
- Example: Course Schedule II - return topological order
- 2. Alien Dictionary Problem (Character Order)
- Example: Alien dictionary character order
- 3. Build Order with Dependencies
- Example: Lexicographically smallest topological order
- Example: Group by parallel execution levels
- 4. All Topological Orderings of DAG
- Example: Generate all topological orderings
- 5. Sequence Reconstruction Verification
- Example: Verify sequence reconstruction
- Example: Alternative - check pairs coverage
- Summary: Topological Sort Patterns
- 1. Minimum Meeting Rooms Required
- Example: Min heap approach
- Example: Chronological ordering
- Example: Sweep line with events
- 2. Employee Free Time Problem
- Example: Flatten and merge approach
- Example: Priority queue k-way merge
- 3. Interval List Intersections
- Example: Two pointers intersection
- Example: Visualizing intersection logic
- 4. Insert Interval and Merge
- Example: Insert and merge interval
- Example: Alternative approach with three passes
- 5. Task Scheduler Problem (Greedy)
- Example: Greedy formula approach
- Example: Heap simulation approach
- Summary: Interval Scheduling Patterns
- 1. Valid Parentheses Using Stack
- Example: Stack-based validation
- Example: Cleaner with early returns
- Example: Optimized for single bracket type
- 2. Generate Parentheses (Backtracking)
- Example: Backtracking generation
- Example: Alternative with explicit tracking
- 3. Longest Valid Parentheses (DP Solution)
- Example: DP approach
- Example: Stack approach
- Example: Two-pass O(1) space
- 4. Remove Invalid Parentheses (BFS)
- Example: BFS with early termination
- Example: Backtracking with counting
- 5. Minimum Add to Make Valid Parentheses
- Example: Counter approach
- Example: Balance tracking
- Example: Related problem - make valid with moves
- Summary: Parentheses Problems Patterns
- 1. Random Pick from Stream (Reservoir Sampling)
- Example: Single item reservoir sampling
- Example: Alternative with random index
- 2. Random Node from Linked List
- Example: Reservoir sampling approach
- Example: Array conversion approach
- 3. Random Pick with Weight (Weighted Sampling)
- Example: Prefix sum with binary search
- Example: Visualizing the probability distribution
- 4. Shuffle Array (Fisher-Yates Algorithm)
- Example: Fisher-Yates shuffle
- Example: Forward version
- Example: Shuffle class for reset functionality
- 5. Sample K Items Uniformly from Stream
- Example: Reservoir sampling for k items
- Example: Partial Fisher-Yates
- Example: Optimized with index set
- Summary: Reservoir Sampling Patterns
- 1. Rabin-Karp String Matching Pattern
- Example: Rabin-Karp pattern matching
- Example: Simplified rolling hash update
- 2. Repeated DNA Sequences Problem
- Example: Rolling hash approach
- Example: Bit encoding optimization
- 3. Longest Duplicate Substring Problem
- Example: Binary search with rolling hash
- 4. Find All Anagrams in String
- Example: Frequency array sliding window
- Example: Optimized with match counter
- 5. Polynomial Rolling Hash Function
- Example: Double hash to reduce collisions
- Example: Polynomial hash implementation details
- Summary: Rolling Hash Patterns
- 1. Minimax Algorithm Pattern
- Example: Basic minimax for Tic-Tac-Toe
- 2. Alpha-Beta Pruning Optimization
- Example: Minimax with alpha-beta pruning
- Example: Alpha-beta pruning visualization
- 3. Nim Game Problem Pattern
- Example: Simple Nim game - remove 1, 2, or 3 stones
- 4. Stone Game (DP Solution)
- Example: Stone game - take first or last
- Example: Stone game with prefix sum optimization
- 5. Predict the Winner Problem
- Example: Predict winner with DP
- Example: Space-optimized and memoization
- Summary: Game Theory Patterns
- 1. LRU Cache (HashMap + Doubly Linked List)
- Example: LRU Cache implementation
- 2. LFU Cache (Frequency Tracking)
- Example: LFU Cache implementation
- 3. Min Stack with O(1) Operations
- Example: Two stacks approach
- Example: Optimized min stack
- 4. Implement Queue Using Stacks
- Example: Queue using two stacks
- 5. Design Twitter Timeline (OOD)
- Example: Twitter timeline with merge k lists
- 6. Design Hit Counter Problem
- Example: Queue-based hit counter
- Example: Circular array (O(1) space)
- Summary: Design Pattern Problems
- 1. Producer-Consumer Pattern (Concurrency)
- Example: Producer-Consumer with bounded buffer
- 2. Print in Order Problem (Thread Synchronization)
- Example: Print in order using semaphores
- Example: Using promises in JavaScript
- 3. Dining Philosophers Problem
- Example: Dining philosophers with resource ordering
- Example: Waiter solution (limit concurrent diners)
- 4. Reader-Writer Lock Pattern
- Example: Readers-preference lock
- Example: Fair reader-writer lock
- 5. Traffic Light Controller System
- Example: Traffic light synchronization
- Example: Advanced traffic light with priorities
- Summary: Multi-threading Patterns
- 1. Integer Overflow Handling Techniques
- Example: Detecting overflow before operation
- Example: Common overflow scenarios
- 2. Floating Point Precision Errors
- Example: Floating point comparison
- Example: Common floating point pitfalls
- 3. Array Index Out of Bounds Errors
- Example: Array bounds checking patterns
- 4. Null Pointer Safety Checks
- Example: Null/undefined safety patterns
- Example: Defensive programming
- 5. Stack Overflow from Recursion Depth
- Example: Stack overflow scenarios
- Example: Converting recursion to iteration
- 6. Off-by-One Errors Prevention
- Example: Common off-by-one mistakes
- Example: Edge case testing for off-by-one
- 7. Empty Input Validation
- Example: Empty input handling
- 8. Single Element Edge Cases
- Example: Single element handling
- Example: Testing with minimal inputs
- 9. Duplicate Handling Strategies
- Example: Various duplicate handling approaches
- Example: Duplicate detection patterns
- 1. Integer Overflow Handling Techniques
- Example: Overflow prevention techniques
- Summary: Common Pitfalls and Edge Cases
- 1. Test Case Generation Strategies
- Example 1: Test Case Generator for Sorting Function
- Example 2: Automated Test Case Generator with Coverage
- 2. Edge Case Identification Techniques
- Example 1: Comprehensive Edge Case Checker
- 3. Boundary Value Testing
- Example 1: Boundary Value Test Generator
- 4. Performance Profiling and Optimization
- Example 1: Performance Profiler with Time Complexity Verification
- 5. Algorithm Code Review Checklist
- Example 1: Automated Code Review Checker
- 6. Stress Testing with Large Inputs
- Example 1: Stress Test Framework
- 7. Corner Case Enumeration Methods
- Example: Corner Case Generator and Validator
- Summary: Testing and Debugging Patterns