Recognizing Patterns in Problems

Every algorithm you have studied so far taught you one tool at a time: sort with this, search with that, traverse a tree this way. Real problems, especially in coding interviews, do not announce which tool to use. Recognizing patterns is the meta-skill that lets you look at an unfamiliar problem and quickly narrow it down to a small set of proven techniques — two pointers, sliding window, fast and slow pointers, hashing, backtracking, dynamic programming, breadth-first search, and heaps — instead of starting from a blank page every time. This lesson trains that recognition muscle directly.

Overview: What Pattern Recognition Really Means

Suppose you are asked: “Given a sorted array of integers, find two numbers that add up to a target value.” A beginner might reach for two nested loops, checking every pair — that works, but it is O(n^2). An experienced solver notices two things about the problem’s shape: the array is sorted, and the answer is a pair. Sortedness is the signal for the two-pointer pattern: start one pointer at each end, and move whichever pointer helps you close the gap toward the target. That single observation turns an O(n^2) search into an O(n) one. Pattern recognition is exactly this: matching a problem’s shape to a technique before you write a single line of code.

This works because the overwhelming majority of problems you will encounter — in coursework, in interviews, and in real systems — are variations on a small number of underlying shapes. Once you have solved one “two pointers on a sorted array” problem, you have effectively solved a hundred of them, because the recognition step, not the implementation, is the hard part. The table below is a starting cheat sheet; you will extend it yourself as you practice.

Signal in the Problem Likely Pattern Typical Complexity Win
Sorted array, need a pair or triplet summing to a target Two pointers O(n^2) to O(n)
Contiguous subarray or substring, fixed or variable size Sliding window O(n^2) to O(n)
Linked list; need a cycle, a middle node, or Nth-from-end Fast and slow pointers O(n) space to O(1) space
Need to know “have I seen this value before” quickly Hashing (set or dict) O(n^2) to O(n)
Explore all combinations or paths, prune invalid ones Backtracking Exponential, pruned
Overlapping subproblems with optimal substructure Dynamic programming Exponential to polynomial
Shortest path or level-by-level spread in an unweighted graph Breadth-first search O(V + E)
“Kth largest,” “top K,” or a running median Heap or priority queue O(n log k)

A Recognition Checklist

When you meet a new problem, work through these questions before writing any code:

  1. What is the input’s shape and any special property? Is it sorted? A linked list? A graph? A string?
  2. What is actually being asked for — a single value, every combination, the shortest path, or the Kth item?
  3. Would checking “have I seen this value before” help? That points toward hashing.
  4. Is the answer built from a contiguous run of elements? That points toward a sliding window.
  5. Does the brute-force solution repeat the same subproblem many times? That points toward dynamic programming.

Time and Space Complexity: Why the Pattern Matters

Recognizing the right pattern is, in almost every case, the difference between an O(n^2) or worse brute-force solution and an O(n) or O(n log n) pattern-based one. The table below summarizes the patterns covered in this course and the complexity they typically unlock, along with the space cost you trade for that speed.

Pattern Typical Time Typical Space Why
Two pointers O(n) O(1) Each pointer moves at most n steps in total across the whole run; sortedness lets you discard half of the remaining possibilities at every step.
Sliding window O(n) O(1) to O(k) Each element enters and leaves the window at most once, so total work is linear even though the code looks like it could be nested.
Fast and slow pointers O(n) O(1) Avoids the O(n) extra memory a hash set of visited nodes would otherwise require.
Hashing (set or dict) O(n) average O(n) Trades memory for average O(1) membership checks instead of an O(n) linear scan through a list.
Dynamic programming O(n) to O(n^2), problem-dependent O(n), often reducible to O(1) Caches each subproblem’s answer so it is computed once instead of exponentially many times.

Notice the trade-off: two pointers and fast/slow pointers reach linear time with constant extra space, because they exploit structure already present in the input — sortedness, or the shape of a linked list. Hashing also reaches linear time, but pays for it with linear extra memory. Picking the wrong pattern is not just inelegant; on a large enough input it is the difference between a solution that finishes in milliseconds and one that times out.

Examples

Example 1: Two Pointers on a Sorted Array

The signal here is unmistakable once you look for it: the array is sorted, and you need a pair that sums to a target. That is the two-pointer pattern. Instead of comparing every pair (O(n^2)), you place one pointer at the start and one at the end, and let the sorted order tell you which pointer to move.

def two_sum_sorted(numbers: list[int], target: int) -> tuple[int, int] | None:
    left, right = 0, len(numbers) - 1
    while left < right:
        current_sum = numbers[left] + numbers[right]
        if current_sum == target:
            return (left, right)
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return None


def main() -> None:
    numbers = [2, 7, 11, 15, 18, 24]
    target = 29
    result = two_sum_sorted(numbers, target)
    print(f"Indices: {result}")
    if result:
        i, j = result
        print(f"Values: {numbers[i]} + {numbers[j]} = {target}")


main()

Output:

Indices: (2, 4)
Values: 11 + 18 = 29

Trace it by hand: left = 0 and right = 5 give 2 + 24 = 26, which is less than 29, so left moves up. left = 1, right = 5 gives 7 + 24 = 31, too big, so right moves down. left = 1, right = 4 gives 7 + 18 = 25, too small, so left moves up again. Finally left = 2, right = 4 gives 11 + 18 = 29, a match. Each comparison eliminates one end of the search space, which is why this never revisits a pair and finishes in O(n) time.

Example 2: Sliding Window for a Maximum Subarray Sum

Here the signal is a contiguous subarray of a fixed size k. Recomputing the sum of every window from scratch would be O(n * k). The sliding window pattern instead keeps a running sum and updates it by subtracting the element that leaves the window and adding the element that enters it.

def max_sum_subarray(nums: list[int], k: int) -> int:
    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


def main() -> None:
    nums = [2, 1, 5, 1, 3, 2]
    k = 3
    result = max_sum_subarray(nums, k)
    print(f"Maximum sum of window size {k}: {result}")


main()

Output:

Maximum sum of window size 3: 9

The window starts as the first three elements, [2, 1, 5], summing to 8. As the window slides, it becomes [1, 5, 1] (subtract 2, add 1: sum 7), then [5, 1, 3] (subtract 1, add 3: sum 9, a new maximum), then [1, 3, 2] (subtract 5, add 2: sum 6). The maximum observed, 9, is the answer. Each element is added once and subtracted once, so the total work is O(n) regardless of k.

Example 3: Fast and Slow Pointers for Cycle Detection

The signal is a linked list combined with a question about its structure — here, whether it loops back on itself. Keeping a hash set of every visited node would work but costs O(n) extra space. The fast/slow pointer pattern (Floyd’s cycle detection) does it in O(1) space: a slow pointer advances one node at a time, a fast pointer advances two, and if there is a cycle they are guaranteed to meet inside it.

class ListNode:
    def __init__(self, value: int) -> None:
        self.value = value
        self.next: "ListNode | None" = None


def has_cycle(head: "ListNode | None") -> bool:
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False


def main() -> None:
    node1 = ListNode(1)
    node2 = ListNode(2)
    node3 = ListNode(3)
    node4 = ListNode(4)
    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node2  # creates a cycle back to node2

    print(f"Cyclic list has cycle: {has_cycle(node1)}")

    node10 = ListNode(10)
    node20 = ListNode(20)
    node30 = ListNode(30)
    node10.next = node20
    node20.next = node30

    print(f"Linear list has cycle: {has_cycle(node10)}")


main()

Output:

Cyclic list has cycle: True
Linear list has cycle: False

In the first list, node4.next points back to node2, creating a loop. Tracing the pointers: after one step slow is at node 2 and fast is at node 3; after two steps slow is at node 3 and fast is at node 2; after three steps slow is at node 4 and fast is also at node 4 — they meet, so the function returns True. In the second list there is no cycle, so fast eventually reaches None and the loop exits normally, returning False.

How It Works Step by Step: From Signal to Solution

Recognizing a pattern is only half the job; applying it correctly means tracing the pointers precisely. Here is the two-pointer search from Example 1 traced one step at a time on numbers = [2, 7, 11, 15, 18, 24] with target = 29.

Step left right Sum Comparison Action
1 0 (value 2) 5 (value 24) 26 26 < 29 sum too small — move left right
2 1 (value 7) 5 (value 24) 31 31 > 29 sum too big — move right left
3 1 (value 7) 4 (value 18) 25 25 < 29 sum too small — move left right
4 2 (value 11) 4 (value 18) 29 29 == 29 match found — return (2, 4)

Two properties make this loop safe and efficient. First, left and right only ever move toward each other, so the loop runs at most n times total — that is what gives the O(n) bound. Second, the correctness argument depends entirely on the array being sorted: when the current sum is too small, increasing left is the only move that can increase the sum, because decreasing right can only decrease or hold it steady in a sorted array. If the array were not sorted, that guarantee disappears, which is exactly the trap in the first Common Mistake below.

Common Mistakes

Mistake 1: Applying Two Pointers to Unsorted Data

The two-pointer pattern’s correctness depends entirely on the input being sorted. Applying it to an unsorted array compiles fine, runs fine, and silently returns a wrong answer — the most dangerous kind of bug.

def two_sum_sorted_wrong(numbers: list[int], target: int) -> tuple[int, int] | None:
    left, right = 0, len(numbers) - 1
    while left < right:
        current_sum = numbers[left] + numbers[right]
        if current_sum == target:
            return (left, right)
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return None


def main() -> None:
    numbers = [11, 2, 15, 7]  # not sorted!
    target = 9
    result = two_sum_sorted_wrong(numbers, target)
    print(f"Result: {result}")


main()

Output:

Result: None

The pair 2 + 7 = 9 does exist in [11, 2, 15, 7] at indices 1 and 3, but the two-pointer logic never finds it, because moving left or right based on “too big” or “too small” only makes sense when the array is ordered. The fix is to recognize that the input lacks the property the pattern depends on, and switch signals: an unsorted array with a “have I seen the complement” question is a hashing problem, not a two-pointer one.

def two_sum_unsorted(numbers: list[int], target: int) -> tuple[int, int] | None:
    seen: dict[int, int] = {}
    for index, value in enumerate(numbers):
        complement = target - value
        if complement in seen:
            return (seen[complement], index)
        seen[value] = index
    return None


def main() -> None:
    numbers = [11, 2, 15, 7]
    target = 9
    result = two_sum_unsorted(numbers, target)
    print(f"Result: {result}")


main()

Output:

Result: (1, 3)

The corrected version uses a dictionary to remember, for each value seen so far, the index it occurred at. For every new value it checks whether target - value, the complement, has already been seen — an average O(1) check — which finds the pair on the first pass in O(n) time, at the cost of O(n) extra space for the dictionary.

Mistake 2: “Using a Hash Pattern” That Isn’t Actually Hashing

It is possible to think you have applied the hashing pattern while still writing an O(n^2) algorithm, because the bug is in the data structure, not the logic.

def contains_duplicate_slow(nums: list[int]) -> bool:
    seen = []  # BUG: list membership check is O(n), so this is really O(n^2)
    for value in nums:
        if value in seen:
            return True
        seen.append(value)
    return False


def main() -> None:
    nums = [4, 8, 2, 9, 2, 5]
    print(f"Has duplicate: {contains_duplicate_slow(nums)}")


main()

Output:

Has duplicate: True

This produces the right answer, so it is easy to miss the problem. But seen is a list, and value in seen on a list is an O(n) linear scan, not the O(1) average lookup a hash-based structure gives you. Across the whole loop that makes this O(n^2) in the worst case — the exact complexity the “recognize hashing” signal was supposed to help you avoid. The fix is a one-word change: use a set, whose in check is O(1) on average because it hashes the value instead of scanning for it.

def contains_duplicate_fast(nums: list[int]) -> bool:
    seen: set[int] = set()
    for value in nums:
        if value in seen:
            return True
        seen.add(value)
    return False


def main() -> None:
    nums = [4, 8, 2, 9, 2, 5]
    print(f"Has duplicate: {contains_duplicate_fast(nums)}")


main()

Output:

Has duplicate: True

Same output, same number of lines of code, but genuinely O(n) time now. The lesson generalizes: recognizing that a problem “needs hashing” is not enough — you have to reach for the structure, a set or dict, that actually delivers O(1) average membership checks, not just something that superficially resembles it.

Best Practices

  • Before writing any code, restate the problem in terms of the input’s shape (sorted? linked list? graph? string?) and the desired output — this alone eliminates most wrong patterns.
  • Estimate the brute-force complexity first. If it is O(n^2) or worse and the input can be large, that is your cue to hunt for a better-fitting pattern.
  • Build a personal cheat sheet mapping signals to patterns, and add to it every time you solve a new style of problem.
  • When two patterns both fit, prefer the one that uses less extra space if the time complexity is the same — for example, fast/slow pointers over a hash set for cycle detection.
  • Never force a pattern onto data that lacks the property it depends on; verify the precondition, such as “is this actually sorted?”, before applying two pointers or binary search.
  • Practice explaining out loud why a pattern applies, not just that it applies — the “why” is what transfers to the next, unfamiliar problem.

Practice Exercises

  1. Given an unsorted array of integers and a target difference k, determine whether two elements exist whose difference equals k. Which pattern applies, and why does the array being unsorted rule out (or not rule out) two pointers?
  2. Given a string, find the length of the longest substring without repeating characters. For example, "abcabcbb" should give 3 (for "abc"). Identify the pattern before writing any code, and note what data structure you need alongside it to detect repeats inside the window.
  3. Given the head of a singly linked list, return its middle node in a single pass without first counting the length. Hint: this is a variant of the fast/slow pointer pattern from Example 3 — think about where slow ends up when fast reaches the end.

Summary

  • Pattern recognition means matching a problem’s input shape and question to one of a small set of proven techniques before writing code, instead of solving each problem from scratch.
  • Sorted array plus a pair or triplet sum points to two pointers: O(n) time, O(1) space.
  • A contiguous subarray or substring points to a sliding window: O(n) time, O(1) to O(k) space.
  • Linked list structure questions, such as cycles or middle nodes, point to fast and slow pointers: O(n) time, O(1) space.
  • “Have I seen this before?” questions point to hashing with a set or dict: O(n) time on average, O(n) space — but only if you actually use a hash-based structure, not a list.
  • Always verify a pattern’s precondition, such as sortedness, before applying it; a pattern applied to data that does not satisfy its assumptions compiles and runs, but silently returns the wrong answer.