Array Patterns Cheat Sheet (Structured Table)

Pattern What It Does Trigger Key Problems How to Think Edge Cases Time/Space

Two-Pointer Uses two pointers to find pairs Find pair with sum, remove Two Sum, 3Sum, Remove Check if array is sorted. Use two pointers. Move Empty array, O(n), O(1)/O(n)
or rearrange elements duplicates, sorted array Duplicates based on condition. duplicates, no solution
Sliding Window Tracks a moving window for Longest/shortest subarray, Max Subarray, Longest Expand/shrink window using start/end pointers based Empty input, invalid O(n), O(1)/O(n)
subarrays/substrings. max/min sum, no repeats Substring No Repeat on window condition. window
Prefix/Suffix Sum Uses cumulative Subarray sum equals K, Subarray Sum = K, Product Build prefix/suffix array. Use prefix[j] - prefix[i-1] for Negatives, zeroes, O(n), O(n)
sums/products for range range sum, product except Except Self range. Handle zeroes/negatives. empty array
queries. self
Binary Search Searches sorted arrays in Sorted array, find position, Search Rotated Array, Find Confirm sorted. Use left/right pointers. Adjust for Duplicates, empty array O(log n), O(1)
logarithmic time. rotated array First/Last Position rotation/duplicates.
Sorting & Greedy Sorts array, then makes Intervals, overlap, Non-overlapping Intervals, Sort by key. Make greedy choice. Track result. Overlapping intervals, O(n log n), O(1)/O(n)
optimal choices. scheduling, min/max Meeting Rooms II empty input
choices
Fast-Slow Pointers Two pointers at different Cycle, duplicate, middle Find Duplicate, Detect Cycle Use fast=2x speed. Find intersection, then entry point. No cycle, single O(n), O(1)
speeds for cycles/midpoints. element
Cyclic Sort Places numbers in correct Missing number, duplicates, First Missing Positive, Find Swap elements to correct position. Ignore Out-of-range values, O(n), O(1)
index for [1,n]. [1,n] range All Duplicates out-of-range. duplicates
Kadane's Algorithm Finds max subarray sum Max subarray sum, Maximum Subarray, Circular Track current/global max. Reset if current sum < 0. All negatives, single O(n), O(1)
using dynamic programming. contiguous sum, circular Subarray Use trick for circular. element
Matrix Traversal Traverses 2D arrays in rows, Matrix, spiral, rotate, search Spiral Matrix, Rotate Matrix Use boundary markers (top/bottom/left/right). Single row/column, O(mn), O(1)/O(mn)
spirals, diagonals. 2D empty matrix
Partitioning Rearranges array around Move elements, partition, Move Zeroes, Sort Colors Use pointers to separate groups. Swap to maintain All zeroes, single O(n), O(1)
pivot/condition. rearrange order. element
Bit Manipulation Uses bitwise ops for Single number, XOR, no Single Number, Missing Use XOR to cancel duplicates. Iterate and update. Zeroes, duplicates O(n), O(1)
space-efficient logic. extra space Number
Monotonic Stack Maintains Next greater/lesser, Next Greater Element, Push/pop to maintain stack order. Track Empty stack, single O(n), O(n)
increasing/decreasing stack. histogram, temperatures Trapping Rain Water indices/values. element
Dutch National Flag Partitions into three groups Sort colors, three partitions Sort Colors, Three Partitions Use low/mid/high pointers to swap elements into Single element, all O(n), O(1)
(0s, 1s, 2s). groups. same
Merge Intervals Combines overlapping Intervals, merge, Merge Intervals, Insert Sort by start. Merge if overlap. Empty intervals, no O(n log n), O(n)
intervals. overlapping Interval overlap
Subsets Generates all combinations or Subsets, combinations, Subsets, Combination Sum Use backtracking or iterative logic. Build Empty array, sum O(2^n), O(2^n)
subsets. permutations incrementally. constraints
Top K Elements Finds top K frequent/largest Top K, frequent, kth Top K Frequent, Kth Largest Use heap or quickselect. Track frequency/order. K > n, empty array O(n log k), O(k)
elements. largest/smallest Element
K-way Merge Merges K sorted arrays into Merge K arrays, K sorted Merge K Sorted Lists, Use min-heap to manage smallest elements. Empty lists, single list O(n log k), O(k)
one. lists Smallest Range

Page 1