Expert: advanced patterns and interviews · Interview strategy and mock problems · topic 57 of 61 · 35 min
Recognising the pattern
Explanation
Why patterns matter
There are thousands of practice problems but only a few dozen ideas behind them. An interviewer changes the story (orders, trains, friends, files) but the structure underneath is usually one you know: a hash map, two pointers, a heap, a BFS, a DP table. Strong candidates do not remember every problem; they recognise which pattern a new problem is wearing.
A pattern is a reusable approach together with the signal that suggests it. Learning the signals turns "I have never seen this" into "this looks like a sliding window, let me check".
A cheat-sheet: signals to techniques
| Signal in the question | Try first | Module |
|---|---|---|
| Sorted array, pair or triple with a target | Two pointers, or binary search | 3, 6 |
| "Subarray" or "substring" with a condition (longest, at most k) | Sliding window | 3 |
| Subarray sums, many range-sum queries | Prefix sums (+ hash map for "sum equals k") | 2, 3 |
| "Have I seen this before?", counting, pairs | Hash map or set | 3 |
| "Top k", "k-th largest", merge k sorted lists, running median | Heap | 8 |
| "All combinations / subsets / permutations", n is small | Backtracking | 5 |
| "Shortest path" with equal steps, "minimum moves", levels | BFS | 9 |
| Shortest path with weights | Dijkstra | 9 |
| Dependencies, prerequisites, build order | Topological sort | 9 |
| "Number of ways", "minimum cost", "can we reach", choices | Dynamic programming | 11 |
| Groups, connected or not, merging sets | Union-find (or DFS) | 9, 10 |
| Prefix lookups, autocomplete, many words | Trie | 10 |
| "Next greater / smaller element", spans | Monotonic stack | 4 |
| Minimum value that works, "at least / at most" with a check | Binary search on the answer | 6 |
| Intervals, meetings, schedules | Sort by start (or end), then sweep; heap for rooms | 6, 8 |
Input size tells you the target complexity
Constraints are a hint the interviewer gives for free. A rough rule of thumb: a judge or test machine does somewhere around 10⁷ to 10⁸ simple steps per second in a fast language, and Python is often 10 to 50 times slower. So work out how many steps your idea needs at the largest n and compare.
| Largest n | What usually fits | Typical ideas |
|---|---|---|
| n ≤ 10–12 | O(n!) | Permutations, brute force |
| n ≤ 20 | O(2ⁿ) or O(2ⁿ × n) | Subsets, backtracking, bitmask DP |
| n ≤ 500 | O(n³) | Interval DP, three nested loops |
| n ≤ 5,000 | O(n²) | 2-D DP, pairs of items |
| n ≤ 10⁵ | O(n log n) | Sorting, heaps, binary search |
| n around 10⁶ or more | O(n), sometimes O(n log n) | One pass, hash map, two pointers |
| n up to 10¹⁸ (a value, not a list) | O(log n) | Binary search on the answer, maths |
Example: with n = 10⁵, an O(n²) idea needs about 10¹⁰ steps, far too many, while O(n log n) needs under 2 × 10⁶. That one calculation tells you to look for sorting, a heap or a hash map before you write any code.
A three-question routine
- What is the input (array, string, grid, graph, intervals) and is anything special about it (sorted, small values, no negatives)?
- What is asked (one number, a yes/no, a list, all combinations, a count)?
- What is n, and therefore which Big-O do I need?
Then match the answers against the cheat-sheet and say your guess aloud: "Since it is sorted and I need a pair, I will try two pointers; that is O(n) time and O(1) space." The interviewer can nudge you early if the guess is off.
Common mistakes
- Ignoring the constraints. Fix: read them before planning; they often rule out your first idea.
- Forcing a favourite pattern (everything becomes DP). Fix: check the signal AND whether the pattern's conditions hold, for example a sliding window needs a condition that only gets worse as the window grows.
- Using a sliding window when numbers can be negative and the question is "sum equals k". Fix: prefix sums with a hash map.
- Memorising problem names instead of the reason behind each pattern. Fix: after every problem, write one line: "Signal → technique, because …".
Need help?
Stuck on a word or an idea? Search this course, or every course, and jump straight to the explanation or a worked question.
Try:
Watch the lesson
Recognising the pattern · 1/8
This lesson teaches you to recognise which pattern a new interview problem is wearing.
Prefer a video by a teacher? Find free videos on “how to identify coding interview patterns leetcode patterns constraints time complexity” on YouTube ↗
In real life: An online assessment in a campus drive
In many campus placement drives, the first round is an online coding test on a platform such as HackerRank or a company's own portal, with two or three problems in about 60 to 90 minutes. Each problem lists its constraints. Candidates who check n first and say "10⁵, so I need O(n log n)" avoid the classic trap of a brute force that passes the sample tests but times out on the hidden ones. The exact format varies by company and year, so read the instructions on the test page.
import math
n = 10 ** 5
print(n * n) # steps for an O(n^2) idea
print(round(n * math.log2(n))) # steps for an O(n log n) ideaPractice (0/4 done)
A sorted array of distinct integers and a target. Return the indexes of two numbers that add up to the target, using O(1) extra space. Which technique fits best?
n ≤ 18 items. Return every group of items whose prices add up to exactly 1,000. Which approach is reasonable?
A university lists courses and their prerequisites ("take A before B"). Find any order in which a student can take all courses, or report that it is impossible. Which technique fits?
Pick the pattern yourself. Write days_until_warmer(temps): for each day i, return how many days you must wait after day i for a STRICTLY warmer temperature, or 0 if no later day is warmer. Return a list of the same length. It must be O(n) time, so a double loop is not enough. Example: days_until_warmer([73, 74, 75, 71, 69, 72, 76, 73]) returns [1, 1, 4, 2, 1, 1, 0, 0].
Quick quiz
Read more (free)
Related help
Before this, learn
This topic builds on these. If something here feels new, open them first.
Related topics
- Running the coding interviewInterview strategy and mock problems · same module
- Testing, edge cases and debugging under pressureInterview strategy and mock problems · same module
- Mock problems: design-style data structuresInterview strategy and mock problems · same module
- Data-structure questions in JavaScriptJavaScript Programming (language in depth) · Interview preparation and career
- What DSA is, and how to learn itThinking in Big-O
- Subnetting drills for exam speedComputer Networking (CCNA level) · Subnetting practice and IPv6
Questions people ask about this
Open a question to see the answer and why. The first ones are this topic's own quiz, so try the quiz above before you peek.
"Find the length of the longest substring with at most k distinct characters." Which pattern?
Answer: Sliding window with a count map
A substring (continuous) with a condition that gets worse as it grows: grow the right end, shrink the left end.
n ≤ 10⁵. Which time complexity is usually safe?
Answer: O(n log n)
n log n is under 2 × 10⁶ steps; n² is 10¹⁰.
"Return the k most frequent words in a large log." Which structure is the natural fit?
Answer: A hash map for counts plus a heap of size k
Count with a dictionary, then keep the top k with a heap: O(n log k).
"Minimum number of moves for a knight to reach a square on a chessboard." Which technique?
Answer: BFS
Every move costs the same, so BFS finds the fewest moves level by level.
Why is a sliding window wrong for "count subarrays with sum exactly k" when numbers can be negative?
Answer: Adding a number may make the sum go down, so you cannot decide when to shrink
With negatives the sum is not monotonic as the window grows; prefix sums with a hash map handle it.
Why must the numbers be positive for the shortest-subarray-with-sum-at-least-target window?Related
Answer: So removing an item from the left always lowers the sum, which makes "shrink while valid" correct
With negatives, removing an item can raise the sum, so the window can stop shrinking too early or miss the answer.
Which pattern fits "find two numbers that add up to a target" in unsorted data?Related
Answer: Hash map
Store what you have seen and look up the complement.
In the subarray-sum pattern, why look up running − k BEFORE storing running?Related
Answer: So a prefix is never matched with itself, which would count an empty subarray when k = 0
If running were stored first, running − 0 would find the prefix just stored.
Which question wording is the weakest signal for DP?Related
Answer: "Print all the items in reverse order"
Reversing is a single pass; the other three ask for a count, an optimum or a yes/no built from choices.
Pass the quiz (60% or more) or mark this topic as done when you are ready.
Your progress is saved on this device only.
Next steps
- 4 more topics in “Interview strategy and mock problems” before its exam: Running the coding interview, Testing, edge cases and debugging under pressure, Mock problems: design-style data structures, Your study plan and the job hunt.
- Module 12 exam: Interview strategy and mock problems · 14 questions · 25 min, without help. 5 topics of this module still to finish first.
- 61 topics left in the course before the final exam.