General Patterns

External article

Prefix Sum

Involves preprocessing an array to create a new array where each element at index i represents the sum of the array from the start up to i

Use cases

Perform multiple sum queries on a subarray
Calculate cumulative sums

Two Pointers

Recognition Signals

Array/string with sorted or sortable data
Finding pairs/triplets with specific sum
Partitioning elements (zeros vs non-zeros)
Comparing from both ends simultaneously
Subsequence or palindrome checking

Main Patterns

Opposite Direction (converging)

Start at both ends, move toward center
Uses: palindrome check, container problems, sorted pair finding
Move pointer based on comparison logic (smaller/larger values)

Same Direction (slow-fast)

Both start at beginning, move at different speeds
Uses: in-place array modification, subsequence matching, removing duplicates
Fast finds elements, slow tracks position for placement

Fixed Distance

Maintain constant gap between pointers
Uses: sliding window variants, k-distance problems

Anchor + Runner

One pointer fixed, other explores from that point
Uses: 3Sum (anchor one, two-pointer on rest), subarrays with constraints

State Tracking

Always track: current sum/product, valid range boundaries
For duplicates: use sets or skip consecutive same values
For triplets/k-sum: fix outer pointer(s), two-pointer on remainder
Result format: check if 0-indexed or 1-indexed required

Implementation Checklist

Sort if needed (O(n log n) often acceptable)
Define pointer positions and movement rules
Handle boundary conditions in loop (< vs <=, check indices)
Skip duplicates AFTER finding valid result
Update result before/after pointer movement (order matters)

Gotchas

Off-by-one: while L < R vs L <= R (equal case validity)
Skip duplicates: do AFTER processing, not before (may skip valid answers)
Index bounds: check L+1, R-1 exist before accessing
Early termination: break when first element > target (sorted ascending)
In-place swap: use temp or simultaneous assignment to avoid overwrite
Return format: some problems want indices+1 (1-indexed)

Sliding window

Contiguous elements: subarray, substring, consecutive, “at most K”, anagram, permutation

Five main patterns

1. Fixed window (size k)

Build window of k elements
Slide by +1 right, -1 left
Start processing when R >= k - 1

2. Maximum length window

Expand right always
Shrink left only when invalid
Update result after window is valid: max_len = max(max_len, R - L + 1)

3. Minimum length window

Expand right until valid
While valid: update min_len, then shrink left
Update result during shrinking

4. Optimize a value (profit, swaps, sum)

Track best value seen so far
Greedy reset: jump L to R when better starting point found
Or reset when continuing hurts (negative sum)

5. Pattern matching (anagram/permutation)

Fixed window size = pattern length
Count matches instead of comparing whole maps (O(1) vs O(26))
Update when match counter equals pattern length

Tracking techniques

Frequencies: hash map (delete key when freq = 0)
Pattern match: match counter for O(1) comparison
Min/max in window: monotonic deque with indices
Valid replacements: window_length - max_freq <= k
Circular arrays: iterate 2×N with modulo indexing

Hash map operation order

Adding to window: increment freq → then check if equals target
Removing from window: check if equals target → then decrement freq
Match counter: increment after adding, decrement before removing

Gotchas

Window length: use R - L + 1, not R - L
Fixed window: start at R >= k - 1, not R >= k
Max problems: update after valid; Min problems: update while valid

Fast and slow pointers

Use cases

Detecting cycles in a linked list
Detecting middle node in a linked list
Odd-length list: The slow pointer will point to the exact middle node.
Even-length list: The slow pointer will point to the first node of the second half (or equivalently, the node right before the middle).

Code

 
let fn = (head) => {
  let slow = head;
  let fast = head;
  let ans = 0;
 
  while (fast && fast.next) {
    // do logic
    slow = slow.next;
    fast = fast.next.next;
  }
 
  return ans;
};

Linked list in-place reversal

Does not use extra space

Use cases

Reversing sections of a linked list

Code

 
let fn = (head) => {
  let curr = head;
  let prev = null;
  while (curr) {
    let nextNode = curr.next;
    curr.next = prev;
    prev = curr;
    curr = nextNode;
  }
 
  return prev;
};

Monotonic stack

Maintain a sequence of elements in a specifc order

Use cases

Finding next greater or smaller element

Top K elements / Kth Largest / Kth Smallest

Finding top k largest or smallest elements in an array
Use heaps (priority queues) or sorting
import heapq

Use cases

Find k-th largest element in an unsorted array

Overlapping intervals

Create an empty list first

Use cases

Merging overlapping intervals

Binary search

Search technique that divides the search space in half at each step
Starts by checking if the middle element is the target
If not, it eliminates half of the search space

Use cases

Searching for an element in a sorted array
Any list where there is a monotonic property

Modified binary search

Use cases

Problems involving sorted or rotated arrays where you need to find a specific element

Tree traversal

Think of trees and graphs as the same thing, except trees don’t have cycles
For graphs, you need to keep track of visited nodes

Binary tree traversal

Preorder: root -> left -> right
Inorder: left -> root -> right
Postorder: left -> right -> root

Depth first search

Traversal technique that travels as far down a branch as possible before backtracking
Use recursion

Use cases

Find all paths from the root to leaves in a binary tree
Find a specific condition deep in the structure

Breadth first search

Traversal technique that explores nodes level by level
Use a queue
Ensures noodes are visited from the closest to the farthest

Use cases

Finding shortest paths in unweighted graphs
Level order traversal in trees

Matrix traversal

Traversing matrices using different techniques (DFS, BFS, etc.)

Use cases

Traversing 2D grids or matrices horizontally, vertically, or diagonally

Backtracking

Traversal technique that explores all possible solutions and backtracks when a solution path fails

Use cases

Find all (or some) solution to a problem that satisfies given constraints
Combinatorial problems: generating permutations, combinations, subsets

Dynamic programming

Technique that involves breaking down a problem into smaller subproblems and storing the results of those subproblems to avoid redundant computations

Dynamic Programming Patterns Leetcode Patterns