How Constraints Guide Algorithm Selection

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