World's Best Array Patterns Cheat Sheet for DSA Interviews

This cheat sheet is the ultimate resource for mastering array patterns in Data Structures and
Algorithms (DSA) interviews. It’s designed to help beginners instantly recognize patterns and
develop a thought process to apply them confidently, while also providing depth for
experienced programmers. By mastering this cheat sheet, you’ll tackle any array problem
with clarity and precision, reaching the limit of your problem-solving thought process.

Why Array Patterns?

• Arrays appear in over 60% of coding interview problems at top companies like
Google, Amazon, and Microsoft.

• Patterns provide reusable templates, saving time and boosting confidence in high-
pressure interviews.

• This cheat sheet combines pattern recognition, practical examples, thought process
development, and advanced techniques for comprehensive preparation.

Pattern Overview: 16 Essential Array Patterns + Advanced Techniques

Key
Trigger (Look Edge Time/Sp
Pattern What It Does Problem How to Think
for These) Cases ace
s

1. Check if array
is sorted.
"Find pair
Two 2. Set pointers
with sum," Empty
Uses two pointers Sum, (left=0, right=n-1 O(n)
"remove array,
Two- to find pairs, sums, 3Sum, or both at 0). time,
duplicates," duplicate
Pointer or rearrange Remove 3. Move based O(1)/O(
"sorted s, no
elements. Duplicate on condition n) space
array," solution
s (e.g., sum >
"reverse."
target, move
right).

1. Identify
"Longest/sho Max window
Tracks a moving rtest Subarray, condition (e.g., Empty O(n)
Sliding window for subarray," Longest no repeats). input, time,
Window subarrays/substrin "max/min Substring 2. Expand/shrink invalid O(1)/O(
gs. sum," "no No window with window n) space
repeats." Repeat start/end
pointers.
 Key
Trigger (Look Edge Time/Sp
Pattern What It Does Problem How to Think
for These) Cases ace
s

3. Track max/min
or length.

1. Build
"Subarray prefix/suffix sum
Subarray
sum equals or product array. Negative O(n)
Uses cumulative Sum = K,
Prefix/Suf K," "range 2. Use sum[i:j] = s, zeroes, time,
sums/products for Product
fix Sum sum," prefix[j] - prefix[i- empty O(n)
range queries. Except
"product 1]. array space
Self
except self." 3. Handle
negatives/zeroes.

1. Confirm array
Search is sorted/rotated.
"Sorted
Rotated 2. Set left/right O(log n)
Searches sorted array," "find Duplicate
Binary Array, pointers, time,
arrays in position," s, empty
Search Find compute mid. O(1)
logarithmic time. "rotated array
First/Last 3. Adjust for space
array."
Position duplicates/rotati
ons.

1. Sort by
start/end or key
Non-
"Intervals," value. Overlapp
overlappi O(n log
Sorts array, then "overlap," 2. Make greedy ing
Sorting & ng n) time,
makes optimal "scheduling, choice (e.g., intervals,
Greedy Intervals, O(1)/O(
choices. " "min/max earliest end empty
Meeting n) space
choices." time). input
Rooms II
3. Track count or
result.

1. Set slow (1
Uses two pointers Find step) and fast (2 No cycle, O(n)
"Cycle,"
Fast-Slow at different speeds Duplicate steps). time,
"duplicate," single
Pointers for , Detect 2. Find O(1)
"middle." element
cycles/midpoints. Cycle intersection, space
then entry point.
 Key
Trigger (Look Edge Time/Sp
Pattern What It Does Problem How to Think
for These) Cases ace
s

3. Treat array like

1. Swap elements
First to correct index
"Missing Out-of-
Missing (i-1). O(n)
Places numbers in number," range
Cyclic Positive, 2. Ignore out-of- time,
correct index for "duplicates," values,
Sort Find All range values. O(1)
[1,n]. "[1,n] duplicate
Duplicate 3. Scan for space
range." s
s missing/duplicat
es.

1. Track
"Max current/global
Maximu
Finds max subarray max sum. All O(n)
m
Kadane’s subarray sum sum," 2. Reset current negatives time,
Subarray,
Algorithm using dynamic "contiguous sum if negative. , single O(1)
Circular
programming. sum," 3. For circular, element space
Subarray
"circular." use min subarray
trick.

1. Set boundaries
(top/bottom/left
/right). Single O(mn)
Traverses 2D "Matrix," Spiral
2. Traverse, row/colu time,
Matrix arrays in patterns "spiral," Matrix,
update mn, O(1)/O(
Traversal (row, spiral, "rotate," Rotate
boundaries. empty mn)
diagonal). "search 2D." Matrix
3. Handle matrix space
square/non-
square matrices.

1. Use pointers
"Move Move to separate All O(n)
Rearranges array
Partitioni elements," Zeroes, groups. zeroes, time,
around a
ng "partition," Sort 2. Swap elements single O(1)
pivot/condition.
"rearrange." Colors to maintain element space
order.
 Key
Trigger (Look Edge Time/Sp
Pattern What It Does Problem How to Think
for These) Cases ace
s

3. Track partition
boundary.

1. Use XOR to
cancel
"Single Single O(n)
Bit Uses bitwise duplicates. Zeroes,
number," Number, time,
Manipula operations for 2. Iterate once, duplicate
"XOR," "no Missing O(1)
tion efficiency. update result. s
extra space." Number space
3. Handle edge
cases like zeroes.

1. Push/pop to
"Next Next
maintain order.
greater/lesse Greater Empty O(n)
Maintains stack in 2. Track
Monotoni r," Element, stack, time,
increasing/decrea indices/values.
c Stack "histogram," Trapping single O(n)
sing order. 3. Return results
"temperatur Rain element space
for each
es." Water
element.

1. Use three
pointers (low,
Sort
mid, high). Single O(n)
Dutch Partitions array "Sort colors," Colors,
2. Swap to group element, time,
National into three groups "three Three
0s, 1s, 2s. all same O(1)
Flag (e.g., 0s, 1s, 2s). partitions." Partition
3. Ensure mid value space
s
doesn’t skip
elements.

1. Sort by start
time. O(n log
"Intervals," Merge 2. Merge if Empty n) time,
Combines
Merge "merge," Intervals, current start ≤ intervals, O(n)
overlapping
Intervals "overlapping Insert last end. no space
intervals.
." Interval 3. Append non- overlap Ascendi
overlapping ng
intervals.
 Key
Trigger (Look Edge Time/Sp
Pattern What It Does Problem How to Think
for These) Cases ace
s

1. Use
backtracking or
"Subsets," iterative Empty
Generates all O(2^n)
"combinatio Subsets, approach. array,
possible time,
Subsets ns," Combina 2. Build subsets sum
subsets/combinati O(2^n)
"permutatio tion Sum incrementally. constrain
ons. space
ns." 3. Handle ts
constraints like
sum.

1. Use heap or
"Top K," Top K quickselect.
O(n log
Finds top K "frequent," Frequent 2. Track K > n,
Top K k) time,
largest/smallest/fr "kth , Kth frequencies or empty
Elements O(k)
equent elements. largest/small Largest order. array
space
est." Element 3. Return top K
results.

1. Use min-heap
Merge K to track smallest
O(n log
"Merge K Sorted elements. Empty
K-way Merges K sorted k) time,
arrays," "K Lists, 2. Pop and push lists,
Merge arrays into one. O(k)
sorted lists." Smallest next elements. single list
space
Range 3. Handle empty
lists.

Additional Techniques for Advanced Problems

These techniques enhance the main patterns for specific scenarios:

• Traversing from the Right: Start from the array’s end for problems like Daily
Temperatures or Number of Visible People. How to Think: Reverse the traversal
direction; useful for finding next elements or backward dependencies.

• Index as Hash Key: Use array indices as a hash table for O(1) space. Example: First
Missing Positive marks presence by negating values at indices. How to Think: Map
values to indices, modify array in-place, restore later.
 • Precomputation with Suffix Sum/Product: Extend prefix sum to include suffix
sums/products for queries like Product Except Self. How to Think: Compute suffix
sums/products in a second pass or use two arrays.

Decision Tree for Pattern Selection

Follow this step-by-step guide to identify the correct pattern in seconds:

1. What’s the problem asking?

o Pairs or sums (e.g., "find two numbers summing to target")? → Two-Pointer

o Subarrays/substrings (e.g., "longest substring without repeats")? → Sliding

o Cumulative or range sums (e.g., "subarray sum equals K")? → Prefix/Suffix

o Max/min subarray sum (e.g., "maximum sum of contiguous elements")? →

o Sorted array or searching (e.g., "find element in rotated array")? → Binary

2. Any specific structure?

o Intervals or scheduling (e.g., "merge overlapping intervals")? → Merge

o Matrix or 2D array (e.g., "rotate matrix 90 degrees")? → Matrix Traversal

o Cycles or duplicates (e.g., "find duplicate in [1,n]")? → Fast-Slow Pointers or

3. Special conditions?

o Three groups (e.g., "sort 0s, 1s, 2s")? → Dutch National Flag

o Bit operations (e.g., "find number appearing once")? → Bit Manipulation

o Next greater/lesser (e.g., "next greater element for each")? → Monotonic

o Rearranging (e.g., "move all zeroes to end")? → Partitioning

4. Complex requirements?

o All subsets/combinations (e.g., "all possible subsets")? → Subsets

o Top K or frequent elements (e.g., "top K frequent numbers")? → Top K

Thought Process Guide for Beginners

To develop a robust thought process for solving array problems:

1. Read Carefully: Highlight keywords (e.g., "sum," "sorted," "subarray").

2. Match to Trigger: Use the table’s "Trigger" column to identify the pattern.

3. Ask Clarifying Questions: Is the array sorted? Are there duplicates? Negatives?
Constraints?

4. Start Simple: Write a brute force solution, then optimize using the pattern’s "How to
Think."

5. Check Edge Cases: Test for empty arrays, single elements, duplicates, negatives, or
out-of-range values.

6. Explain Clearly: Articulate your pattern choice and reasoning to the interviewer (e.g.,
“I’ll use Two-Pointer because we need a pair summing to the target”).

Common Pitfalls and How to Avoid Them

• Two-Pointer: Forgetting to check if the array is sorted or handling duplicates

• Sliding Window: Misdefining the window condition or not shrinking the window
properly.

• Prefix/Suffix Sum: Not accounting for zeroes or negative numbers in sums/products.

• Binary Search: Mishandling rotations or duplicate elements.

• Kadane’s: Forgetting to handle all-negative cases or circular subarrays.

Must-Practice Problems

Pattern Problems

Two-Pointer Two Sum, 3Sum, Container With Most Water

Sliding Window Longest Substring No Repeat, Min Window Substring

Prefix/Suffix Sum Subarray Sum = K, Product Except Self

Binary Search Search Rotated Array, Find First/Last Position

Sorting & Greedy Non-overlapping Intervals, Meeting Rooms II

Fast-Slow Pointers Find Duplicate, Detect Cycle

Cyclic Sort First Missing Positive, Find All Duplicates

Kadane’s Algorithm Maximum Subarray, Circular Subarray

Matrix Traversal Spiral Matrix, Rotate Matrix

Partitioning Move Zeroes, Sort Colors

Bit Manipulation Single Number, Missing Number

Monotonic Stack Next Greater Element, Trapping Rain Water

Dutch National Flag Sort Colors, Three Partitions

Merge Intervals Merge Intervals, Insert Interval

Subsets Subsets, Combination Sum

Top K Elements Top K Frequent, Kth Largest Element

K-way Merge Merge K Sorted Lists, Smallest Range

Real-World Applications

• Two-Pointer: Used in search algorithms or merging sorted data in databases.

• Sliding Window: Common in stream processing or real-time data analysis.

• Kadane’s: Applied in financial modeling for maximum profit calculations.

• Binary Search: Powers efficient search in sorted datasets, like indexes in databases.

Interview Tips

• Practice Strategically: Solve 3-5 problems per pattern on LeetCode or

• Time Management: Spend 5 min planning, 20 min coding, 5 min testing.

• Communicate Clearly: Explain your pattern choice and thought process aloud.

• Handle Follow-Ups: Be ready to optimize or adapt your solution for new constraints.

• Resources: Use NeetCode, AlgoMonster, DesignGurus, and Cracking the Coding

Quick Reference Guide

• Two-Pointer: Pairs/sums in sorted arrays.

• Prefix/Suffix Sum: Range sum/product queries.

• Binary Search: Fast search in sorted arrays.

• Sorting & Greedy: Optimal choices after sorting.

• Fast-Slow Pointers: Cycles or midpoints.

• Cyclic Sort: Missing/duplicates in [1,n].

• Kadane’s: Max subarray sum.

• Matrix Traversal: 2D array patterns.

• Partitioning: Rearrange around conditions.

• Bit Manipulation: XOR for unique elements.

• Monotonic Stack: Next greater/lesser elements.

• Dutch National Flag: Three-group partitioning.

• Merge Intervals: Combine overlapping intervals.

• Subsets: Generate all combinations.

• Top K Elements: Find top K elements.

• K-way Merge: Merge K sorted arrays.

Why This Cheat Sheet is the Best

• Clarity: Simple explanations for beginners.

• Completeness: Covers 16 patterns + advanced techniques.

• Practicality: Includes must-solve problems and real-world applications.

• Depth: Explains why patterns work and how to adapt them.

• Efficiency: Quick reference table and decision tree for instant recall.

• Thought Process: Guides beginners to think like experts.

Last Updated: June 9, 2025 | Powered by Grok 3, xAI