Common Algorithm Patterns Cheat Sheet

Common Algorithm Patterns Cheat Sheet

Master these 15 patterns to solve 90% of coding interview questions

Why Learn Patterns?

Instead of memorizing 500 problems, learn 15 patterns that apply across hundreds of problems. Pattern recognition is key to interview success.

Pattern 1: Sliding Window

Use When: Contiguous subarray/substring problems

Approach:

  • Expand window by moving right pointer
  • Shrink window when condition violated (move left pointer)
  • Track best result seen so far

Time: O(n) | Space: O(1) or O(k) for hash map

Classic Problems:

  • Longest Substring Without Repeating Characters
  • Minimum Window Substring
  • Maximum Sum Subarray of Size K
  • Longest Substring with K Distinct Characters

Template:

left = 0
for right in range(len(arr)):
    # Expand window
    add arr[right] to window

    while window_condition_violated:
        # Shrink window
        remove arr[left] from window
        left += 1

    # Update result
    result = max(result, right - left + 1)

Pattern 2: Two Pointers

Use When: Sorted array, find pairs/triplets, reverse/palindrome

Approach:

  • Two pointers start at different positions
  • Move pointers based on condition
  • Often used with sorted arrays

Time: O(n) | Space: O(1)

Classic Problems:

  • Two Sum (sorted array)
  • Remove Duplicates from Sorted Array
  • Valid Palindrome
  • Container With Most Water
  • 3Sum, 4Sum

Template:

left, right = 0, len(arr) - 1
while left < right:
    if condition_met:
        process_result()
        left += 1
        right -= 1
    elif sum < target:
        left += 1
    else:
        right -= 1

Pattern 3: Fast & Slow Pointers

Use When: Detect cycles, find middle, find kth from end

Approach:

  • Fast pointer moves 2 steps
  • Slow pointer moves 1 step
  • When fast reaches end, slow is at middle

Time: O(n) | Space: O(1)

Classic Problems:

  • Detect Cycle in Linked List
  • Find Middle of Linked List
  • Linked List Cycle II (find cycle start)
  • Happy Number
  • Palindrome Linked List

Pattern 4: Binary Search

Use When: Sorted data, search space can be halved

Approach:

  • Define search space [left, right]
  • Check middle element
  • Eliminate half based on comparison

Time: O(log n) | Space: O(1)

Classic Problems:

  • Binary Search
  • First Bad Version
  • Search in Rotated Sorted Array
  • Find Peak Element
  • Search a 2D Matrix

Pattern 5: Merge Intervals

Use When: Overlapping intervals, scheduling

Approach:

  • Sort intervals by start time
  • Iterate and merge overlapping

Time: O(n log n) | Space: O(n)

Classic Problems:

  • Merge Intervals
  • Insert Interval
  • Meeting Rooms I & II
  • Non-overlapping Intervals

Pattern 6: Breadth-First Search (BFS)

Use When: Level-order traversal, shortest path in unweighted graph

Approach:

  • Use queue (FIFO)
  • Process level by level
  • Mark visited to avoid cycles

Time: O(V + E) | Space: O(V)

Classic Problems:

  • Binary Tree Level Order Traversal
  • Minimum Depth of Binary Tree
  • Number of Islands (alternative to DFS)
  • Word Ladder
  • Rotting Oranges

Pattern 7: Depth-First Search (DFS)

Use When: Explore all paths, backtracking, tree/graph traversal

Approach:

  • Use recursion or stack
  • Go deep before going wide
  • Backtrack when needed

Time: O(V + E) | Space: O(V) for recursion stack

Classic Problems:

  • Number of Islands
  • Clone Graph
  • Path Sum in Binary Tree
  • Course Schedule (cycle detection)
  • Word Search in Grid

Pattern 8: Backtracking

Use When: Generate all combinations/permutations, constraint satisfaction

Approach:

  • Make a choice
  • Explore with that choice
  • Undo choice (backtrack)
  • Try next choice

Time: O(2^n) or O(n!) typically | Space: O(n)

Classic Problems:

  • Permutations
  • Combinations
  • Subsets
  • N-Queens
  • Generate Parentheses
  • Palindrome Partitioning

Template:

def backtrack(state, choices):
    if is_solution(state):
        add_to_results(state)
        return

    for choice in choices:
        make_choice(choice)
        backtrack(new_state, remaining_choices)
        undo_choice(choice)  # Backtrack!

Pattern 9: Dynamic Programming

Use When: Optimal substructure + overlapping subproblems

Approach:

  • Define state
  • Find recurrence relation
  • Memoize (top-down) or tabulate (bottom-up)

Time: O(n²) typically | Space: O(n) or O(n²)

Classic Problems:

  • Fibonacci, Climbing Stairs
  • Coin Change
  • Longest Common Subsequence
  • 0/1 Knapsack
  • Edit Distance
  • Longest Increasing Subsequence

Pattern 10: Greedy

Use When: Local optimal choices lead to global optimal

Approach:

  • Make best choice at each step
  • Don’t reconsider past choices
  • Prove greedy choice is safe

Time: Varies | Space: Usually O(1)

Classic Problems:

  • Jump Game
  • Gas Station
  • Meeting Rooms II
  • Minimum Platforms
  • Fractional Knapsack

Pattern 11: Topological Sort

Use When: Dependency resolution, task scheduling

Approach:

  • Kahn’s Algorithm (BFS with in-degree)
  • DFS with post-order traversal
  • Detect cycles (impossible to sort if cycle exists)

Time: O(V + E) | Space: O(V + E)

Classic Problems:

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

Pattern 12: Union-Find (Disjoint Set)

Use When: Connectivity, grouping, cycle detection

Approach:

  • Union: Connect two elements
  • Find: Determine which set element belongs to
  • Use path compression + union by rank

Time: O(α(n)) ≈ O(1) with optimizations | Space: O(n)

Classic Problems:

  • Number of Connected Components
  • Graph Valid Tree
  • Accounts Merge
  • Redundant Connection
  • Number of Islands II

Pattern 13: Top K Elements

Use When: Finding k largest/smallest, k closest, k frequent

Approach:

  • Use min/max heap of size k
  • For k largest: use min heap
  • For k smallest: use max heap

Time: O(n log k) | Space: O(k)

Classic Problems:

  • Kth Largest Element
  • Top K Frequent Elements
  • K Closest Points to Origin
  • Find K Pairs with Smallest Sums
  • Reorganize String

Pattern 14: Modified Binary Search

Use When: Sorted but rotated/modified, find boundary

Approach:

  • Identify which half is sorted
  • Check if target in sorted half
  • Search appropriate half

Time: O(log n) | Space: O(1)

Classic Problems:

  • Search in Rotated Sorted Array
  • Find Minimum in Rotated Sorted Array
  • Find First and Last Position
  • Single Element in Sorted Array

Pattern 15: Monotonic Stack/Queue

Use When: Next greater/smaller element, sliding window max/min

Approach:

  • Maintain increasing or decreasing order in stack/deque
  • Remove elements that violate monotonic property
  • Each element added and removed once → O(n)

Time: O(n) | Space: O(n)

Classic Problems:

  • Next Greater Element
  • Daily Temperatures
  • Sliding Window Maximum
  • Largest Rectangle in Histogram
  • Trapping Rain Water

How to Identify the Pattern

Keyword/Clue Pattern
Contiguous subarray/substring Sliding Window
Find pairs, sorted array Two Pointers
Cycle detection, find middle Fast & Slow Pointers
Sorted array, O(log n) Binary Search
Overlapping intervals Merge Intervals
Shortest path, level order BFS
All paths, graph/tree traversal DFS
Generate all combinations Backtracking
Optimal substructure Dynamic Programming
Local optimum → global Greedy
Dependencies, prerequisites Topological Sort
Connectivity, grouping Union-Find
K largest/smallest/frequent Top K Elements (Heap)
Next greater/smaller Monotonic Stack

Study Strategy

  1. Learn one pattern at a time (1-2 patterns per week)
  2. Solve 5-10 problems using that pattern
  3. Understand why the pattern works, don’t just memorize
  4. Mix patterns after learning all 15
  5. Practice identifying which pattern to use

Master these 15 patterns and you’ll be prepared for 90% of coding interviews!

Scroll to Top