DSA Patterns — Complete Study Guide¶

A comprehensive reference for identifying, understanding, and applying common DSA patterns in coding interviews.

How to Identify & Apply Patterns¶

1. Two Pointers¶

When to use: Sorted array or linked list. You need to find a pair, triplet, or partition elements with O(1) extra space.

Core technique: Start one pointer at the left (i = 0) and one at the right (j = n-1). Move them toward each other based on a comparison.

Template:

left, right = 0, len(arr) - 1
while left < right:
    if condition(arr[left], arr[right]):
        # found answer
    elif arr[left] + arr[right] < target:
        left += 1
    else:
        right -= 1

2. Fast & Slow Pointers¶

When to use: Cycle detection in linked lists or arrays. Finding the middle of a list. Problems involving "meeting point."

Core technique: slow moves 1 step at a time, fast moves 2. If they meet → cycle exists. After detecting a cycle, reset one pointer to head to find the cycle start.

Template:

slow, fast = head, head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if slow == fast:
        # cycle detected

3. Sliding Window¶

When to use: Contiguous subarray or substring problems. Asked for maximum/minimum/longest/shortest within a window. Key signal: "subarray of size k" or "at most k distinct."

Core technique (variable window):

left = 0
for right in range(len(arr)):
    # expand window by including arr[right]
    while window_is_invalid:
        # shrink from left
        left += 1
    update_answer()

4. Kadane's Algorithm¶

When to use: Maximum (or minimum) sum contiguous subarray. Circular subarray variants. Variants that allow one deletion.

Core technique: Track a running sum. If it goes negative, reset it. Update global max at every step.

Template:

max_sum = arr[0]
current = arr[0]
for x in arr[1:]:
    current = max(x, current + x)
    max_sum = max(max_sum, current)

5. Prefix Sum¶

When to use: Range sum queries. Counting subarrays with a target sum. Divisibility of subarrays. "Number of subarrays where sum equals k."

Core technique: Build a running sum array. Use a hashmap to track how many times each prefix sum has been seen.

Template:

prefix = 0
count = 0
seen = {0: 1}
for x in arr:
    prefix += x
    count += seen.get(prefix - target, 0)
    seen[prefix] = seen.get(prefix, 0) + 1

6. Merge Intervals¶

When to use: Problems involving ranges, schedules, or time intervals. "Merge overlapping," "find free time," "minimum rooms needed."

Core technique: Sort by start time. Compare current interval's end with next interval's start.

Template:

intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for start, end in intervals[1:]:
    if start <= merged[-1][1]:
        merged[-1][1] = max(merged[-1][1], end)
    else:
        merged.append([start, end])

7. In-place Reversal of a LinkedList¶

When to use: Reverse a portion (or all) of a linked list without extra space. "Reverse every k-group," "rotate list."

Core technique: Keep track of prev, current, and next. Redirect current.next to prev, then advance.

Template:

prev = None
current = head
while current:
    next_node = current.next
    current.next = prev
    prev = current
    current = next_node
return prev

8. Heap / Top-K Elements¶

When to use: "Top K," "K closest," "K largest/smallest," "Kth largest," "Median from a data stream." Use a min-heap of size K to track top-K largest elements.

Core technique: - Top K largest → min-heap of size K (pop when size > K) - Top K smallest → max-heap of size K - Median → two heaps: max-heap for lower half, min-heap for upper half

9. Binary Search¶

When to use: Sorted array. "Find minimum/maximum satisfying a condition." Search space that is monotone (answer is feasible on one side, not the other). Key signal: O(log n) expected complexity.

Template (find leftmost condition):

lo, hi = 0, len(arr) - 1
while lo < hi:
    mid = (lo + hi) // 2
    if condition(mid):
        hi = mid
    else:
        lo = mid + 1
return lo

10. Tree BFS (Level Order)¶

When to use: Level-by-level traversal. "Average of levels," "right side view," "zigzag traversal," "connect level nodes."

Core technique: Use a queue. At each level, process all nodes currently in the queue (that's one level).

Template:

from collections import deque
queue = deque([root])
while queue:
    level_size = len(queue)
    for _ in range(level_size):
        node = queue.popleft()
        # process node
        if node.left:  queue.append(node.left)
        if node.right: queue.append(node.right)

11. Tree DFS¶

When to use: Path sum problems. "All root-to-leaf paths," "validate BST," "lowest common ancestor," diameter problems.

Core technique: Recursive pre/in/post-order traversal. Pass state down (e.g. current sum) and accumulate results up.

12. Backtracking¶

When to use: All combinations / permutations / subsets. Constraint satisfaction (N-Queens, Sudoku). "Generate all valid…"

Core technique: Make a choice → recurse → undo the choice (backtrack).

Template:

def backtrack(start, path):
    if is_solution(path):
        results.append(list(path))
        return
    for choice in choices(start):
        path.append(choice)
        backtrack(next_start, path)
        path.pop()  # undo

13. Dynamic Programming¶

When to use: "How many ways," "minimum cost," "maximum profit," overlapping subproblems where brute force recurses into the same state multiple times.

Key sub-patterns:

14. Graph BFS / DFS¶

When to use: Connected components, shortest path in unweighted graph, "number of islands," "rotting oranges," reachability.

Template (BFS):

from collections import deque
visited = set([start])
queue = deque([start])
while queue:
    node = queue.popleft()
    for neighbor in graph[node]:
        if neighbor not in visited:
            visited.add(neighbor)
            queue.append(neighbor)

15. Topological Sort¶

When to use: Ordering tasks with dependencies. "Course prerequisites," "build order," "detect cycle in directed graph."

Core technique (Kahn's BFS): Find all nodes with in-degree 0, process them, reduce neighbors' in-degrees, repeat.

16. Union-Find (Disjoint Set Union)¶

When to use: Group/connect components dynamically. "Number of connected components," "detect cycle in undirected graph," "accounts merge."

Template:

parent = list(range(n))
rank = [0] * n

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])  # path compression
    return parent[x]

def union(x, y):
    px, py = find(x), find(y)
    if px == py: return False
    if rank[px] < rank[py]: px, py = py, px
    parent[py] = px
    if rank[px] == rank[py]: rank[px] += 1
    return True

17. Monotonic Stack¶

When to use: "Next greater element," "next smaller element," "largest rectangle in histogram," "trapping rain water." The stack maintains a monotonically increasing or decreasing order.

Template (next greater element):

stack = []
result = [-1] * len(arr)
for i, val in enumerate(arr):
    while stack and arr[stack[-1]] < val:
        result[stack.pop()] = val
    stack.append(i)

18. Trie¶

When to use: Prefix search, autocomplete, "word search in a board," "longest common prefix," problems involving a dictionary of words.

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 ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True
    def search(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children: return False
            node = node.children[ch]
        return node.is_end

19. HashMap / HashSet¶

When to use: O(1) lookups. Anagram detection, two-sum variants, frequency counting, "first duplicate," "group by."

20. Bit Manipulation¶

When to use: Problems involving XOR (finding unique elements), counting set bits, checking powers of 2, subsets via bitmask.

Common tricks:

Quick Pattern Decision Tree¶

Is the input sorted?
├── Yes → Two Pointers or Binary Search
│         └── Finding pairs/triplets → Two Pointers
│         └── Finding a value / min-max condition → Binary Search
└── No  → Continue below

Is it a subarray/substring problem?
├── Fixed size window → Sliding Window (fixed)
├── Variable size window → Sliding Window (variable) or Prefix Sum
└── Max/min sum subarray → Kadane's

Is it a tree?
├── Level-by-level → BFS
└── Path / depth / ancestor → DFS

Is it a graph?
├── Shortest path, unweighted → BFS
├── Shortest path, weighted → Dijkstra
├── Dependency ordering → Topological Sort
└── Connectivity / grouping → Union-Find

Is it "how many ways" or "min cost"?
└── Dynamic Programming

Is it "all combinations / all subsets"?
└── Backtracking

Does it involve ranges/intervals?
└── Merge Intervals (sort by start time)

Is it about cycles in a linked list?
└── Fast & Slow Pointers

Is it about top/bottom K elements?
└── Heap

Does it involve prefix/word search?
└── Trie

Last updated: June 2026. All LeetCode links point to the problem description page.