Questions to ask to find which linear pattern is needed

Below is a pattern–selection cheat sheet.


For each pattern, ask yourself these questions while reading the problem.


If you answer YES, that pattern is likely the correct approach.

1. Sliding Window (Fixed Size)

Ask these questions:

• Is the problem asking about subarrays/substrings of exact length k?


• Do I need to compute something (sum, max, count) for every window of size k?


• Does brute force give O(n·k) and I need O(n)?

Trigger words:

“window of size k”, “consecutive k elements”, “substring length k”

2 Sliding Window (Variable Size)

Ask these questions:

• Is the window size not fixed, but constrained by a condition?


• Am I trying to find the smallest / largest subarray satisfying a condition?


• Can I expand right and shrink left?

Trigger words:

“at most k”, “at least k”, “minimum window”, “longest substring”

3 Two Pointers (Same Direction)

Ask these questions:

• Do I move through the array left → right with two indices?


• Is one pointer catching up to the other?


• Am I maintaining a range inside the array?

Trigger words:

“subarray”, “range”, “continuous segment”

4 Two Pointers (Opposite Ends)

Ask these questions:

• Is the array sorted?


• Am I looking for a pair satisfying a condition?


• Can I move left++ or right-- based on comparison?

Trigger words:

“pair sum”, “target”, “sorted array”

5 Fast & Slow Pointers (Cycle Detection)

Ask these questions:

• Is there a linked list or pointer structure?


• Could there be a cycle / loop?


• Can one pointer move 2× faster than the other?

Trigger words:

“cycle”, “loop”, “circular”, “duplicate via index jump”

6 Prefix Sum

Ask these questions:

• Do I need sum of ranges repeatedly?


• Does the problem involve subarray sum equals k?


• Can a running cumulative value help?

Trigger words:

“range sum”, “subarray sum”, “sum between i and j”

7 Difference Array

Ask these questions:

• Are there multiple range updates?


• Am I asked to apply increments/decrements on intervals?


• Final values matter, intermediate don’t?

Trigger words:

“range update”, “apply operations”, “add x from l to r”

8 Hash Map Frequency Counting

Ask these questions:

• Am I counting frequency of elements/characters?


• Do I need constant-time lookup?


• Is order less important than counts?

Trigger words:

“frequency”, “count occurrences”, “anagram”

9 In-place Modification

Ask these questions:

• Am I told not to use extra space?


• Can the array be modified?


• Is the output expected inside the same array?

Trigger words:

“in-place”, “O(1) space”, “modify input”

10 Sorting-based Pattern

Ask these questions:

• Does sorting simplify the logic drastically?


• Am I matching pairs or intervals?


• Can order change without affecting correctness?

Trigger words:

“after sorting”, “arrange”, “reorder”

11 Cyclic Sort

Ask these questions:

• Are numbers in the range 1…n?


• Is each number supposed to be at a specific index?


• Am I finding missing / duplicate elements?

Trigger words:

“missing number”, “duplicate”, “1 to n”

12 Kadane’s Algorithm (Max Subarray)

Ask these questions:

• Am I asked for maximum sum subarray?


• Is negative sum harmful?


• Can I reset when sum < 0?

Trigger words:

“maximum subarray”, “largest sum contiguous”

13 Merge Intervals

Ask these questions:

• Are there intervals [start, end]?


• Do overlapping intervals need merging?


• Is output also intervals?

Trigger words:

“overlapping”, “merge”, “intervals”

14 Interval Sweep Line

Ask these questions:

• Do events start and end?


• Am I counting overlaps at a time?


• Do I need max/min concurrent events?

Trigger words:

“meetings”, “events”, “timeline”, “rooms needed”

15 Subarray / Subsequence Enumeration

Ask these questions:

• Do I need to consider all subarrays or subsequences?


• Is brute force acceptable or optimized via DP/hash?

Trigger words:

“all possible”, “count of subarrays”, “number of subsequences”

16 Monotonic Stack

Ask these questions:

• Am I looking for next greater/smaller element?


• Is direction important (left/right)?


• Can I maintain increasing/decreasing order?

Trigger words:

“next greater”, “previous smaller”, “span”

17 Monotonic Queue

Ask these questions:

• Is there a sliding window max/min?


• Do I need O(1) retrieval of max/min?


• Window size fixed or variable?

Trigger words:

“maximum in window”, “minimum in range”

18 Counting / Bucket Sort

Ask these questions:

• Is the value range small?


• Do I only care about frequency?


• Can sorting be done without comparison?

Trigger words:

“range is small”, “frequency array”

19 Boyer–Moore Voting

Ask these questions:

• Is there an element appearing > n/2 times?


• Can I assume a majority exists?


• Do I need O(1) space?

Trigger words:

“majority element”, “more than half”

20 Reservoir Sampling

Ask these questions:

• Is the data streaming / infinite?


• Do I not know n beforehand?


• Do I need uniform random selection?

Trigger words:

“stream”, “random sample”, “unknown size”