gitGood.dev
Patterns

Common Interview Patterns

PatternsFREELast updated: May 2026 · By gitGood Editorial

The recurring shapes - sliding window, two pointers, fast/slow, BFS/DFS, backtracking, DP, divide & conquer, binary search variants, union-find, topological sort. Each entry: when to reach for it, the template, complexity, and which classic problems use it.

How to use this sheet

When a problem looks new, the trick is rarely a new algorithm - it's recognizing which of these ~12 shapes it maps onto. For each pattern, the first instinct is the trigger condition ("contiguous subarray with constraint" -> sliding window; "shortest path in unweighted graph" -> BFS). Memorize the trigger first, the template second.

The patterns

Sliding window

When to use
Contiguous subarray / substring satisfying a constraint (max sum of size k, longest substring without repeating chars, smallest subarray with sum >= S, longest substring with at most k distinct chars).
Template
left = 0
state = empty
best = identity
for right in 0..n-1:
  state.add(arr[right])
  while not valid(state):
    state.remove(arr[left])
    left += 1
  best = combine(best, right - left + 1)
return best
Complexity
O(n) time, O(k) space (k = window contents - often O(1) or O(alphabet)).
Examples
  • Longest Substring Without Repeating Characters
  • Minimum Window Substring
  • Longest Substring with At Most K Distinct Characters
  • Maximum Sum Subarray of Size K (fixed window)
  • Permutation in String

Two pointers (opposite ends)

When to use
Sorted array, palindrome check, pair / triplet with target sum, container-with-most-water-style optimization.
Template
left = 0
right = n - 1
while left < right:
  s = combine(arr[left], arr[right])
  if s == target: return ...
  elif s < target: left += 1
  else: right -= 1
Complexity
O(n) after an O(n log n) sort if input is unsorted. 3-Sum is O(n^2) (outer loop + 2-pointer inner).
Examples
  • Two Sum II (sorted)
  • Valid Palindrome
  • Container With Most Water
  • 3-Sum / 4-Sum
  • Trapping Rain Water (two-pointer variant)

Fast / slow pointers (Floyd's tortoise & hare)

When to use
Cycle detection in linked list / functional graph, finding the middle of a list, finding the cycle entry, duplicate detection in [1..n] array (treated as linked list).
Template
slow = head
fast = head
while fast and fast.next:
  slow = slow.next
  fast = fast.next.next
  if slow == fast: cycle detected
# To find cycle entry: reset one pointer to head, advance both by 1 until they meet again.
Complexity
O(n) time, O(1) space.
Examples
  • Linked List Cycle / Linked List Cycle II
  • Find the Duplicate Number
  • Middle of the Linked List
  • Happy Number
  • Palindrome Linked List

BFS (breadth-first search)

When to use
Shortest path in an unweighted graph or grid, level-order traversal of a tree, multi-source shortest path (rotting oranges, 01-matrix), word ladder.
Template
queue = deque([start])
visited = {start}
dist = {start: 0}
while queue:
  node = queue.popleft()
  for nxt in neighbors(node):
    if nxt not in visited:
      visited.add(nxt)
      dist[nxt] = dist[node] + 1
      queue.append(nxt)
Complexity
O(V + E) time, O(V) space.
Examples
  • Word Ladder
  • Rotting Oranges
  • Shortest Path in Binary Matrix
  • Binary Tree Level Order Traversal
  • 01 Matrix

DFS (depth-first search)

When to use
Tree / graph traversal, connectivity, cycle detection, path enumeration, topological sort, articulation points / bridges, flood fill.
Template
def dfs(node, visited):
  if node in visited: return
  visited.add(node)
  pre_order_work(node)
  for nxt in neighbors(node):
    dfs(nxt, visited)
  post_order_work(node)
# Iterative variant: use an explicit stack.
Complexity
O(V + E) time, O(V) space (recursion depth).
Examples
  • Number of Islands
  • Clone Graph
  • Course Schedule (cycle detection in directed graph)
  • Path Sum II
  • All Paths From Source to Target

Backtracking

When to use
Enumerate / search a combinatorial space (subsets, permutations, combinations, n-queens, sudoku, word search). Recurse, mutate, recurse, undo.
Template
def backtrack(state, choices):
  if is_solution(state):
    record(state)
    return
  for choice in choices:
    if not feasible(state, choice): continue
    apply(state, choice)
    backtrack(state, remaining(choices, choice))
    undo(state, choice)
Complexity
Exponential in the worst case (subsets O(2^n), permutations O(n!)). Pruning is the difference between accepted and TLE.
Examples
  • Subsets / Subsets II
  • Permutations / Permutations II
  • Combination Sum
  • N-Queens
  • Word Search
  • Sudoku Solver

Dynamic programming - 1D

When to use
State depends on a single index. Examples: "longest / count / min / max" over a sequence with overlapping subproblems.
Template
dp = [base_case for _ in range(n)]
for i in 1..n-1:
  dp[i] = recurrence(dp[i-1], dp[i-2], ..., arr[i])
return dp[n-1] (or max(dp))
Complexity
O(n) time, O(n) space (often collapses to O(1) with rolling variables).
Examples
  • Climbing Stairs
  • House Robber
  • Maximum Subarray (Kadane)
  • Longest Increasing Subsequence (O(n^2) DP or O(n log n) patience)
  • Decode Ways

Dynamic programming - 2D

When to use
Two strings, two sequences, or a grid. State is (i, j).
Template
dp = [[base for _ in range(m+1)] for _ in range(n+1)]
for i in 1..n:
  for j in 1..m:
    dp[i][j] = recurrence(dp[i-1][j], dp[i][j-1], dp[i-1][j-1], a[i], b[j])
return dp[n][m]
Complexity
O(n * m) time, O(n * m) space (often collapses to O(min(n, m))).
Examples
  • Edit Distance
  • Longest Common Subsequence
  • Unique Paths / Unique Paths II
  • Distinct Subsequences
  • Interleaving String

DP - state machine

When to use
The problem is naturally a finite-state automaton: each state encodes "what mode are we in" (holding stock vs not, just sold vs cooled-down vs free, k transactions remaining).
Template
# Define explicit states. For "Best Time to Buy and Sell Stock with Cooldown":
# states: holding, sold (cooldown), rest
# transitions:
#   holding[i]  = max(holding[i-1], rest[i-1] - price[i])
#   sold[i]     = holding[i-1] + price[i]
#   rest[i]     = max(rest[i-1], sold[i-1])
return max(sold[n-1], rest[n-1])
Complexity
O(n * S) time where S = number of states (often constant), O(S) space.
Examples
  • Best Time to Buy/Sell Stock series (with cooldown / fee / k transactions)
  • Paint House III
  • String matching DP (regex / wildcard)
  • Maximum Profit in Job Scheduling

Divide and conquer

When to use
Problem can be split into independent subproblems whose solutions combine cheaply. Merge sort, quicksort, closest-pair, fast exponentiation, segment tree build.
Template
def solve(arr, lo, hi):
  if hi - lo <= base_case_size: return base(arr, lo, hi)
  mid = (lo + hi) // 2
  left = solve(arr, lo, mid)
  right = solve(arr, mid+1, hi)
  return combine(left, right)
Complexity
Master theorem: T(n) = a*T(n/b) + f(n). For merge sort a=2, b=2, f(n)=O(n) -> T(n) = O(n log n).
Examples
  • Merge Sort / Count of Smaller Numbers After Self
  • Quicksort / Quickselect
  • Maximum Subarray (D&C variant)
  • Pow(x, n) by binary exponentiation
  • Median of Two Sorted Arrays

Binary search variants

When to use
Sorted (or implicitly sorted) input, OR the answer space is monotonic ("can we do it with capacity C? smaller C -> harder, larger C -> easier" -> binary-search on C).
Template
# Classic: find target.
lo, hi = 0, n - 1
while lo <= hi:
  mid = lo + (hi - lo) // 2
  if arr[mid] == target: return mid
  if arr[mid] < target: lo = mid + 1
  else: hi = mid - 1
return -1

# Lower bound (first index >= target):
lo, hi = 0, n
while lo < hi:
  mid = (lo + hi) // 2
  if arr[mid] < target: lo = mid + 1
  else: hi = mid

# Search-on-answer:
def feasible(x): ...  # monotonic in x
lo, hi = lo_bound, hi_bound
while lo < hi:
  mid = (lo + hi) // 2
  if feasible(mid): hi = mid
  else: lo = mid + 1
return lo
Complexity
O(log n) per search; O(n log n) for n searches; O(log range * cost(feasible)) for search-on-answer.
Examples
  • Search in Rotated Sorted Array
  • Find First and Last Position
  • Capacity to Ship Packages within D Days (search-on-answer)
  • Koko Eating Bananas (search-on-answer)
  • Median of Two Sorted Arrays
  • Find Peak Element

Union-find (disjoint set)

When to use
Dynamic connectivity, grouping by equivalence relation, Kruskal MST, detecting redundant edges in an undirected graph, accounts merge, friend circles.
Template
parent = list(range(n))
rank   = [0] * n

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

def union(a, b):
  ra, rb = find(a), find(b)
  if ra == rb: return False
  if rank[ra] < rank[rb]: ra, rb = rb, ra
  parent[rb] = ra
  if rank[ra] == rank[rb]: rank[ra] += 1
  return True
Complexity
Effectively O(1) amortized per op (inverse Ackermann alpha(n)).
Examples
  • Number of Connected Components
  • Redundant Connection
  • Accounts Merge
  • Kruskal's MST
  • Most Stones Removed With Same Row or Column

Topological sort

When to use
Order tasks with prerequisites, build orderings, course schedule, package install order, expression evaluation in DAGs. Two flavors: Kahn (BFS / in-degree) and DFS post-order.
Template
# Kahn's algorithm:
indeg = [0] * n
for u, v in edges: indeg[v] += 1
q = deque([u for u in range(n) if indeg[u] == 0])
order = []
while q:
  u = q.popleft()
  order.append(u)
  for v in adj[u]:
    indeg[v] -= 1
    if indeg[v] == 0: q.append(v)
if len(order) != n: cycle detected
return order
Complexity
O(V + E) time, O(V) space.
Examples
  • Course Schedule / Course Schedule II
  • Alien Dictionary
  • Minimum Height Trees
  • Sequence Reconstruction
  • Build dependency resolver

Greedy

When to use
Local-optimal choice at each step yields global optimum. Always justify why greedy is provably correct (exchange argument). Common: interval scheduling, Huffman coding, jump game.
Template
sort by some key
result = init
for item in sorted_items:
  if compatible(result, item):
    take(item)
return result
Complexity
O(n log n) usually dominated by the sort. O(n) once sorted.
Examples
  • Jump Game / Jump Game II
  • Non-overlapping Intervals
  • Minimum Number of Arrows to Burst Balloons
  • Task Scheduler
  • Gas Station

Monotonic stack / deque

When to use
"Next greater / next smaller" queries, sliding window max/min, largest rectangle in histogram, stock span.
Template
# Next greater element (right):
stack = []  # stores indices, values strictly decreasing from bottom to top
ans = [-1] * n
for i in range(n):
  while stack and arr[stack[-1]] < arr[i]:
    j = stack.pop()
    ans[j] = i
  stack.append(i)
Complexity
O(n) time, O(n) space.
Examples
  • Next Greater Element I/II
  • Daily Temperatures
  • Largest Rectangle in Histogram
  • Sliding Window Maximum (deque)
  • Trapping Rain Water (stack variant)

Other cheat sheets

Big-O Reference

Algorithms

Time and space complexity for the data structures, sorting algorithms, and search routines that show up in coding interviews. Skim the row, remember the row, defend the row in an interview.

Design Tradeoffs

Systems

The recurring forks in system design interviews. CAP, PACELC, sync vs async, push vs pull, SQL vs NoSQL, sharding shapes, consistency models, cache strategies, idempotency, and rate limiting. For each, the options and when to choose each.

Unix Essentials

Tools

Filesystem layout, the commands you actually use (find / grep / awk / sed / xargs), processes and signals, networking, permissions, basic shell scripting, and a vi survival kit.

Practice the patterns

Reading is the floor. The signal in interviews comes from working problems out loud and defending your tradeoffs. Spin up an AI mock interview or run a coding challenge to put these to work.

Coding challengesAI mock interview