Cracking the Coding Interview: 17 Patterns You Need to Know

If you’re preparing for a tech interview, you’ve probably realized that solving random LeetCode problems isn’t enough. Patterns matter.

After practicing and analyzing tons of problems, I’ve found that most coding challenges fall into these 17 core patterns. Here’s a comprehensive guide to each pattern, along with relevant LeetCode problems to practice.

1. Two Pointers

When to use:

• Searching pairs in a sorted array
• Comparing elements from both ends of an array
• Removing duplicates or filtering elements

Key concept: Utilize two pointers, often at opposite ends of the array, moving them based on specific conditions.

Code Template:

def two_pointers(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        # Process elements at arr[left] and arr[right]
        if condition_met:
            # Do something
            left += 1
            right -= 1
        elif need_to_move_left:
            left += 1
        else:
            right -= 1
    return result

LeetCode Problems:

• Valid Palindrome
• 3Sum
• Container With Most Water
• Remove Duplicates from Sorted Array
• Trapping Rain Water

2. Sliding Window

When to use:

• Finding subarrays or substrings that meet certain conditions
• Calculating a running average or sum
• Solving string problems with constraints on characters

Key concept: Maintain a window of elements, expanding or contracting it based on problem conditions.

Code Template:

def sliding_window(arr):
    left = 0
    window_sum = 0
    result = 0
    for right in range(len(arr)):
        window_sum += arr[right]
        while condition_not_met:
            window_sum -= arr[left]
            left += 1
        result = max(result, right - left + 1)
    return result

LeetCode Problems:

• Longest Substring Without Repeating Characters
• Minimum Window Substring
• Longest Repeating Character Replacement
• Maximum Sum Subarray of Size K
• Permutation in String

3. Fast and Slow Pointers

When to use:

• Detecting cycles in a linked list
• Finding the middle element of a linked list
• Determining the length of a cycle

Key concept: Use two pointers moving at different speeds to detect patterns or anomalies.

Code Template:

def fast_slow_pointers(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True  # Cycle detected
    return False

LeetCode Problems:

• Linked List Cycle
• Find the Duplicate Number
• Middle of the Linked List
• Happy Number
• Palindrome Linked List

4. Merge Intervals

When to use:

• Merging overlapping intervals
• Finding conflicts in schedules
• Optimizing resource allocation

Key concept: Sort intervals by start time and then merge or process them sequentially.

Code Template:

def merge_intervals(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = []
    for interval in intervals:
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            merged[-1][1] = max(merged[-1][1], interval[1])
    return merged

LeetCode Problems:

• Merge Intervals
• Insert Interval
• Non-overlapping Intervals
• Meeting Rooms II
• Employee Free Time

5. Cyclic Sort

When to use:

• Finding missing numbers
• Detecting duplicates in a specific range
• Rearranging elements in-place

Key concept: Utilize the fact that array elements are in a specific range to sort or identify anomalies efficiently.

Code Template:

def cyclic_sort(nums):
    i = 0
    while i < len(nums):
        correct_pos = nums[i] - 1
        if nums[i] != nums[correct_pos]:
            nums[i], nums[correct_pos] = nums[correct_pos], nums[i]
        else:
            i += 1
    return nums

LeetCode Problems:

• Missing Number
• Find All Numbers Disappeared in an Array
• Find the Duplicate Number
• First Missing Positive
• Kth Missing Positive Number

6. In-place Reversal of a Linked List

When to use:

• Reversing a linked list or its subparts
• Reordering linked list elements
• Detecting palindromes in a linked list

Key concept: Use multiple pointers to reverse links in-place.

Code Template:

def reverse_linked_list(head):
    prev = None
    current = head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev

LeetCode Problems:

• Reverse Linked List
• Reverse Linked List II
• Reverse Nodes in k-Group
• Swap Nodes in Pairs
• Rotate List

7. Tree Breadth-First Search (BFS)

When to use:

• Level-order traversal of a tree
• Finding the minimum depth of a tree
• Connecting nodes at the same level

Key concept: Use a queue to process nodes level by level.

Code Template:

from collections import deque

def bfs(root):
    if not root:
        return []
    queue = deque([root])
    result = []
    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

LeetCode Problems:

• Binary Tree Level Order Traversal
• Binary Tree Zigzag Level Order Traversal
• Minimum Depth of Binary Tree
• Binary Tree Right Side View
• Average of Levels in Binary Tree

8. Tree Depth-First Search (DFS)

When to use:

• Path sum problems
• Tree diameter calculation
• Validating binary search trees

Key concept: Use recursion or a stack to explore branches to their full depth before backtracking.

Code Template:

def dfs(root):
    if not root:
        return
    # Process current node
    dfs(root.left)
    dfs(root.right)

LeetCode Problems:

• Path Sum
• Binary Tree Maximum Path Sum
• Diameter of Binary Tree
• Validate Binary Search Tree
• Flatten Binary Tree to Linked List

9. Two Heaps

When to use:

• Finding the median in a stream of numbers
• Scheduling problems
• Priority queue-related problems

Key concept: Maintain two heaps, one max-heap and one min-heap, to efficiently track extremes of a dataset.

Code Template:

import heapq

class MedianFinder:
    def __init__(self):
        self.small = []  # max heap
        self.large = []  # min heap

    def addNum(self, num: int) -> None:
        if len(self.small) == len(self.large):
            heapq.heappush(self.large, -heapq.heappushpop(self.small, -num))
        else:
            heapq.heappush(self.small, -heapq.heappushpop(self.large, num))

    def findMedian(self) -> float:
        if len(self.small) == len(self.large):
            return (-self.small[0] + self.large[0]) / 2.0
        else:
            return float(self.large[0])

LeetCode Problems:

• Find Median from Data Stream
• Sliding Window Median
• IPO
• Find Right Interval
• Schedule Tasks on Minimum Machines

10. Subsets

When to use:

• Generating all subsets of a set
• Creating permutations of a string
• Solving combination sum problems

Key concept: Use recursion or bit manipulation to generate all possible combinations.

Code Template:

def subsets(nums):
    result = []
    def backtrack(start, current):
        result.append(current[:])
        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()
    backtrack(0, [])
    return result

LeetCode Problems:

• Subsets
• Permutations
• Combination Sum
• Letter Combinations of a Phone Number
• Generate Parentheses

11. Modified Binary Search

When to use:

• Searching in a sorted, rotated array
• Finding a peak element
• Searching in a 2D sorted matrix

Key concept: Adapt the traditional binary search algorithm to handle more complex scenarios.

Code Template:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

LeetCode Problems:

• Search in Rotated Sorted Array
• Find Minimum in Rotated Sorted Array
• Peak Index in a Mountain Array
• Search a 2D Matrix
• Find K Closest Elements

12. Topological Sort

When to use:

• Course scheduling problems
• Build order dependencies
• Task scheduling with prerequisites

Key concept: Use DFS or BFS to find a valid ordering of nodes in a directed acyclic graph.

Code Template:

from collections import defaultdict, deque

def topological_sort(num_nodes, edges):
    graph = defaultdict(list)
    in_degree = [0] * num_nodes
    for src, dest in edges:
        graph[src].append(dest)
        in_degree[dest] += 1
    
    queue = deque([node for node in range(num_nodes) if in_degree[node] == 0])
    result = []
    
    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    return result if len(result) == num_nodes else []

LeetCode Problems:

• Course Schedule
• Course Schedule II
• Alien Dictionary
• Minimum Height Trees
• Sequence Reconstruction

13. Dynamic Programming

When to use:

• Optimization problems (e.g., maximum/minimum path sum)
• Counting problems (e.g., number of ways to reach a target)
• String manipulation problems (e.g., longest common subsequence)

Key concept: Break down complex problems into simpler subproblems and store their solutions to avoid redundant calculations.

Code Template:

def dynamic_programming(n):
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

LeetCode Problems:

• Climbing Stairs
• Coin Change
• Longest Increasing Subsequence
• Word Break
• Regular Expression Matching

14. Bitwise XOR

When to use:

• Finding a missing number in a sequence
• Detecting a single number in a set of pairs
• Swapping numbers without using a temporary variable

Key concept: Leverage the properties of XOR operation to solve problems efficiently.

Code Template:

def find_single_number(nums):
    result = 0
    for num in nums:
        result ^= num
    return result

LeetCode Problems:

• Single Number
• Missing Number
• Find the Duplicate Number
• Decode XORed Array
• XOR Queries of a Subarray

15. Graph Traversal

When to use:

• Finding shortest paths
• Detecting cycles in a graph
• Solving maze-related problems

Key concept: Use DFS or BFS to traverse and analyze graph structures.

Code Template:

from collections import defaultdict, deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    
    while queue:
        node = queue.popleft()
        # Process node
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

LeetCode Problems:

• Number of Islands
• Clone Graph
• Pacific Atlantic Water Flow
• Word Ladder
• Graph Valid Tree

16. Monotonic Stack/Queue

When to use:

• Finding the next greater/smaller element
• Solving histogram-related problems
• Optimizing time complexity in certain array problems

Key concept: Maintain a stack or queue in monotonic order to efficiently solve problems involving comparisons.

Code Template:

from collections import defaultdict, deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    
    while queue:
        node = queue.popleft()
        # Process node
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

LeetCode Problems:

• Next Greater Element I
• Daily Temperatures
• Largest Rectangle in Histogram
• Trapping Rain Water
• Remove K Digits

17. Trie (Prefix Tree)

When to use:

• Implementing autocomplete features
• Solving word search problems
• Efficiently storing and searching strings

Key concept: Use a tree-like data structure to store and retrieve strings based on their prefixes.

Code Template:

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
    
    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end

LeetCode Problems:

• Implement Trie (Prefix Tree)
• Word Search II
• Design Add and Search Words Data Structure
• Replace Words
• Palindrome Pairs

By mastering these 17 patterns, you’ll be well-equipped to tackle a wide range of coding interview questions. Remember, the key is not just to memorize solutions, but to understand the underlying patterns and apply them creatively to new problems.