What are most common LeetCode patterns?

LeetCode challenges often revolve around certain problem-solving patterns or techniques. Recognizing these patterns can greatly enhance your ability to solve various problems efficiently. Here are some of the most common LeetCode patterns:

1. Sliding Window

• Usage: Mainly used for array/string problems.
• Purpose: To find a subrange in an array/string, such as a substring or subarray, that meets certain criteria.
• Example Problems: Maximum sum subarray of size 'K', smallest subarray with a given sum, longest substring with K distinct characters.

2. Two Pointers

• Usage: For arrays, linked lists, strings.
• Purpose: Efficiently comparing elements and finding a pair or set of elements that meet specific conditions.
• Example Problems: Pair with target sum, remove duplicates, long-pressed name.

3. Fast & Slow Pointers

• Usage: Linked lists and arrays.
• Purpose: Detecting cycles, finding middle elements, or solving problems requiring a certain form of traversal.
• Example Problems: Start of LinkedList cycle, happy number, middle of the LinkedList.

4. Two Heaps

• Usage: Problems involving a set of elements divided into two parts to find a median, or for scheduling and interval problems.
• Purpose: To manage two sets of numbers where one set is always greater or smaller than the other.
• Example Problems: Find median from data stream, maximize capital, minimum number of refueling stops.

5. Merge Intervals

• Usage: Intervals, ranges, or time slots.
• Purpose: To merge overlapping intervals and sort intervals.
• Example Problems: Merge intervals, insert interval, employee free time.

6. Cyclic Sort

• Usage: Arrays.
• Purpose: Sorting an array containing numbers in a given range.
• Example Problems: Find the missing number, find all duplicate numbers, find the first K missing positive numbers.

7. In-place Reversal of a LinkedList

• Usage: Linked list problems.
• Purpose: To reverse a linked list in place.
• Example Problems: Reverse a LinkedList, reverse a sub-list, rotate a LinkedList.

8. Tree Breadth-First Search (BFS)

• Usage: Trees and graphs.
• Purpose: Level order traversal or exploring nodes level by level.
• Example Problems: Binary tree level order traversal, zigzag traversal, minimum depth of a binary tree.

9. Tree Depth-First Search (DFS)

• Usage: Trees and occasionally graphs.
• Purpose: Deep exploration of nodes, often used to solve subtree problems.
• Example Problems: Maximum depth of binary tree, path sum, count paths for a sum.

10. Topological Sort (Graph)

• Usage: Graphs, especially those representing tasks or courses.
• Purpose: To sort vertices in a graph based on their dependencies.
• Example Problems: Course schedule, task scheduling, minimum height trees.

11. Subset/Backtracking

• Usage: Combinatorial problems.
• Purpose: To explore all possible combinations or permutations.
• Example Problems: Subsets, permutations, letter case string permutation.

12. Dynamic Programming

• Usage: Problems that require breaking down into smaller overlapping sub-problems.
• Purpose: To find the optimal solution to a problem by solving its sub-problems.
• Example Problems: Longest increasing subsequence, knapsack problem, coin change.

Conclusion

Recognizing these patterns is key to efficiently approaching and solving a wide array of LeetCode problems. Each pattern offers a systematic way to navigate through the problem space, making seemingly complex problems more manageable.