You've learned to read constraints. Now let's use them systematically.

Most beginners approach algorithm selection backwards. They think: "What algorithms do I know?" then try to fit one to the problem. Engineers think: "What do the constraints allow?" and let that filter their options.

This difference is profound. The constraint-first approach:

1. Eliminates wasted effort — Why implement O(n²) only to discover it times out?
2. Reveals required complexity — The constraint tells you the complexity class you need
3. Guides learning — "I need O(n log n) here" tells you what techniques to study
4. Prevents overthinking — If O(n²) fits, don't hunt for O(n log n)

This page teaches you to use constraints as a systematic filter for algorithm selection.

Here's a systematic approach to algorithm selection that professionals use. Follow these steps in order:

Step 1: Extract All Constraints

Read the problem statement carefully. Identify:

• Input size bounds (n, m, Q, etc.)
• Time limit (or performance requirement)
• Memory limit (or space requirement)
• Special conditions (sorted input? positive numbers? unique elements?)

Step 2: Calculate the Complexity Ceiling

Using the time limit and input size, determine the maximum complexity class:

• What's n²? Over 10⁸? Then O(n²) is too slow.
• What's n × log(n)? Under 10⁸? Then O(n log n) works.
• What's n × Q? If both are large, you need fast queries.

Step 3: Eliminate Infeasible Approaches

Cross off any algorithm that exceeds your complexity ceiling. Be ruthless—if O(n²) won't fit, don't consider O(n²) algorithms no matter how elegant.

Step 4: Match Problem Pattern to Algorithm Class

Among the remaining feasible approaches, match the problem type to known algorithm patterns.

Step 5: Verify Against Memory Constraints

Confirm your chosen approach fits memory. A brilliant O(n log n) algorithm is useless if it needs O(n²) space.

Experienced engineers recognize common constraint patterns instantly. Each pattern implies specific algorithm classes:

Pattern 1: Very Small n (n ≤ 20)

Implication: Exponential algorithms are viable.

Signals: The problem wants you to explore all possibilities.

Typical approaches:

• Brute force enumeration: O(2ⁿ), O(n!)
• Bitmask DP: O(n × 2ⁿ)
• Meet-in-the-middle: O(2^(n/2))
• Complete search with pruning

Example constraint: "n ≤ 15, find minimum cost to visit all cities"

• This screams Traveling Salesman
• n ≤ 15 means bitmask DP with O(n² × 2ⁿ) is fine

Pattern 2: Medium n (n ≤ 1,000 to 5,000)

Implication: O(n²) is acceptable, maybe O(n³) for smaller values.

Signals: Classic DP, nested loops, or graph algorithms on dense graphs.

Typical approaches:

• 2D dynamic programming: O(n²)
• Floyd-Warshall shortest paths: O(n³)
• Comparison-based algorithms with nested loops
• Graph algorithms on adjacency matrices

Example constraint: "n ≤ 2,000, find longest common subsequence"

• Classic O(n²) DP is expected and sufficient
• Don't hunt for O(n log n) LCS unless needed

Pattern 3: Large n (n ≤ 10⁵ to 10⁶)

Implication: O(n log n) or O(n) required.

Signals: Sorting, binary search, divide and conquer, or specialized data structures.

Typical approaches:

• Sorting + two pointers: O(n log n)
• Binary search on answer: O(n log X)
• Merge sort, quicksort: O(n log n)
• Single-pass with hash tables: O(n)
• Segment trees, BIT: O(n log n) build, O(log n) query

Example constraint: "n ≤ 10⁵, count inversions in array"

• O(n²) naive? 10¹⁰ ops → too slow
• Modified merge sort O(n log n)? ~1.7M ops → perfect

Pattern 4: Very Large n (n ≤ 10⁷ to 10⁸)

Implication: Must be O(n) or close to it.

Signals: Linear scans, counting, prefix sums, simple arithmetic.

Typical approaches:

• Single-pass algorithms: O(n)
• Counting sort: O(n + k)
• Prefix/suffix computations: O(n)
• Simple array manipulation

Example constraint: "n ≤ 10⁷, find max subarray sum"

• Even O(n log n) is risky at 10⁷ × 23 ≈ 2.3 × 10⁸
• Kadane's O(n) is clearly expected

Pattern 5: Astronomical n (n ≤ 10⁹ or more)

Implication: O(log n) or O(1) only. Cannot even read input linearly!

Signals: Mathematical formulas, binary search on answer, matrix exponentiation.

Typical approaches:

• Direct formula computation: O(1)
• Binary search: O(log n)
• Matrix exponentiation: O(log n)
• Digit DP (for counting problems)

Example constraint: "n ≤ 10¹⁸, find nth Fibonacci number mod 10⁹+7"

• Can't iterate 10¹⁸ times
• Matrix exponentiation: O(log n) ≈ 60 operations

Real problems often have multiple constraints that interact. Analyzing them together reveals more than analyzing each alone.

The Query Pattern: Large n, Large Q

n ≤ 10⁵ elements, Q ≤ 10⁵ queries

Analysis:

• Total budget: ~10⁸ operations (1 second)
• Naive O(n) per query: n × Q = 10¹⁰ ❌
• Fast O(log n) per query: Q × log(n) ≈ 1.7 × 10⁶ ✓
• O(1) per query with O(n) preprocess: n + Q = 2 × 10⁵ ✓✓

Implication: You need preprocessing or logarithmic queries. This pattern signals segment trees, binary indexed trees, or prefix sums.

The Reverse Pattern: Large n, Tiny Q

n ≤ 10⁶ elements, Q ≤ 10 queries

Analysis:

• Total budget: ~10⁸ operations
• O(n) per query: 10 × 10⁶ = 10⁷ ✓
• Even O(n log n) per query: 10 × 2 × 10⁷ = 2 × 10⁸ ⚠️ borderline

Implication: Simple per-query algorithms are fine. Don't waste time on complex preprocessing.

The Grid Pattern: n × m Constraints

Grid of n × m cells, n, m ≤ 1,000

Analysis:

• Total cells: 10⁶
• O(n × m) scan: 10⁶ ✓
• O(n × m × min(n,m)) DP: 10⁹ ⚠️ borderline
• O(n² × m²): 10¹² ❌

Implication: Standard grid DP is fine. Four-loop approaches (two coordinates each) are too slow.

The Sum Constraint Pattern

Sum of n across all test cases ≤ 2 × 10⁵

This is a game-changer! It means:

• Individual test cases might have large n
• But total work across ALL cases is bounded
• O(n) per case is guaranteed to work overall

Don't be intimidated by "n ≤ 10⁵" when there's a sum constraint—the amortized budget is what matters.

The Product Constraint Pattern

n × m ≤ 10⁶

This allows asymmetric dimensions:

• n = 10⁶, m = 1: Long array
• n = 1,000, m = 1,000: Square grid
• n = 10, m = 10⁵: Many short arrays

Implication: Algorithm must handle all shapes. O(n × m) total work is fine.

The Edge vs Node Pattern (Graphs)

n ≤ 10⁵ nodes, m ≤ 2 × 10⁵ edges

Analysis:

• Graph is relatively sparse (m ≈ 2n)
• O(n + m) algorithms (BFS, DFS): 3 × 10⁵ ✓
• O(m log m) for edge sorting: 3.4 × 10⁶ ✓
• O(n²): 10¹⁰ ❌ (don't use adjacency matrix!)

Implication: Use adjacency list, not matrix. Dijkstra with heap O((n + m) log n) works.

Once you know your complexity ceiling, you can match problem types to algorithm classes. Here are the most common mappings:

For O(n²) budget:

Sorting problems:

• Bubble sort, insertion sort, selection sort
• When n ≤ 5,000 and simple implementation matters

Subsequence problems:

• Longest Common Subsequence (2D DP)
• Longest Increasing Subsequence (can also be O(n log n))
• Edit Distance

Comparison problems:

• Compare all pairs: nested loops
• Check all edges in dense graph

Graph problems:

• Floyd-Warshall (O(n³) for small n ≤ 400)
• Adjacency matrix algorithms

For O(n log n) budget:

Sorting-based problems:

• Any problem that benefits from sorted order
• Meeting/interval scheduling
• Merge sort for inversions counting

Divide and conquer:

• Binary search on arrays
• Merge-based algorithms
• Closest pair of points

Tree/set operations:

• Balanced BST operations
• Priority queue-based algorithms
• Segment tree build + queries

Search problems:

• Binary search on answer
• Two pointers after sorting

For O(n) budget:

Linear scans:

• Maximum subarray (Kadane's)
• Finding duplicates with hash set
• Two Sum with hash map
• Sliding window problems

Counting problems:

• Counting sort
• Frequency tables
• Prefix sums

Stack/queue patterns:

• Next greater element
• Valid parentheses
• Monotonic stack patterns

Two pointers (on sorted or structured data):

• Pair sum in sorted array
• Container with most water

For O(log n) or O(1) budget:

Mathematical:

• GCD (Euclidean algorithm)
• Modular exponentiation
• Direct formulas (arithmetic/geometric series)

Binary search variants:

• Search in rotated array
• Find peak element
• Binary search on answer space

Precomputed lookups:

• O(n) preprocessing, O(1) query
• Sparse tables for RMQ
• Precomputed factorials/inverses

Let's walk through complete examples of constraint-driven algorithm selection.

Example 1: Two Sum

Problem: Given array of n integers, find if any two sum to target. Constraints: n ≤ 10⁵, time limit 1 second.

Step 1: Identify constraints

• n ≤ 10⁵
• Budget: 10⁸ operations

Step 2: Calculate complexity ceiling

• n² = 10¹⁰ → exceeds 10⁸ by 100x
• n log n = 1.7 × 10⁶ → fits easily
• n = 10⁵ → fits easily

Step 3: Eliminate infeasible approaches

• ❌ Brute force O(n²): All pairs comparison
• ✓ O(n log n): Sort + two pointers
• ✓ O(n): Hash set lookup

Step 4: Select approach

• Both O(n log n) and O(n) work. O(n) is simpler for this problem.
• Use hash set: for each element, check if (target - element) exists.

Step 5: Verify memory

• Hash set of n integers: n × (8 + overhead) ≈ 2 MB ✓

Example 2: Range Sum Queries

Problem: Given array of n integers, answer Q queries for sum of elements in range [l, r]. Constraints: n ≤ 10⁵, Q ≤ 10⁵, time limit 2 seconds.

Step 1: Identify constraints

• n ≤ 10⁵, Q ≤ 10⁵
• Budget: 2 × 10⁸ operations

Step 2: Calculate complexity ceiling

• O(n) per query: n × Q = 10¹⁰ ❌
• O(log n) per query with O(n log n) build: 10⁵ × 17 + 10⁵ × 17 ≈ 3.4 × 10⁶ ✓
• O(1) per query with O(n) preprocess: 10⁵ + 10⁵ = 2 × 10⁵ ✓✓

Step 3: Eliminate infeasible approaches

• ❌ Naive sum for each query: O(n × Q)
• ✓ Segment tree: O(n + Q log n)
• ✓ Prefix sums: O(n + Q)

Step 4: Select approach

• Static array (no updates) → prefix sums are simpler and faster
• If updates existed → segment tree would be needed

Step 5: Verify memory

• Prefix sum array: n integers ≈ 0.4 MB ✓

Example 3: All-Pairs Shortest Paths

Problem: Given weighted graph, find shortest path between every pair of nodes. Constraints: n ≤ 400 nodes, m ≤ n², time limit 2 seconds.

Step 1: Identify constraints

• n ≤ 400, dense graph possible
• Budget: 2 × 10⁸ operations

Step 2: Calculate complexity ceiling

• n³ = 64 × 10⁶ → fits comfortably
• Even n³ with constant factor 3 → 192 × 10⁶ → borderline but ok

Step 3: Eliminate infeasible approaches

• ✓ Floyd-Warshall O(n³): Perfect fit
• ⚠️ n × Dijkstra O(n × (m + n) log n): Also works but more complex

Step 4: Select approach

• n ≤ 400 with all-pairs query → Floyd-Warshall is the expected solution
• Simple, well-known, handles negative edges (no negative cycles)

Step 5: Verify memory

• n × n distance matrix: 400 × 400 × 4 ≈ 0.6 MB ✓

Example 4: Subset Sum (Small n)

Problem: Given n integers, check if any subset sums to target. Constraints: n ≤ 20, integers up to 10⁹, time limit 2 seconds.

Step 1: Identify constraints

• n ≤ 20 (very small!)
• Values up to 10⁹ (too large for DP on sum)
• Budget: 2 × 10⁸ operations

Step 2: Calculate complexity ceiling

• 2ⁿ = 2²⁰ ≈ 10⁶ → easily fits
• n × 2ⁿ = 2 × 10⁷ → fits

Step 3: Analyze approaches

• ❌ DP on sum: O(n × target) = O(20 × 10⁹) impossible
• ✓ Bitmask enumeration: O(2ⁿ) = 10⁶
• ✓ Meet-in-the-middle: O(2^(n/2)) = 10³ each half

Step 4: Select approach

• Small n + large values = bitmask enumeration
• The constraint deliberately blocks DP and enables exponential

Step 5: Verify memory

• Storing 2ⁿ sums: 10⁶ × 8 ≈ 8 MB ✓

Some constraints carry special meaning beyond raw numbers. Learn to recognize these signals.

"Values are small" (values ≤ 10⁶ with large n)

Signal: Counting sort or value-indexed DP might work.

Example: "n ≤ 10⁷ elements, each element ≤ 10⁶"

• Can't comparison-sort: O(n log n) = 2.3 × 10⁸ risky
• Counting sort: O(n + k) where k = 10⁶ → perfect

"Array is sorted" or "Sorted in non-decreasing order"

Signal: Binary search is available. Two pointers work.

Example: "Given sorted array, find pair summing to target"

• Don't sort again (it's given!)
• Two pointers: O(n), not O(n log n)

"All elements are distinct" or "Unique integers"

Signal: No duplicates to handle. Simpler logic.

Example: "Array of n distinct integers"

• Finding kth smallest? No tie-breaking needed.
• Hash lookups guaranteed O(1) with no collisions

"Elements are 0 or 1" or "Binary values"

Signal: Bit manipulation, special counting techniques.

Example: "Given binary array, find longest subarray with equal 0s and 1s"

• Convert 0→-1, problem becomes "longest subarray with sum 0"
• Prefix sum + hash map: O(n)

"Coordinates up to 10⁹" (but n is small)

Signal: Coordinate compression needed if using arrays.

Example: "n ≤ 10⁵ points with coordinates up to 10⁹"

• Can't create array of size 10⁹
• Compress coordinates: map to 1..n, then use array

"Tree with n nodes" or "Connected graph with n-1 edges"

Signal: Tree-specific algorithms apply. No cycles.

Example: "Given tree with n ≤ 10⁵ nodes"

• DFS/BFS from any root
• DP on trees might be expected
• LCA preprocessing might be useful

"Queries are online" or "Answer each query before seeing next"

Signal: Can't preprocess queries. Need persistent or online structures.

Contrast: "Offline queries" means you can reorder them for efficiency (e.g., Mo's algorithm).

"Modulo 10⁹+7" or "Answer mod M"

Signal: Answer is huge. Need modular arithmetic.

Example: "Find number of subsequences, answer mod 10⁹+7"

• Result could be astronomically large
• Use modular arithmetic throughout, not just at the end

"Exactly k" vs "At most k"

Signal: "Exactly k" often uses inclusion-exclusion or sliding window. "At most k" might use binary search on k.

Here's a decision flowchart you can apply to any problem:

START: Read problem constraints
    ↓
[1] Is n very small (≤ 20)?
    → YES: Consider exponential algorithms (2ⁿ, n!)
    → NO: Continue
    ↓
[2] Is n small-medium (≤ 5,000)?
    → YES: O(n²) algorithms are viable
    → NO: Continue
    ↓
[3] Is n large (≤ 10⁶)?
    → YES: Need O(n log n) or O(n)
    → NO: Continue (very large n)
    ↓
[4] Is n huge (> 10⁶)?
    → YES: Need O(n) or better. Maybe O(log n) or O(1).

After determining complexity budget, ask:

[5] Are there Q queries?
    → Q large: Need fast per-query (O(log n) or O(1))
    → Q small: Per-query can be O(n)
    ↓
[6] What's the memory budget?
    → Calculate if 2D arrays fit
    → Consider in-place algorithms if tight
    ↓
[7] Are there special constraints?
    → Sorted input: Two pointers, binary search
    → Small values: Counting-based approaches
    → Tree structure: Tree-specific algorithms

Constraints are the first thing to analyze—before you even think about algorithm specifics. They narrow your options, eliminate dead ends, and point toward the expected solution class.

What's next:

We've covered how constraints guide algorithm selection. But what about when multiple viable algorithms exist with different trade-offs? The next page explores time vs. space trade-offs—how to choose when you can trade memory for speed or vice versa.