A problem gives n up to 200,000 and asks for the longest subarray with sum at most k. What do you do first?

Read the constraint: 200,000 squared is 4 × 10¹⁰ operations, far too many, so I need O(n log n) or O(n). A contiguous subarray with a sum condition suggests a sliding window if all numbers are non-negative, or prefix sums with a sorted structure if negatives are allowed. State the brute force (check all subarrays, O(n²)), then the window solution in O(n) time and O(1) space.

You see "find the k-th largest element in an unsorted array" with n up to 10⁶. Walk through your thinking.

Brute force: sort and index, O(n log n), which fits at n = 10⁶. A heap of size k gives O(n log k) with O(k) space and works on streams. Quickselect gives O(n) expected with O(1) extra space but modifies the array. Which to choose depends on whether the data is a stream, whether I may modify it, and how large k is.

Your solution is correct but times out. How do you find the bottleneck and improve it?

Count the operations for the largest input and compare with about 10⁸. Find the nested loops or repeated work. Typical fixes are caching with a hash map (remove repeated lookups), sorting then using two pointers (remove the inner loop), prefix sums (remove repeated range sums), or a better structure such as a heap or balanced tree. Re-check the new time and space.

The constraint says n is at most 18. What does that tell you?

An exponential solution is allowed: 2^18 is about 262,000, while 18! is about 6 × 10¹⁵ and is far too large, but subsets and bitmasks are fine. This usually means backtracking or a bitmask dynamic programme, for example trying every subset, or O(2^n × n²) (Held-Karp) for a travelling salesperson style problem: 18² × 2^18 is about 8.5 × 10⁷, which fits the budget. The small limit is a hint that the intended solution is exponential.

Choosing a Pattern from the Constraints

beginner · 25 min · Asked often · Last reviewed 31 Oct 2026 · by TheLearningLoop Team

Key takeaways

A machine does about 10⁸ simple operations a second. The largest n in the problem tells you which complexity class fits: n of 10⁵ allows O(n log n), but not O(n²).
Clues in the wording point to patterns: sorted input suggests binary search or two pointers, a subarray suggests a sliding window, and range queries suggest prefix sums or a tree.
Always state the brute force and its cost first, then say what repeated or wasted work the better pattern removes.

New to this topic? Read the overview first: Data Structures & Algorithms: The Big Picture

When to use a problem-solving framework

Use the framework when:

You face a new problem and do not know where to start, in an interview or at work.
The statement gives constraints (the size of n) and you must pick an algorithm that is fast enough.
You can name several approaches and need to choose between them with a reason.

Use something else when:

The problem is one you have solved before: reuse the pattern directly.
The input is tiny and any correct solution will do: write the simplest one first.
You are stuck for a long time: step away from the framework, work a small example by hand, and look for a pattern in the answers.

There is no library for thinking, but there is a routine. The steps below are a checklist to run through out loud in an interview.

Think of a builder who is asked to build a shed or a skyscraper. The size of the job decides the tools before the first brick is laid. Constraints do the same for code: the size of n rules some algorithms out before you write a line.

How the framework works

Most problems can be solved by reading two things in the statement: how big the input can be, and what the input looks like. The first tells you how fast your solution must be. The second suggests which technique to try.

Budget rule: a typical machine does about 10⁸ simple operations in a second. Pick an algorithm whose operation count for the largest n stays under that.

Where does 10⁸ come from? A modern processor runs a few billion clock cycles each second, and a simple operation such as an addition or a comparison takes a few cycles. That gives somewhere around 10⁸ to 10⁹ simple operations. This is an approximate estimate, so we use the cautious end, 10⁸. It is a soft budget, not a hard law.

The budget is a guide, not a promise. It assumes a compiled language such as C++, Java, Go or Rust and simple operations. In an interpreted language such as Python, a safer budget is nearer 10⁷. Heavy operations (hash lookups, memory allocation, string building) cost more than one unit each. Always read the real time limit in the statement.

The routine is:

Restate the problem in your own words, with a small example.
Read the constraints. Find the largest n, then work out which time complexity fits.
Look for clues in the statement ("sorted", "subarray", "range query", "shortest", "all combinations").
Pick a pattern from the clues, and write down its time and space.
Say the brute force first, with its cost, then improve it. This shows the reasoning.
Test on a small example and on edge cases (empty input, one element, all equal, maximum size).
State the final complexity in terms of the right variables.

Try it

Choose the largest n in the problem and a clue from its wording. See which complexity classes fit and which patterns to try.

Choosing a Pattern from the Constraints

Step 1 of 9 · Press Space to play, arrow keys to step

Constraint on nClue in the problem

Complexity class

O(log n)

O(n)

O(n log n)

O(n²)

O(n³)

O(2ⁿ)

O(n!)

Initial state. A typical limit is about 1.0e8 simple operations in a second. With n = 1.0e5, which complexity classes fit? Then use the clue "Longest or shortest subarray / substring" to pick a pattern.

step:: 0
n:: 1.0e5
operations allowed:: 1.0e8
classes that fit:: 0

Speed

Things to try:

Choose n up to 100,000 and Longest or shortest subarray / substring. O(n log n) fits and O(n²) (10 billion operations) does not, so the answer must be a sliding window, a hash map or a sort, not a pair of loops.
Choose n up to 20 and Try choices: subsets, orders, paths. Now O(2ⁿ) (about a million operations) fits, so backtracking or a bitmask over all subsets is allowed.
Choose n up to 1,000,000,000. Only O(log n) fits. You cannot even read that much input, so look for a formula or a binary search on the answer.

What to watch: the list of patterns depends on the clue, and the list of complexity classes depends on n. Read them together. The two can disagree, because the tool lists patterns for a clue without checking cost. For example, at n of 10⁹ with the subarray clue it still names a sliding window, but a window scans every item, which is O(n) and does not fit. Always check that the pattern's own complexity is in the "fits" list.

Framework steps: from constraints to a pattern

Step 1: Constraints to complexity. Use this table for a limit of about 10⁸ operations.

Largest `n`	Complexity that usually fits	Typical approach
Up to about 10	`O(n!)`	Try every order (permutations)
11 to 12	`O(n!)` is borderline	11! is about 40 million and fits; 12! is about 479 million and is risky. Prefer pruning or a bitmask
Up to 20 to 25	`O(2ⁿ)`	Subsets, bitmask, backtracking
Up to about 400	`O(n³)`	Triple loops, Floyd-Warshall, some dynamic programming
Up to 5,000	`O(n²)`	Pairs, two-dimensional dynamic programming
Up to about 10,000	`O(n²)` is borderline	10⁴ squared is exactly 10⁸, so it needs a tight inner loop
Up to 10⁵ to 10⁶	`O(n log n)` or `O(n)`	Sorting, heaps, binary search, sliding window, hash maps
Up to 10⁹ and more	`O(log n)` or `O(1)`	Binary search on the answer, maths, formulas

Some limits point to a different shape. If n is about 10¹² and the statement does not give you an array, O(√n) (about 10⁶ steps) can fit, for example when testing whether a number is prime. If the input is an n by m grid, count n × m cells, not n.

Step 2: Clues to patterns.

Clue in the statement	Try this pattern
Sorted array, or "find a pair or triple"	Binary search, two pointers
Contiguous subarray or substring, "longest" or "shortest"	Sliding window, prefix sums with a hash map
Many range sums, with or without updates	Prefix sums, Fenwick tree, segment tree
"Next greater", "largest rectangle", "sliding window maximum"	Monotonic stack or queue
Linked list, cycle, "middle"	Fast and slow pointers
Grid, islands, flood fill	BFS or DFS on the grid, union-find
Fewest steps, unweighted graph	BFS
Cheapest route, weighted graph	Dijkstra, Bellman-Ford
Ordering with dependencies	Topological sort
"All combinations", "all arrangements", small `n`	Backtracking, bitmask
"Count the ways", "best score", overlapping subproblems	Dynamic programming
"Top k", "k-th largest", streaming	Heap, quickselect
Prefix lookups, autocomplete, many words	Trie
Maximise or minimise something, with a monotonic yes/no check	Binary search on the answer
Locally best choice looks safe	Greedy (and try to prove it)

What the pattern names mean.

Two pointers: two indices that move through the data, usually towards each other or in the same direction.
Sliding window: a range [left, right] that grows on the right and shrinks on the left while you keep a running total.
Prefix sums: a stored running total, so any range sum is one subtraction.
Monotonic stack or queue: a stack or queue kept in sorted order by removing items that can never be the answer.
Binary search on the answer: guess a value, check it with a yes/no test, and halve the range of guesses.
Backtracking: build a choice step by step and undo it when it cannot work.
Bitmask: a number whose bits record which items are chosen.
Greedy: take the locally best choice at each step.

Check before you commit. A pattern only works when its precondition holds.

Sliding window for sums needs non-negative numbers. With negatives, adding an item can make the sum smaller, so shrinking the window no longer fixes it. Use prefix sums with a map instead.
Binary search on the answer needs a monotonic yes/no check: if value x works, every larger (or every smaller) value must work too.
Two pointers on a pair usually needs sorted data, or you must sort first and accept O(n log n).

Step 3: Improve the brute force. Ask which work is repeated (cache it with a hash map or memoisation), which work is wasted (skip it with two pointers or a monotonic structure), and which order helps (sort first).

For example, checking every pair in an array of n items means about n(n-1)/2 pairs. At n = 100,000 that is nearly 5 billion pair checks, far over the budget. If you sort first (about 1.7 million operations) and then walk two pointers inwards (about 100,000 steps), the total is under 2 million, which fits easily. The reason is that sorting made the wasted pairs impossible to need, so the pointers can skip them.

Always say the brute force and its cost before improving it. This is the interview habit that matters most: it shows that the faster solution comes from a reason, not a guess.

Worked example: longest subarray with sum at most k

Problem. Given non-negative integers and a number k, find the length of the longest contiguous subarray whose sum is at most k. The array can have 200,000 items.

Restate. For [2, 1, 3, 1, 2] and k = 5, the subarray [1, 3, 1] has sum 5 and length 3.
Constraints. n = 200,000, so O(n²) is 4 × 10¹⁰ operations. Too slow. We need O(n log n) or O(n).
Clues. "Contiguous subarray", "longest", and a sum condition.
Pattern. A sliding window, because all numbers are non-negative.
Brute force. Try every start and end: O(n²) time (or O(n³) if you re-add each sum). Then improve it: each item enters the window once and leaves once, so O(n) time and O(1) space.
Test. Trace the window on [2, 1, 3, 1, 2] with k = 5.
State. O(n) time, O(1) space.

Step	Add	Window	Sum	Action	Best length
1	2	`[2]`	2	fits	1
2	1	`[2, 1]`	3	fits	2
3	3	`[2, 1, 3]`	6	too big, remove 2	2
3		`[1, 3]`	4	fits	2
4	1	`[1, 3, 1]`	5	fits	3
5	2	`[1, 3, 1, 2]`	7	too big, remove 1, then 3	3
5		`[1, 2]`	3	fits	3

The answer is 3. Edge cases to test: an empty array (answer 0), one item larger than k (the window becomes empty, answer 0), and all items equal.

Framework time complexity

`n`	Operations for `O(n)`	`O(n log n)`	`O(n²)`	`O(2ⁿ)`	Fits in about 10⁸?
20	20	about 86	400	about 1 million	All of them, up to `O(2ⁿ)`
1,000	1,000	about 10,000	1 million	Far too large	Up to `O(n²)`
100,000	100,000	about 1.7 million	10 billion	Far too large	Up to `O(n log n)`
1,000,000	1 million	about 20 million	1 trillion	Far too large	Up to `O(n log n)`
1,000,000,000	1 billion	Too slow	Too slow	Too slow	`O(log n)` only

These counts ignore constant factors, so treat them as a guide. A simple loop is faster than a hash map lookup, and a O(n log n) algorithm with a big constant can still be slow. Memory limits matter too: an array of 10⁹ integers does not fit in typical memory. As a typical rule of thumb (limits differ between judges and services), 256 MB holds about 6 × 10⁷ four-byte integers. A table of n by n with n = 5,000 has 25 million cells, which is fine, but with n = 10⁵ it has 10¹⁰ and is not.

Time budgets also depend on the language. About 10⁸ simple operations is realistic in compiled languages, but plan for roughly 10⁷ in Python, and always check the actual limit in the problem.

Constraints with more than one variable. Sometimes the statement gives n and m, or V and E. Then the cost is a formula in both, such as O(n × m) or O((V + E) log V). Work out the product or sum for the largest values of each, and do not collapse them into one n.

Common mistakes

Reading only n. Missing a second limit such as k, m or the value range changes which algorithm fits.
Ignoring constants. An O(n log n) solution with heavy work per step can be slower than a light O(n²) at small n.
Using a sliding window with negative numbers. The window logic breaks, as shown in the checks under Step 2.
Forgetting overflow. A sum of 200,000 values each up to 10⁹ can reach 2 × 10¹⁴, which does not fit in a 32-bit integer. Use a 64-bit type in Java, Go, Rust and C++. Python integers do not overflow. (The numbers here are an illustrative case.)
Skipping the brute force. Without a baseline you cannot show that the faster idea is correct.
Stopping at the first idea. If a pattern does not fit the budget, go back to the clues and pick another one.

The framework vs other ways of working

Job	Constraint-first framework	Recall a memorised solution	Start coding at once	Brute force only
Finds a fast enough algorithm	Yes, by design	Only for problems you have seen	By luck	No, may time out
Works on a new problem	Yes	No	Sometimes	Yes, but slowly
Explains the reasoning clearly	Yes	Weak	Weak	Partly
Avoids wasted effort	Yes	Yes	No	Yes
Time to first idea	A minute	Instant	Instant, but often wrong	Instant
Best for	Interviews and unfamiliar problems	Review before an interview	Tiny problems	Establishing a baseline

The framework wins on unfamiliar problems and when you must explain your thinking. Memorised solutions win only when the problem matches one you have already solved.

How to explain your approach in an interview

Think out loud in this order: restate, constraints, brute force and its cost, the pattern you will use and why, then the improved complexity.
Quote the constraint: "n is up to 100,000, so O(n²) is 10 billion operations, too slow. I need O(n log n) or better."
Name the pattern from the clue: "A contiguous subarray with a condition suggests a sliding window or prefix sums."
Finish with checks: edge cases, the final time and space in terms of n, and one alternative with its trade-off.

Where you meet constraint-driven design in real systems

The same habit, "work out the size of the problem first", is how engineers choose data structures and architectures, not only how contestants solve puzzles. Here are three of them drawn out, the first with code you can run, then more examples.

Example 1: Choosing an algorithm from the size of the data

Before writing a feature that compares every pair of records, an engineer asks how many records there will be. With 1,000 records a nested loop does a million comparisons and is fine. With 10 million it does 10¹⁴, which would take days, so a hash join or a sort-based approach is needed. Open the example below to see the picture and the code.

Code: the slowest algorithm that fits a sizeTime O(1)Memory O(1)

Each cell is the approximate number of operations. Only the classes up to O(n log n) stay under about 100 million, so a pair of nested loops (O(n squared), 10 billion) is too slow.

# Turn a constraint on n into the slowest algorithm you can afford.
# Rule of thumb: about 10^8 simple operations fit in one second.
# Time: O(1) per size checked. Memory: O(1).
import math

BUDGET = 1e8

def ops(name, n):                      # number of operations for each complexity class
    if name == "O(log n)":    return math.log2(n)
    if name == "O(n)":        return float(n)
    if name == "O(n log n)":  return n * math.log2(n)
    if name == "O(n^2)":      return float(n) ** 2
    if name == "O(n^3)":      return float(n) ** 3
    if name == "O(2^n)":      return 2.0 ** n if n <= 60 else math.inf
    if name == "O(n!)":       return float(math.factorial(n)) if n <= 20 else math.inf

CLASSES = ["O(log n)", "O(n)", "O(n log n)", "O(n^2)", "O(n^3)", "O(2^n)", "O(n!)"]

def slowest_that_fits(n):
    # The classes are listed from fastest to slowest, so the last one that fits is the slowest we can afford.
    fitting = [c for c in CLASSES if ops(c, n) <= BUDGET]
    return fitting[-1]

for n in [20, 1000, 100000, 1000000, 1000000000]:
    print(f"n={n}: {slowest_that_fits(n)}")

Each version estimates the number of operations for each complexity class and prints the slowest class that stays under 10⁸ operations for five sizes. Every version was compiled and run, and printed the same five lines: O(2^n) for 20, O(n^2) for 1,000, O(n log n) for 100,000 and 1,000,000, and O(log n) for 1,000,000,000.

Example 2: Capacity planning

A team estimates traffic before choosing a design: 100 million requests a day is about 1,200 requests a second on average, with peaks several times higher. That number decides whether one database is enough, whether to add a cache, and whether a queue is needed. System design interviews ask for exactly this kind of estimate first.

Estimate the size of the problem first. The number tells you which designs are possible and which are not, before any detail is decided.

Example 3: Matching the clue to a pattern

Reading a problem is like reading a symptom. The clue points to the family of solutions before you think about details.

A clue in the statement leads to a pattern, and the pattern comes with a known complexity. If the complexity does not fit the constraint, try the next pattern.

More real-world scenarios

4. Database queries

An analyst's query that joins two big tables without an index is a nested loop in disguise. Looking at the size of each table and adding the right index is the same exercise as picking O(n log n) over O(n²).

5. Choosing a data structure

Needing "lookup by key" points to a hash map, "keep sorted" to a balanced tree, and "smallest first" to a heap. The need decides the structure, not habit.

6. Search and autocomplete

A search box with millions of entries must respond in milliseconds, so the design uses precomputed indexes (a trie or inverted index) instead of scanning, which the constraints make unavoidable.

7. Batch jobs and ETL

A nightly job that processes a billion rows must be linear or near linear and stream the data. A pass that is quadratic in the number of rows would never finish.

8. Games and real-time systems

A game has about 16 milliseconds per frame, so collision detection uses spatial grids or trees instead of checking every pair of objects.

9. Code review and performance bugs

Spotting a loop inside a loop over user data, or a lookup in a list inside a loop, is the framework applied to code you did not write.

10. Machine learning pipelines

Choosing between exact nearest-neighbour search and an approximate index depends on how many vectors there are and how fast queries must be.

11. Estimating and negotiating scope

Knowing that a feature needs O(n²) work for large n lets an engineer say early that it will not scale and propose an alternative.

12. Interviews and contests

The constraint-first routine is what makes an unfamiliar problem tractable under time pressure, by narrowing the solution space before any code is written.

Language standard libraries

Knowing what your language's standard tools cost is part of the framework. These are the building blocks that give the complexities used in the table.

Language	Sort	Binary search	Hash map	Priority queue
Java	`Arrays.sort`, `Collections.sort`: O(n log n)	`Arrays.binarySearch`: O(log n)	`HashMap`: O(1) average	`PriorityQueue`: O(log n) push and pop
C++	`std::sort`: O(n log n)	`std::lower_bound`: O(log n)	`std::unordered_map`: O(1) average	`std::priority_queue`: O(log n)
C#	`Array.Sort`, `List.Sort`: O(n log n)	`Array.BinarySearch`: O(log n)	`Dictionary`: O(1) average	`PriorityQueue` (.NET 6 and later): O(log n)
Rust	`slice::sort`, `sort_unstable`: O(n log n)	`slice::binary_search`: O(log n)	`HashMap`: O(1) average	`BinaryHeap`: O(log n)
Python	`sorted`, `list.sort`: O(n log n)	`bisect`: O(log n)	`dict`: O(1) average	`heapq`: O(log n)
Go	`sort.Slice`, `slices.Sort`: O(n log n)	`sort.Search`, `slices.BinarySearch`: O(log n)	`map`: O(1) average	`container/heap`: O(log n)
JavaScript	`Array.prototype.sort`: O(n log n)	None built in	`Map`, `Object`: O(1) average	None built in
Kotlin	`sorted`, `sortWith`: O(n log n)	`binarySearch`: O(log n)	`HashMap`: O(1) average	`PriorityQueue` (Java's): O(log n)

The takeaway from the table: sorting, searching, hashing and heaps are in every standard library, and they are the pieces that make O(n log n) the usual target when n is large. Hash map and heap costs are the typical ones; the worst case can be higher.

The takeaway

Whenever a problem or a design must run within a time budget, estimate the size first, work out which complexity fits, and then choose a pattern or structure that reaches it. When the size is tiny, it usually pays to write the simplest correct version instead.

Interview questions

Try answering out loud before you reveal hints. Interviewers care about how you reason, not just the final answer.

1.
A problem gives n up to 200,000 and asks for the longest subarray with sum at most k. What do you do first?
easy
2.
You see "find the k-th largest element in an unsorted array" with n up to 10⁶. Walk through your thinking.
medium
3.
Your solution is correct but times out. How do you find the bottleneck and improve it?
medium
4.
The constraint says n is at most 18. What does that tell you?
easy

Finished this lesson?

Progress is saved on this device. Create a free account to keep it everywhere.

← Previous

Randomized Algorithms

Topics:Problem solvingInterview frameworkConstraintsComplexityPatternsBig O