Introduction: Conquering LeetCode with Patterns
LeetCode can feel like a daunting mountain range, filled with hundreds of coding problems that seem impossible to conquer. But what if I told you that there’s a way to navigate this challenging terrain more effectively? The secret lies in recognizing recurring patterns. As experienced software engineer Sahil mentions in his insightful YouTube video, mastering a few key patterns can equip you to solve a significant portion of LeetCode problems. This post will break down 8 of these essential patterns, providing explanations, examples, and tips to help you level up your problem-solving skills for your next coding interview.
Pattern 1: Sliding Window
Concept: The Sliding Window pattern is your go-to when dealing with linear data structures (arrays, strings, linked lists) and you need to find a sub-section (a “window”) that satisfies a given condition. Think of it like a window sliding across your data, one element at a time.
When to Use:
- Finding the longest/shortest substring/subarray meeting a condition.
- Problems involving contiguous sequences.
Example: Longest Substring with K Unique Characters
Pseudocode:
function longestSubstringKUnique(str, k) {
windowStart = 0;
maxLength = 0;
charFrequency = {}; // Keep track of character frequencies in the window
for (windowEnd = 0; windowEnd < str.length; windowEnd++) {
rightChar = str[windowEnd];
// Add rightChar to charFrequency
while (Object.keys(charFrequency).length > k) {
// Shrink window if more than k unique chars
leftChar = str[windowStart];
// Remove leftChar from charFrequency
windowStart++;
}
maxLength = Math.max(maxLength, windowEnd - windowStart + 1); // Update max length
}
return maxLength;
}
Python Example:
def longest_substring_k_unique(s, k):
window_start = 0
max_length = 0
char_frequency = {}
for window_end in range(len(s)):
right_char = s[window_end]
char_frequency[right_char] = char_frequency.get(right_char, 0) + 1
while len(char_frequency) > k:
left_char = s[window_start]
char_frequency[left_char] -= 1
if char_frequency[left_char] == 0:
del char_frequency[left_char]
window_start += 1
max_length = max(max_length, window_end - window_start + 1)
return max_length
Pattern 2: Subsets (Combinations/Permutations)
Concept: This pattern deals with finding all possible combinations or permutations of elements in a set.
When to Use:
- Generating all subsets of a set.
- Finding all permutations of a string or array.
- Problems involving combinations with or without repetitions.
Example: Permutations of a String
Conceptual Approach: Iteratively build subsets level by level, similar to Breadth-First Search (BFS).
Python Example:
def permute(nums):
if not nums:
return []
result = []
perms = [[]]
for num in nums:
new_perms = []
for perm in perms:
for i in range(len(perm) + 1):
new_perms.append(perm[:i] + [num] + perm[i:])
perms = new_perms
return perms
Pattern 3: Modified Binary Search
Concept: Adapting the classic binary search algorithm to handle variations like rotated sorted arrays, finding the closest element, or dealing with duplicates.
When to Use:
- Searching in sorted arrays, even with modifications like rotations.
- Finding the closest element to a target value.
- Problems where the search space can be halved efficiently.
Example: Search in Rotated Sorted Array
Key Idea: Modify the standard binary search to determine which half of the array is sorted and adjust the search accordingly.
Python Example:
def search_rotated(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
Pattern 4: Top K Elements
Concept: Finding the k largest, smallest, most frequent, etc., elements in a dataset.
When to Use:
- Finding the top
kelements based on a specific criterion. - Problems involving ranking or selecting a subset of elements.
Example: Kth Largest Number in an Array
Solution using a Min-Heap:
- Maintain a min-heap of size
k. - Iterate through the array. For each number, add it to the heap.
- If the heap size exceeds
k, remove the smallest element (heap’s root). - After iterating, the heap’s root will be the kth largest element.
Python Example:
import heapq
def find_kth_largest(nums, k):
min_heap = []
for num in nums:
heapq.heappush(min_heap, num)
if len(min_heap) > k:
heapq.heappop(min_heap)
return min_heap[0]
Pattern 5: Binary Tree Depth-First Search (DFS)
Concept: Traversing a binary tree by exploring as far as possible along each branch before backtracking. Usually implemented using recursion.
When to Use:
- Problems involving tree traversal, path finding, or node property calculations.
- Preorder, inorder, and postorder traversals.
Example: Maximum Depth of Binary Tree
Solution (Recursive):
class TreeNode {
val: number;
left: TreeNode | null;
right: TreeNode | null;
constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
this.val = val === undefined ? 0 : val;
this.left = left === undefined ? null : left;
this.right = right === undefined ? null : right;
}
}
function maxDepth(root: TreeNode | null): number {
if (!root) {
return 0;
}
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
Python Example:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def maxDepth(root):
if not root:
return 0
return 1 + max(maxDepth(root.left), maxDepth(root.right))
Pattern 6: Topological Sort
Concept: Ordering elements in a directed acyclic graph (DAG) based on their dependencies. If there’s a directed edge from node A to node B, then A must come before B in the ordering.
When to Use:
- Problems involving prerequisites or dependencies.
- Task scheduling, build systems, and dependency resolution.
Example: Course Schedule
Conceptual Approach:
- Build a dependency graph (adjacency list).
- Calculate the in-degree (number of incoming edges) for each node.
- Start with nodes having an in-degree of 0.
- Process these nodes, removing their outgoing edges and decrementing the in-degree of their neighbors.
- Repeat step 4 until all nodes are processed.
Python Example:
from collections import defaultdict, deque
def canFinish(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for course, prereq in prerequisites:
graph[prereq].append(course)
in_degree[course] += 1
queue = deque([course for course in range(numCourses) if in_degree[course] == 0])
order = []
while queue:
course = queue.popleft()
order.append(course)
for next_course in graph[course]:
in_degree[next_course] -= 1
if in_degree[next_course] == 0:
queue.append(next_course)
return len(order) == numCourses
Pattern 7: Binary Tree Breadth-First Search (BFS)
Concept: Traversing a binary tree level by level, using a queue.
When to Use:
- Problems involving level-order traversal.
- Finding the shortest path in an unweighted graph.
Example: Level Order Traversal of a Binary Tree
Conceptual Approach:
- Use a queue to store nodes at each level.
- Start with the root node in the queue.
- While the queue is not empty:
- Dequeue a node.
- Process the node.
- Enqueue its children.
Python Example:
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def levelOrder(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
current_level = []
for _ in range(level_size):
node = queue.popleft()
current_level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(current_level)
return result
Pattern 8: Two Pointers
Concept: Using two pointers to iterate through a sorted array or linked list, often moving them towards or away from each other based on a specific condition.
When to Use:
- Problems involving finding pairs or triplets that satisfy a condition in a sorted array.
- Reversing an array or linked list in place.
Example: Two Sum (assuming the input array is sorted)
Solution:
function twoSum(nums: number[], target: number): number[] | null {
let left = 0;
let right = nums.length - 1;
while (left < right) {
const sum = nums[left] + nums[right];
if (sum === target) {
return [left, right];
} else if (sum < target) {
left++;
} else {
right--;
}
}
return null;
}
Python Example:
def two_sum(nums, target):
left, right = 0, len(nums) - 1
while left < right:
current_sum = nums[left] + nums[right]
if current_sum == target:
return [left, right]
elif current_sum < target:
left += 1
else:
right -= 1
return None
Conclusion: Practice Makes Perfect
These 8 patterns are powerful tools in your LeetCode arsenal. Remember, understanding the underlying concepts and practicing applying these patterns are crucial. Don’t just memorize solutions; focus on recognizing when a particular pattern is applicable. Now, go forth and conquer those coding challenges! 🚀