Key Coding Patterns for Problem Solving

Overview

• Solved 554 LeetCode problems
• Realized importance of focusing on recurring patterns
• Presenting 8 coding patterns

1. Sliding Window Pattern

• Use: Processing series of data elements (e.g. list, string)
• Concept: Look at a smaller part of the list (the "window") which slides one step at a time until the entire list is scanned
• When to Use:
  • To find a subset of elements satisfying a condition
  • Typical inputs: linear data structures (array, string, linked list)
  • Example: Longest substring with K unique characters

2. Subset Pattern

• Use: Finding all combinations of elements from a given set
• Concept: Explore all possible arrangements by iteratively building subsets
• Approach: Similar to breadth-first search (BFS)
  • Start with an empty set, add the next element at each level
  • Example: Permutations problem

3. Modified Binary Search Pattern

• Use: Searching in a modified or rotated sorted array
• Core Idea: Divide the search space in half, adjusting logic as needed
• Example: Search in rotated sorted array
• Tip: Understand core binary search algorithm well; use Python's bisect module for practice

4. Top K Elements Pattern

• Use: Selecting K elements from a larger dataset
• Concept: Track the K most important numbers seen so far
• Data Structure: Use a heap for efficiency in finding and removing elements
• Example: Finding the kth largest number

5. Depth First Search (DFS) of Binary Tree

• Use: Visiting every node in a binary tree
• Concept: Focus on one branch at a time, using recursion
• Example: Maximum depth of binary tree
• Flow: Start at the root, apply DFS recursively to left and right nodes

6. Topological Sort

• Use: Arranging elements with dependencies
• Application: Effective for directed acyclic graphs (DAGs)
• Example: Course scheduling problem

7. Breadth First Search (BFS) of Binary Tree

• Use: Explore nodes at the same level before moving to the next level
• Data Structure: Use a queue
• Process: Remove a node from the queue, perform operations, add its children back to the queue
• Example: Level order reversal of a binary tree

8. Two-Pointer Pattern

• Use: Iterating through a sorted array
• Concept: Use two pointers to solve a problem in a single pass
• Example: Two sum problem in a sorted array
• Variation: Finding triplets that sum to zero

Conclusion

• Explore problems that fit these patterns
• Need a solid understanding of data structures and algorithms
• Consider signing up for a free email crash course on mastering DSA
• Speaker: Sahil