Skip to content
Interview Prep
DSA Patterns: The Cheatsheet for Coding Interviews

DSA Patterns: The Cheatsheet for Coding Interviews

DodaTech Updated Jun 20, 2026 10 min read

DSA (Data Structures & Algorithms) patterns are reusable solution blueprints that map to common problem types. Instead of memorizing thousands of problems, learn 15 patterns that cover 90% of coding interview questions.

Learning Path 

    flowchart LR
  A["DSA Review<br/>Foundations"] --> B["DSA Patterns<br/>Cheatsheet"]
  B --> C["System Design<br/>Prep"]
  C --> D["Mock Interviews<br/>Practice"]
  style B fill:#f90,color:#fff,stroke-width:2px
What you’ll learn: 15 essential DSA patterns — when to use them, how to identify them from problem statements, and template code for each pattern. Why it matters: Pattern recognition is the #1 skill that separates strong candidates from average ones. Each pattern unlocks 50+ LeetCode problems. Real-world use: DodaTech’s engineering team uses these patterns daily — from parsing browser data streams (sliding window) to optimizing antivirus signature lookups (binary search).

Pattern Identification Flowchart 

    flowchart TD
  Q["Problem Statement"] --> S{Need to<br/>search?}
  S -->|Sorted array| BS["Binary Search"]
  S -->|Unsorted array| H{Need to<br/>compare pairs?}
  H -->|Yes| TP["Two Pointers"]
  H -->|No| SW{Need contiguous<br/>subarray?}
  
  SW -->|Yes| SL["Sliding Window"]
  SW -->|No| G{Graph or<br/>tree?}
  
  G -->|Shortest path| BFS["BFS"]
  G -->|Explore all paths| DFS["DFS"]
  G -->|Connected components| UF["Union-Find"]
  
  Q --> D{Need all<br/>combinations?}
  D -->|Yes| BT["Backtracking"]
  
  Q --> O{Optimization<br/>problem?}
  O -->|Yes| DP{Overlapping<br/>subproblems?}
  DP -->|Yes| DY["Dynamic Programming"]
  DP -->|No| GR["Greedy"]
  
  O -->|Top K| HK["Heap / Top K"]
  O -->|Range query| ST["Segment Tree"]

Pattern 1: Two Pointers

Use when: Problem involves a sorted array or linked list, and you need to find pairs that satisfy a condition.

def two_sum_sorted(nums, target):
    """Find two numbers in sorted array that sum to target."""
    left, right = 0, len(nums) - 1
    while left < right:
        current = nums[left] + nums[right]
        if current == target:
            return [left, right]
        elif current < target:
            left += 1
        else:
            right -= 1
    return [-1, -1]

print(two_sum_sorted([2, 7, 11, 15], 9))
print(two_sum_sorted([1, 3, 5, 7, 9], 10))

Expected output:

[0, 1]
[1, 3]

Variations: Three Sum, Remove Duplicates from Sorted Array, Container With Most Water, Trapping Rain Water.

Pattern 2: Sliding Window

Use when: Problem asks for contiguous subarray/substring that satisfies a condition — maximum/minimum/longest/shortest.

def max_sum_subarray(nums, k):
    """Find maximum sum of any contiguous subarray of size k."""
    window_sum = sum(nums[:k])
    max_sum = window_sum
    
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]
        max_sum = max(max_sum, window_sum)
    
    return max_sum

print(max_sum_subarray([2, 1, 5, 1, 3, 2], 3))
print(max_sum_subarray([1, 9, -1, -2, 7, 3, -1, 2], 4))

Expected output:

9
13

Variations: Longest Substring Without Repeating Characters, Minimum Window Substring, Permutation in String.

Pattern 3: Binary Search

Use when: Problem involves a sorted array and you need to find a specific element, boundary, or rotated point.

def binary_search(nums, target):
    """Standard binary search on sorted array."""
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

def find_peak_element(nums):
    """Find a peak element (greater than neighbors)."""
    left, right = 0, len(nums) - 1
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] > nums[mid + 1]:
            right = mid
        else:
            left = mid + 1
    return left

print(f"Index of 7: {binary_search([1, 3, 5, 7, 9, 11], 7)}")
print(f"Peak at: {find_peak_element([1, 2, 3, 5, 4, 3, 1])}")

Expected output:

Index of 7: 3
Peak at: 3

Pattern 4: BFS (Breadth-First Search)

Use when: Shortest path in unweighted graph, level-order traversal, word ladder.

from collections import deque

def bfs_shortest_path(graph, start, target):
    """Find shortest path in unweighted graph using BFS."""
    visited = {start}
    queue = deque([(start, 0)])
    
    while queue:
        node, distance = queue.popleft()
        if node == target:
            return distance
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, distance + 1))
    return -1

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
print(bfs_shortest_path(graph, 'A', 'F'))

Expected output:

2

Pattern 5: DFS (Depth-First Search)

Use when: Exploring all paths, detecting cycles, tree traversals, connected components.

def num_islands(grid):
    """Count number of islands in a grid using DFS."""
    if not grid:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    count = 0
    
    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
            return
        grid[r][c] = '0'  # mark visited
        dfs(r+1, c)
        dfs(r-1, c)
        dfs(r, c+1)
        dfs(r, c-1)
    
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)
    return count

grid = [
    ['1', '1', '0', '0', '0'],
    ['1', '1', '0', '0', '0'],
    ['0', '0', '1', '0', '0'],
    ['0', '0', '0', '1', '1']
]
print(num_islands(grid))

Expected output:

3

Pattern 6: Backtracking

Use when: Problem requires all combinations, permutations, or subsets. If you need to enumerate all solutions.

def permute(nums):
    """Generate all permutations of an array."""
    result = []
    
    def backtrack(path, remaining):
        if not remaining:
            result.append(path[:])
            return
        for i, num in enumerate(remaining):
            path.append(num)
            backtrack(path, remaining[:i] + remaining[i+1:])
            path.pop()
    
    backtrack([], nums)
    return result

print(permute([1, 2, 3]))

Expected output:

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Pattern 7: Dynamic Programming

Use when: Problem has optimal substructure and overlapping subproblems. Maximization or minimization with choices.

0/1 Knapsack 

def knapsack(weights, values, capacity):
    """0/1 Knapsack: maximize value within weight capacity."""
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(
                    values[i-1] + dp[i-1][w - weights[i-1]],
                    dp[i-1][w]
                )
            else:
                dp[i][w] = dp[i-1][w]
    return dp[n][capacity]

print(knapsack([2, 3, 4, 5], [3, 4, 5, 6], 5))
print(knapsack([1, 2, 3], [6, 10, 12], 5))

Expected output:

7
22

Longest Common Subsequence (LCS) 

def lcs(text1, text2):
    """Find length of longest common subsequence."""
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = 1 + dp[i-1][j-1]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

print(lcs("abcde", "ace"))
print(lcs("abc", "abc"))
print(lcs("abc", "def"))

Expected output:

3
3
0

Pattern 8: Top K (Heap)

Use when: Problem asks for K largest/smallest/sorted elements from a collection.

import heapq

def top_k_frequent(nums, k):
    """Return the k most frequent elements."""
    freq = {}
    for num in nums:
        freq[num] = freq.get(num, 0) + 1
    
    # Min heap of size k
    heap = []
    for num, count in freq.items():
        heapq.heappush(heap, (count, num))
        if len(heap) > k:
            heapq.heappop(heap)
    
    return [num for count, num in heap]

print(top_k_frequent([1, 1, 1, 2, 2, 3], 2))
print(top_k_frequent([4, 4, 4, 4, 5, 5, 5, 6, 6, 7], 3))

Expected output:

[2, 1]
[6, 5, 4]

Pattern 9: Union-Find (Disjoint Set)

Use when: Dynamic connectivity, detecting cycles in undirected graph, number of connected components.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            self.parent[px] = py
        elif self.rank[px] > self.rank[py]:
            self.parent[py] = px
        else:
            self.parent[py] = px
            self.rank[px] += 1
        return True
    
    def connected(self, x, y):
        return self.find(x) == self.find(y)

# Example: Find if path exists in graph
uf = UnionFind(6)
edges = [(0, 1), (1, 2), (3, 4), (4, 5)]
for u, v in edges:
    uf.union(u, v)

print(uf.connected(0, 2))
print(uf.connected(0, 3))
print(uf.connected(3, 5))

Expected output:

True
False
True

How to Identify the Pattern from a Problem Statement

When you read a problem, ask these questions in order:

QuestionPattern
Is the input sorted or can be sorted?Two Pointers or Binary Search
Need contiguous subarray/substring?Sliding Window
Shortest path or level-order?BFS
All paths, combinations, permutations?Backtracking
Connected components or cycle detection?Union-Find
Optimize with choices?DP or Greedy
Need top K elements?Heap
Need range queries?Segment Tree / Fenwick

Common DSA Pattern Mistakes

  1. Jumping to code before pattern identification — Spend 2-3 minutes analyzing the problem. Choose your pattern before writing a single line. The wrong pattern leads to the wrong solution.
  2. Using DP when greedy works — Greedy is simpler and faster. Only use DP when you’ve confirmed the problem has overlapping subproblems. Classic trap: coin change (DP) vs activity selection (greedy).
  3. Forgetting edge cases in binary search — Off-by-one errors are the most common bug. Use left <= right for standard search, left < right for boundary search. Always test with single-element arrays.
  4. BFS vs DFS confusion — BFS finds shortest path; DFS explores all paths. If you need shortest path and use DFS, you’ll explore exponentially more nodes.
  5. Not handling visited nodes in graph problems — Forgetting to mark nodes as visited causes infinite loops or exponential runtime. Always initialize a visited set.
  6. Backtracking without pruning — Unoptimized backtracking explores all branches. Add pruning conditions: sort first to skip duplicates, check partial validity before recursing deeper.
  7. Heap direction confusion — Min heap for K largest, max heap for K smallest. Python’s heapq is a min heap. For max heap behavior, insert negative values.

Practice Questions

1. Which pattern should you use for “Find the longest substring without repeating characters”? Sliding window — the problem asks for a contiguous substring with a constraint.

2. When would you choose DFS over BFS? When you need to explore all paths, when memory is limited (DFS uses less memory for deep graphs), or when you need to detect cycles.

3. What’s the time complexity of the Union-Find with path compression? O(alpha(n)) — inverse Ackermann function, nearly constant for all practical input sizes.

4. How do you identify a DP problem? Optimal substructure (solution depends on subproblems) + overlapping subproblems (same subproblems solved multiple times). Common keywords: “minimum”, “maximum”, “number of ways”.

5. Challenge: Pattern identification For each problem below, identify the pattern(s) needed:

  • “Find all palindrome substrings in a string”
  • “Serialize and deserialize a binary tree”
  • “Merge K sorted linked lists”
  • “Word ladder II (all shortest transformation sequences)”

Answers: (1) Two pointers or DP, (2) BFS/DFS for serialization, (3) Heap (Top K pattern), (4) BFS + Backtracking.

Mini Project: Pattern Classifier 

def classify_problem(statement):
    """Classify a problem statement into DSA patterns."""
    keywords = {
        "two pointers": ["sorted", "pair", "three sum", "container"],
        "sliding window": ["subarray", "substring", "contiguous", "longest"],
        "binary search": ["sorted", "rotated", "peak", "search"],
        "bfs": ["shortest path", "level", "minimum distance"],
        "dfs": ["island", "connected", "path exists", "all paths"],
        "backtracking": ["combinations", "permutations", "subsets"],
        "dynamic programming": ["maximum", "minimum", "ways", "optimal"],
        "heap": ["k largest", "k smallest", "top k", "frequent"],
        "union find": ["connected", "cycle", "redundant", "components"],
    }
    
    matched = []
    statement_lower = statement.lower()
    for pattern, words in keywords.items():
        if any(w in statement_lower for w in words):
            matched.append(pattern)
    return matched or ["No pattern confidently identified"]

problems = [
    "Find the longest substring with at most K distinct characters",
    "Find K closest points to origin",
    "Find if there is a path between two nodes in a graph",
]
for p in problems:
    print(f"{p}")
    print(f"  → {classify_problem(p)}\n")

Expected output:

Find the longest substring with at most K distinct characters
  → ['sliding window']

Find K closest points to origin
  → ['heap']

Find if there is a path between two nodes in a graph
  → ['dfs', 'union find']

FAQ

How many patterns do I need to know for FAANG interviews?
15 core patterns cover 90% of coding interview questions. Focus on mastering these before moving to advanced patterns like segment trees or tries.
Should I memorize pattern templates?
Learn the structure and adapt. Pure memorization fails when the problem has a twist. Understand WHY the template works so you can modify it.
How do I practice pattern recognition?
Read the problem, identify the pattern BEFORE looking at solutions. Use the flowchart in this guide. After solving, categorize the problem by pattern in a spreadsheet.
What if a problem fits multiple patterns?
Many problems do. Start with the simplest pattern that could work (greedy before DP, two pointers before binary search) and escalate complexity only if needed.
How long does it take to master these patterns?
Most engineers need 4-8 weeks of consistent practice (1-2 problems daily) to reach interview readiness. Pattern recognition becomes intuitive after about 50-80 problems.

Related Tutorials

Behavioral Questions Guide
Previous
System Design Prep
Next
DSA Review
Related

Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro. Updated 2026-06-20.

Previous Behavioral Interview Questions: The STAR Method Guide Next System Design Interview: Complete Preparation Guide

Built by the developers of DodaTech

Doda Browser, DodaZIP & Durga Antivirus Pro

Home Browse Interview Prep