DSA Pa!
ern Problems - 6 DS
► Graphs
► Graphs
Pattern 1: DFS/BFS Traversal
→ Number of Islands
→ Flood Fill
→ Clone Graph
→ Graph Valid Tree
→ Course Schedule
Pattern 2: Shortest Path Algorithms
→ Dijkstra’s Algorithm
→ Bellman-Ford
→ Shortest Path in a Grid
→ Network Delay Time
→ Cheapest Flights Within K Stops
Pattern 3: Topological Sort
→ Course Schedule II
→ Alien Dictionary
→ Sequence Reconstruction
→ Minimum Height Trees
→ Task Scheduling
Pattern 4: Cycle Detection
→ Course Schedule
→ Graph Cycle Detection
→ Find if Path Exists in Graph
→ Redundant Connection
→ Minimum Edge to Add to Make Graph Strongly Connected
Pattern 5: Connected Components
→ Number of Connected Components in Graph
→ Friend Circles
→ Count Sub Islands
→ Graph Connectivity After Removing Edges
→ Maximum Area of Island
Pattern 6: Minimum Spanning Tree
→ Kruskal’s Algorithm
→ Prim’s Algorithm
→ Min Cost to Connect All Points
→ Connecting Cities With Minimum Cost
→ Redundant Connection II
Pattern 7: Union-Find
→ Redundant Connection
→ Number of Islands II
→ Accounts Merge
→ Friend Circles
→ Satisfiability of Equality Equations
Pattern 8: Grid-Based Graph Problems
→ Number of Islands
→ Walls and Gates
→ Rotten Oranges
→ Shortest Path in Binary Matrix
→ Surrounded Regions
Pattern 9: Graph Coloring
→ Graph Coloring
→ Is Graph Bipartite?
→ Map Coloring
→ Partition to K Equal Sum Subsets
→ Scheduling With Constraints
Pattern 10: Strongly Connected Components
→ Course Schedule III
→ Kosaraju’s Algorithm Challenge
→ Tarjan’s Algorithm Challenge
→ Evaluate Division
→ Minimum Days to Disconnect
Pattern 11: Eulerian & Hamiltonian Paths
→ Course Schedule IV
→ Find Itinerary
→ Hamiltonian Path in Directed Graph
→ Eulerian Circuit
→ Reconstruct Itinerary
Pattern 12: Planets & Queries
→ Dynamic Connectivity
→ Reachability Queries
→ Graph Connectivity via Snapshots
→ Distance Queries in Tree
→ Offline Query Processing
► Strings
► Strings
Pattern 1: KMP Algorithm
→ String Matching
→ Find the Index of the First Occurrence in a String
→ Shortest Palindrome
→ Longest Happy Prefix
→ Implement strStr()
Pattern 2: Z-Algorithm
→ String Matching
→ Shortest Palindrome
→ Pattern Search
→ Count and Say
→ Frequency of Pattern
Pattern 3: Rabin-Karp Algorithm
→ String Matching
→ Repeated String Match
→ Find All Anagrams in a String
→ Substring with Concatenation of All Words
→ Detect Cycle in a Circular Array
Pattern 4: Longest Common Subsequence
→ Longest Common Subsequence
→ Uncrossed Lines
→ Minimum ASCII Delete Sum for Two Strings
→ Shortest Common Supersequence
→ Delete Operation for Two Strings
Pattern 5: Edit Distance
→ Edit Distance
→ Word Ladder
→ Word Break II
→ Sequence Alignment
→ Minimum Steps to Convert Word
Pattern 6: Regular Expression Matching
→ Regular Expression Matching
→ Wildcard Matching
→ Word Search
→ Valid Palindrome II
→ Pattern Matching in String
Pattern 7: Palindrome Problems
→ Palindrome Partitioning
→ Valid Palindrome II
→ Longest Palindromic Subsequence
→ Palindromic Substrings
→ Minimum Cuts for Palindromes
Pattern 8: Trie (Prefix Tree)
→ Implement Trie
→ Add and Search Word
→ Replace Words
→ Map Sum Pairs
→ Word Search II
Pattern 9: DP on Intervals for Strings
→ Palindrome Partitioning II
→ Burst Balloons
→ Strange Printer
→ Matrix Chain Multiplication
→ Optimal Binary Search Tree
► Dynamic Programming
► Dynamic Programming
Pattern 1: Fibonacci/Simple Recurrence
→ Climbing Stairs
→ Min Cost Climbing Stairs
→ Dice Combinations
→ Frog Jump
→ Fibonacci Number
Pattern 2: 0/1 Knapsack
→ 0/1 Knapsack
→ Partition Equal Subset Sum
→ Target Sum
→ Subset Sum
→ Last Stone Weight II
Pattern 3: Unbounded Knapsack
→ Coin Change
→ Coin Change II
→ Rod Cutting
→ Combination Sum IV
→ Integer Break
Pattern 4: Longest Common Subsequence (LCS)
→ Longest Common Subsequence
→ Uncrossed Lines
→ Edit Distance
→ Shortest Common Supersequence
→ Delete Operation for Two Strings
Pattern 5: Longest Increasing Subsequence (LIS)
→ Longest Increasing Subsequence
→ Wiggle Subsequence
→ Increasing Triplet Subsequence
→ Continuous Increasing Subsequence
→ Russian Doll Envelopes
Pattern 6: Grid-Based DP
→ Unique Paths
→ Unique Paths II
→ Minimum Path Sum
→ Dungeon Game
→ Cherry Pickup
Pattern 7: Interval DP
→ Burst Balloons
→ Palindrome Partitioning II
→ Merge Stones
→ Optimal BST
→ Strange Printer
Pattern 8: Tree DP
→ House Robber III
→ Binary Tree Maximum Path Sum
→ Tree Diameter
→ Subtree Queries
→ Longest Univalue Path
Pattern 9: Bitmasking/State Compression
→ Traveling Salesman
→ Campus Bikes II
→ Elevator Rides
→ Count All Possible Routes
→ Bitmask DP Template
Pattern 10: Digit DP
→ Numbers With Repeated Digits
→ Count Digit One
→ Number of Digit One
→ Digit DP Template
→ Remove Digits
Pattern 11: Probability/Expectation DP
→ Dice Roll Simulation
→ New 21 Game
→ Random Pick with Weight
→ Frog Jump Probability
→ Candy Lottery
► Trees
► Trees
Pattern 1: Distance Between Nodes
→ Binary Tree Distance Queries
→ Tree Diameter
→ Lowest Common Ancestor
→ Kth Ancestor of a Tree Node
→ Distance to Root
Pattern 2: Sum of Distances
→ Sum of Distances in Tree
→ Tree Distances II
→ Sum of Root to Leaf Numbers
→ Tree Tilt
→ Diameter of Binary Tree
Pattern 3: Subtree Queries
→ Subtree Sum Queries
→ Company Queries II
→ Subtree Size Queries
→ Path Sum III
→ Count Univalue Subtrees
Pattern 4: Binary Lifting (LCA)
→ Lowest Common Ancestor
→ Binary Lifting Template
→ Jump Game in Tree
→ Tree Ancestry Queries
→ Tree Path Queries
Pattern 5: Tree DP
→ House Robber III
→ Tree Matching
→ Tree DP Template
→ Largest Independent Set
→ Maximum Path Sum
Pattern 6: Rerooting Technique
→ Tree Distances I
→ Tree Distances II
→ Sum of Distances in Tree
→ Rerooting DP Template
→ Tree Diameter
Pattern 7: Path Queries
→ Path Sum
→ Path Sum II
→ Longest Path in Tree
→ Query on a Tree
→ Kth Smallest Path Sum
Pattern 8: Tree Construction
→ Construct Binary Tree from Preorder/Inorder
→ Serialize and Deserialize Binary Tree
→ Reconstruct Itinerary
→ Build Tree from Leaf Sequence
→ Recover Binary Search Tree
► Heap
► Heap
Pattern 1: Top K Elements
→ Kth Largest Element in a Stream
→ Top K Frequent Elements
→ K Closest Points to Origin
→ Last Stone Weight
→ Task Scheduler
Pattern 2: Merge K Sorted Structures
→ Merge K Sorted Lists
→ Smallest Range Covering K Lists
→ Find K Pairs with Smallest Sums
→ Merge K Sorted Arrays
→ Merge Stones
Pattern 3: Two Heaps for Medians
→ Find Median from Data Stream
→ Sliding Window Median
→ Continuous Median
→ Median of Two Sorted Arrays
→ Sliding Window Median II
Pattern 4: Sliding Window Heaps
→ Sliding Window Maximum
→ Jump Game VI
→ Sliding Window Cost
→ Sliding Window Median (CSES)
→ Cheapest Flights Within K Stops
Pattern 5: Greedy Heap Applications
→ Minimum Cost to Connect Sticks
→ Maximum Performance Team
→ Reorganize String
→ Course Schedule III
→ IPO
Pattern 6: Heap-Based Game Theory
→ Stone Game VI
→ Minimum Initial Energy to Finish Tasks
→ Another Game (CSES)
→ Grundy’s Game
→ Game of Stones
► Linked List
► Linked List
Pattern 1: Fast & Slow Pointers
→ Linked List Cycle
→ Linked List Cycle II
→ Palindrome Linked List
→ Middle of the Linked List
→ Intersection of Two Linked Lists
Pattern 2: Reversing Linked Lists
→ Reverse Linked List
→ Reverse Nodes in k-Group
→ Reorder List
→ Swap Nodes in Pairs
→ Reverse Linked List II
Pattern 3: Merging & Partitioning Lists
→ Merge Two Sorted Lists
→ Partition List
→ Merge K Sorted Lists
→ Sort List
→ LR Insertion Template
Pattern 4: Dummy Node Technique
→ Remove Nth Node From End of List
→ Partition List
→ Swap Nodes in Pairs
→ Design Linked List
→ Add Two Numbers
Pattern 5: List Manipulation Operations
→ Design Linked List
→ List Removals
→ Insert into a Cyclic Sorted List
→ Reverse Linked List II
→ Split Linked List in Parts
Pattern 6: List Transformation
→ Reorder List
→ Remove Nth Node From End of List
→ Partition List
→ Add Two Numbers
→ Copy List with Random Pointer
Pattern 7: Basic List Operations Implementation
→ Design Linked List
→ Add Two Numbers
→ Remove Duplicates from Sorted List
→ Palindrome Linked List
→ Intersection of Two Linked Lists