Mastering Complex DSA Topics

My experience of mastering complex topics like DP, Trees, etc

When I was studying for a job switch from consulting in 2020, I was prepping for data engineering interviews. And , at the time, I focussed on two main topics. SQL and DSA. I had mastered SQL to a point where I could solve most questions easily. However, DSA remained an issue. I practiced a lot and thought I was getting better. But when I failed to solve the coin change problem for a FAANG company interview, that really hurt. It felt even more disappointing because I had seen that problem. And at this time , I knew , I needed to fix something with my strategy. So, I reached out to my friend who worked at Google and asked him for some tips and advise. And here’s what he said :

1. Create a list of patterns that summarize most DSA problems.

2. Solve at least 4-5 problems per pattern

3. Reinforce your learning. For example : If you can’t solve a problem, understand how to solve it. Then next day, try to code it and write its logic to see how much you remember. And at a gap of 4-5 days, resolve these problems to test your knowledge.

With this in mind, I analyzed my weaker topics which are below :

Linked Lists

Trees

Tries

Graphs

Backtracking

DP

So, to overcome them, below are the patterns and the problems I solved for them.

Before, I go further, credit is due. I didn’t create these patterns. I leveraged number of resources which are all shared at the bottom of this page. Also, I have mapped the problem number which would make it easier for you to find them on linked in. Happy Coding!

Linked Lists

• Two pointer

  • Famous two pointer is the use of fast and slow pointer(this algorithm is also known as Floyd’s Algorithm) ,if the slow pointer moves 1 step ahead, then the fast pointer moves 2 step ahead.

  • Problems:

  • 876.Finding the middle node in linked list[EASY]

• Getting the k^th from last node

  • Have two pointers, where one is k nodes ahead of the other. When the node ahead reaches the end, the other node is k nodes behind

  • Problems : Remove nth node from end of list

• Detecting cycles

  • Have two pointers, where one pointer increments twice as much as the other, if the two pointers meet, means that there is a cycle

  • Problems : Detect cycles.

• Getting the middle node

  • Have two pointers, where one pointer increments twice as much as the other. When the faster node reaches the end of the list, the slower node will be at the middle

  • Problems : Middle node

Trees :

1. Traversal Patterns

• Depth-First Search (DFS) - Preorder, Inorder, Postorder

• Breadth-First Search (BFS) - Level-order Traversal

• Binary Tree Inorder Traversal (Easy)
  LeetCode #94

• Binary Tree Preorder Traversal (Easy)
  LeetCode #144

• Binary Tree Postorder Traversal (Easy)
  LeetCode #145

• Binary Tree Level Order Traversal (Medium)
  LeetCode #102

• Average of Levels in Binary Tree (Easy)
  LeetCode #637

2. Binary Search Tree (BST) Operations

• Searching, Insertion, Deletion

• Validation of BST properties

1. Validate Binary Search Tree (Medium)
   LeetCode #98

2. Search in a Binary Search Tree (Easy)
   LeetCode #700

3. Lowest Common Ancestor of a BST (Easy)
   LeetCode #235

4. Minimum Absolute Difference in BST (Easy)
   LeetCode #530

5. Convert Sorted Array to BST (Easy)
   LeetCode #108

3. Tree Height & Depth Problems

• Calculating height, depth, diameter

• Balanced vs unbalanced trees

1. Maximum Depth of Binary Tree (Easy)
   LeetCode #104

2. Balanced Binary Tree (Easy)
   LeetCode #110

3. Diameter of Binary Tree (Easy)
   LeetCode #543

4. Minimum Depth of Binary Tree (Easy)
   LeetCode #111

4. Lowest Common Ancestor (LCA)

• Finding common ancestors in binary trees or BSTs

1. Lowest Common Ancestor of a Binary Tree (Medium)
   LeetCode #236

2. Lowest Common Ancestor of a BST (Easy)
   LeetCode #235

3. Smallest Common Region (Medium)
   LeetCode #1257

4. Find Nearest Right Node in Binary Tree (Medium)
   LeetCode #1602

5. Path Sum Problems

• Finding paths with a given sum, counting paths, and path existence

• Path Sum (Easy)
  LeetCode #112

• Path Sum II (Medium)
  LeetCode #113

• Path Sum III (Medium)
  LeetCode #437

• Binary Tree Paths (Easy)
  LeetCode #257

• Sum Root to Leaf Numbers (Medium)
  LeetCode #129

Graphs :

Pattern 1: Graph Traversal (BFS and DFS)

Explanation: Visiting all nodes, useful for finding connectivity, shortest paths (unweighted), and connected components.

Practice Problems:

• #200 Number of Islands (Medium)

• #733 Flood Fill (Easy)

• #994 Rotting Oranges (Medium)

• #547 Number of Provinces (Medium)

Pattern 2: Topological Sorting

Explanation: Linear ordering of nodes used for tasks scheduling or resolving dependencies.

Practice Problems:

• #207 Course Schedule (Medium)

• #210 Course Schedule II (Medium)

• #269 Alien Dictionary (Premium) (Hard but classic)

• #802 Find Eventual Safe States (Medium)

Pattern 3: Shortest Path Algorithms (BFS, Dijkstra)

Explanation: Finding minimum distance or minimum moves in graphs.

Practice Problems:

• #542 01 Matrix (Medium)

• #1091 Shortest Path in Binary Matrix (Medium)

• #286 Walls and Gates (Premium) (Medium)

• #1926 Nearest Exit in Maze (Medium)

Pattern 4: Union-Find (Disjoint Set)

Explanation: Managing and checking connections among nodes quickly, useful in detecting cycles or connected groups.

Practice Problems:

• #684 Redundant Connection (Medium)

• #547 Number of Provinces (Medium)

• #323 Number of Connected Components (Premium) (Medium)

• #1319 Number of Operations to Connect Network (Medium)

BACKTRACKING :

Pattern 1: Combinations & Subsets

Explanation: Explore all possible subsets/combinations by recursively including/excluding elements.

Practice Problems:

• #78 Subsets (Medium)

• #77 Combinations (Medium)

• #90 Subsets II (Medium)

• #39 Combination Sum (Medium)

Pattern 2: Permutations

Explanation: Generate all possible orderings of elements by swapping or using flags to track used elements.

Practice Problems:

• #46 Permutations (Medium)

• #47 Permutations II (Medium)

• #784 Letter Case Permutation (Medium)

Pattern 3: Constraints Satisfaction (e.g., N-Queens)

Explanation: Finding solutions under certain constraints, such as placements on a grid or board.

Practice Problems:

• #79 Word Search (Medium)

Pattern 4: Partitioning Problems

Explanation: Finding all possible partitions of a string or array into substrings/subarrays satisfying a condition.

Practice Problems:

• #131 Palindrome Partitioning (Medium)

• #93 Restore IP Addresses (Medium)

DYNAMIC PROGRAMMING :

Pattern 1: 0/1 Knapsack & Subset Sum

Explanation: Choosing subsets based on optimal criteria (maximize/minimize sums or values).

Practice Problems:

• #416 Partition Equal Subset Sum (Medium)

• #494 Target Sum (Medium)

• #474 Ones and Zeroes (Medium)

• #1049 Last Stone Weight II (Medium)

Pattern 2: Longest Increasing Subsequence (LIS)

Explanation: Finding longest subsequences (increasing or similar conditions).

Practice Problems:

• #300 Longest Increasing Subsequence (Medium)

• #673 Number of Longest Increasing Subsequences (Medium)

• #646 Maximum Length of Pair Chain (Medium)

• #368 Largest Divisible Subset (Medium)

Pattern 3: Grid or Matrix DP (Paths & Minimum Cost)

Explanation: Solving problems by building solutions from previous grid or matrix cells.

Practice Problems:

• #62 Unique Paths (Medium)

• #64 Minimum Path Sum (Medium)

• #931 Minimum Falling Path Sum (Medium)

• #63 Unique Paths II (Medium)

Pattern 4: DP on Strings (LCS, Edit Distance)

Explanation: Solving problems involving two or more strings by comparing subsequences or operations.

Practice Problems:

• #1143 Longest Common Subsequence (Medium)

• #583 Delete Operation for Two Strings (Medium)

• #516 Longest Palindromic Subsequence (Medium)

• #72 Edit Distance (Medium-Hard but fundamental)

Tries :

I would be honest, while I did practice these, I didn’t see them asked in any interviews. So, solve this topic at the end.

1. Basic Trie Implementation (Insert/Search)

• Building and querying a trie data structure.

LeetCode Practice Problems:

• Implement Trie (Prefix Tree) (Medium)
  LeetCode #208

• Design Add and Search Words Data Structure (Medium)
  LeetCode #211

• Map Sum Pairs (Medium)
  LeetCode #677

• Replace Words (Medium)
  LeetCode #648

---

2. Prefix Matching & Autocomplete

• Finding or counting words with given prefixes.

LeetCode Practice Problems:

• Longest Common Prefix (Easy) (Trie solution applicable)
  LeetCode #14

• Implement Trie II (Prefix Tree) (Medium)
  LeetCode #1804

• Search Suggestions System (Medium)
  LeetCode #1268

• Prefix and Suffix Search (Hard, but very common pattern)
  LeetCode #745

---

3. Word Search in Grids (DFS + Trie)

• Efficiently searching multiple words in 2D grids.

LeetCode Practice Problems:

• Word Search II (Hard, but common interview pattern)
  LeetCode #212

• Word Search (Medium; Trie optional but helpful)
  LeetCode #79

(Note: These problems combine DFS with Trie and are popular in interviews.)

---

4. Counting Unique or Distinct Patterns

• Problems involving counting distinct substrings or words.

LeetCode Practice Problems:

• Count Distinct Substrings in a String (Medium)
  LeetCode #1698

• Maximum XOR of Two Numbers in an Array (Medium, Trie solution)
  LeetCode #421

---

Credits :

Leetcode patterns

Leetcode patterns article

Github repo