# The 28 Coding Interview Patterns Cheat Sheet: Constraint-to-Algorithm Mapping for FAANG Loops

> Stop memorizing 1,000 disconnected LeetCode solutions. Use input constraints, data properties, and output shapes to identify the exact optimal pattern in under 30 seconds.

- **Author:** Former Amazon Software Engineer (Crush the FAANG Interview)
- **Category:** Coding Patterns
- **Updated:** 2026-11-20
- **Canonical URL:** https://crushthefaanginterview.com/blog/28-coding-interview-patterns-cheat-sheet

## Key Takeaways
- Input size N instantly eliminates infeasible time complexities: N <= 20 allows O(2^N) backtracking/bitmasking; N <= 10^5 requires O(N log N) or O(N).
- Sorted arrays or monotonic predicates point directly to Two Pointers or Binary Search on Answer Spaces.
- Contiguous subarray constraints with non-negative weights map to Sliding Window; negative weights require Prefix Sums + Hash Map.
- Streaming top-K or running medians map to Heaps / Two Heaps in O(log K) per update.

## 1. Read the Input Constraints Before Writing Code

In 45-minute coding rounds at Meta, Google, and Amazon, candidates lose the first 12 minutes guessing data structures instead of reading the input bounds. Every constraint in an interview prompt is a mathematical hint telling you which complexity class passes stress tests.

Before touching the keyboard, translate the maximum input size N into an upper bound of ~10^7 operations per test case in Python:

| Input Bound (N) | Target Time Complexity | Primary Coding Patterns |
| --- | --- | --- |
| N <= 18..20 | O(2^N) or O(N!) | Subsets, Permutations, Backtracking, Bitmask DP |
| N <= 400..500 | O(N^3) or O(N^2 log N) | 3D Dynamic Programming, Interval DP, Floyd-Warshall |
| N <= 2,000..5,000 | O(N^2) | 2D DP, Fix-One-Index + Two Pointers (3Sum), BFS/DFS on dense grids |
| N <= 10^5..2*10^5 | O(N log N) or O(N) | Sliding Window, Two Pointers, Heaps, Merge Intervals, Monotonic Stack, Union-Find |
| N >= 10^9 (or search range) | O(log N) or O(1) | Modified Binary Search on Answer Space, Bitwise Manipulation, Math |

## 2. Cue-to-Pattern Decision Matrix Across All 28 Patterns

Across our 540 verified Python problems in Crush the FAANG Interview, over 90% of coding rounds reduce to recognizing structural invariants:

| Prompt Signal / Structure | Optimal Pattern | Canonical Invariant |
| --- | --- | --- |
| Sorted array + pair/triplet target sum or palindrome | Two Pointers | Each pointer move Permanently discards an entire row or column of pairs in O(1). |
| Linked list cycle, middle node, or duplicate number in 1..N | Fast & Slow Pointers | Tortoise (1x) and Hare (2x) meet inside any cycle in O(N) time and O(1) space. |
| Longest/shortest contiguous subarray satisfying a window budget | Sliding Window | Expand right pointer to gather state; shrink left pointer while constraint breaks. |
| Overlapping meetings, calendars, or resource timelines | Merge Intervals + Min-Heap | Sort by start time; active end times in a min-heap equal concurrent rooms needed. |
| Minimum capacity / speed / k-th smallest where feasibility is monotonic | Modified Binary Search | Binary search over [low, high] using an O(N) greedy check(mid) predicate. |
| Next greater/smaller element, histogram area, or stock span | Monotonic Stack | Each index is pushed once and popped once, yielding strict O(N) amortized time. |
| Prerequisite ordering, build dependency graph, or cycle detection | Topological Sort (Kahn BFS) | Repeatedly dequeue zero-indegree nodes; visited < V proves a cycle exists. |
| Dynamic connectivity, redundant edges, or merging accounts | Union-Find (DSU) | Path compression + union by rank answers connectivity queries in O(alpha(N)). |

## 3. Reusable Python 3.14 Sliding Window Template

Instead of writing ad-hoc while-loops with off-by-one bugs, anchor your implementation around a single loop invariant where [left..right] is always valid at the bottom of each iteration:

```python
def longest_valid_subarray(nums: list[int], limit: int) -> int:
    left = 0
    window_sum = 0
    best = 0

    for right, val in enumerate(nums):
        window_sum += val
        while window_sum > limit:
            window_sum -= nums[left]
            left += 1
        # Invariant holds: nums[left : right + 1] has sum <= limit
        best = max(best, right - left + 1)

    return best
```

## Frequently Asked Questions

### How many coding patterns are needed for FAANG interviews?

28 core patterns—including Two Pointers, Sliding Window, Modified Binary Search, Heaps, Trees, Graphs, Topological Sort, Union-Find, Tries, Backtracking, and Dynamic Programming—cover virtually every standard L3–L6 SWE coding round.

### Should I memorize problem solutions or pattern invariants?

Always learn the underlying invariant (why moving a pointer or popping a monotonic stack is safe). Interviewers routinely twist constraints in follow-ups, which breaks memorized code.

## Related Video & Interactive Courses
- [Two Pointers (34 Problems)](https://crushthefaanginterview.com/course/gtci-01-two-pointers)
- [Sliding Window (24 Problems)](https://crushthefaanginterview.com/course/gtci-03-sliding-window)
- [Modified Binary Search (24 Problems)](https://crushthefaanginterview.com/course/gtci-09-modified-binary-search)
- [Dynamic Programming (41 Problems)](https://crushthefaanginterview.com/course/gtci-13-dynamic-programming)
