Constraint-Based Selection - Learning Module

Loading content...

0/276

Using Constraints to Eliminate Approaches

The Power of Elimination

So far, we've focused on what constraints enable—which algorithms are fast enough to pass. But equally important is what constraints eliminate—which approaches to immediately discard. Master eliminators solve problems faster not by knowing more algorithms, but by wasting no time on doomed approaches.

When facing a problem with n ≤ 10⁵, an experienced solver doesn't consider O(n²) solutions. They don't even let O(n²) ideas form fully in their mind. That entire branch of the solution tree is pruned before exploration begins. This mental discipline—ruthless elimination based on constraints—dramatically accelerates problem-solving.

What You Will Learn

By the end of this page, you'll develop the discipline to immediately eliminate infeasible approaches based on constraints. You'll learn the complete elimination checklist, understand common elimination scenarios, and gain the confidence to narrow your focus to viable solutions without second-guessing.

The Elimination Mindset

Elimination is not about being pessimistic—it's about being efficient. Every approach you eliminate saves time that would have been wasted on:

Designing a solution that will fail
Implementing code that will TLE
Debugging performance issues that can't be fixed
Frustration from the cycle of hope and failure

The Cost of Not Eliminating:

Consider a developer who doesn't practice elimination. Facing a problem with n ≤ 10⁵:

First idea: nested loops → implements → TLE
Second idea: optimize with hash map → implements → still TLE (O(n²) with O(1) inner work is still O(n²))
Third idea: finally realizes n² is fundamentally impossible
Fourth idea: segment tree → finally works

Time wasted: potentially hours on approaches 1-3.

An elimination-first solver sees n ≤ 10⁵ and immediately knows:

NO nested loops over the full array
NO algorithms with O(n²) complexity
YES to O(n log n) structures if needed
MAYBE O(n √n) if nothing better exists

They skip directly to approach 4 or equivalent.

Elimination Before Exploration

Make elimination your first step, not an afterthought. Before brainstorming solutions, look at constraints and explicitly list what's eliminated. This focuses your creative energy on viable approaches only.

The Complete Elimination Checklist

Use this systematic checklist when analyzing any problem. Work through each elimination category to narrow your solution space.

Step 1: Time Complexity Elimination

Based on primary constraint n:

n Range	Eliminate These Complexities
n > 25	O(2ⁿ), O(n!), O(n × 2ⁿ) — all exponential
n > 500	O(n³), O(n⁴) — cubic and higher
n > 10,000	O(n²), O(n² log n) — quadratic
n > 10⁶	O(n √n), O(n log² n) — sub-linear but super-log
n > 10⁷	O(n log n) — log factor eliminated
n > 10⁸	Anything that reads all input — need formula

Instant Eliminations by Constraint

•n > 10,000 → Eliminate: nested for-loops, O(n²) DP, all-pairs algorithms
•n > 10⁶ → Eliminate: balanced tree operations in tight loops, repeated sorting
•n > 10⁸ → Eliminate: reading all input, any algorithm with linear scan
•Values > 10⁹ → Eliminate: direct array indexing by value, value-based DP arrays
•Memory ≤ 64MB → Eliminate: large 2D arrays, storing full graph adjacency matrix for large n
•Multiple test cases → Eliminate: heavy preprocessing that can't be reused

Step 2: Space Complexity Elimination

Memory limits constrain data structures:

64 MB limit:
- Cannot store 10⁷ integers (40 MB for ints, but limited headroom)
- Cannot use adjacency matrix for graph with V > 4000
- 2D DP table limited to roughly 4000 × 4000

256 MB limit:
- Can store ~6 × 10⁷ integers
- Adjacency matrix up to ~8000 × 8000
- 2D DP up to ~8000 × 8000

1 GB limit:
- Can store ~2.5 × 10⁸ integers
- Most practical limits removed

Step 3: Structural Elimination

Problem structure eliminates algorithm categories:

Not a tree → Eliminate: tree DP, LCA queries, tree-specific traversals
Has cycles → Eliminate: topological sort, simple tree algorithms
Graph is dense (E ≈ V²) → Eliminate: sparse graph algorithms that assume E ≪ V²
Online queries → Eliminate: offline algorithms (Mo's), approaches requiring all queries upfront
No sorting allowed → Eliminate: sorting-dependent approaches

Common Elimination Scenarios

Let's work through realistic constraint sets and practice elimination thinking.

Scenario 1: Large Array with Queries

Constraints:
n ≤ 10⁵ (array size)
q ≤ 10⁵ (number of queries)
Time limit: 2 seconds

Elimination Analysis:

✗ O(n × q) = 10¹⁰ — ELIMINATED (100× over budget) ✗ O(n² + q) = 10¹⁰ — ELIMINATED ✗ Per-query O(n) with no preprocessing — ELIMINATED

✓ O(n + q log n) — Segment tree with build + queries ✓ O((n + q) √n) — Mo's algorithm for offline queries ✓ O(n log n + q) — Preprocessing + O(1) queries (prefix sums, sparse table)

Scenario 2: Small n, Complex Problem

Constraints:
n ≤ 15
m ≤ 100
Time limit: 1 second

Elimination Analysis:

✗ Polynomial algorithms that don't use n's smallness — likely not the intended solution

✓ O(2ⁿ × m) = 32768 × 100 = 3.3 × 10⁶ — acceptable ✓ O(n! × something small) — up to ~1.3 × 10¹² / something = depends on "something" ✓ Bitmask DP with m factor

Insight: n = 15 is screaming for exponential-in-n approach. Look for subset structure.

Scenario 3: Graph Problem

Constraints:
V ≤ 10⁵ (vertices)
E ≤ 2 × 10⁵ (edges)
Time limit: 2 seconds

Elimination Analysis:

✗ Floyd-Warshall O(V³) = 10¹⁵ — ELIMINATED ✗ Bellman-Ford O(V × E) = 2 × 10¹⁰ — ELIMINATED ✗ Adjacency matrix (V² space) — ELIMINATED (4 × 10¹⁰ bytes)

✓ Dijkstra O((V + E) log V) ≈ 5 × 10⁶ — works ✓ BFS O(V + E) ≈ 3 × 10⁵ — works ✓ DFS O(V + E) — works ✓ Adjacency list representation — required

Scenario 4: String Problem with Large Values

Constraints:
n ≤ 10⁵ (string length)
Characters: lowercase English letters (26)
Time limit: 1 second

Elimination Analysis:

✗ O(n²) substring enumeration — ELIMINATED ✗ O(n × 26ⁿ) anything — obviously eliminated ✗ Suffix tree/array with O(n²) construction — need efficient construction

✓ O(n × 26) = 2.6 × 10⁶ — alphabet-sized inner loop per character ✓ O(n log n) — sorting-based approaches ✓ O(n) with O(26) state — linear with bounded auxiliary

Insight: The 26-letter alphabet means O(n × 26) is essentially O(n). Look for character-frequency or per-character-type solutions.

Document Your Eliminations

During problem-solving, mentally or physically note: "Eliminated X because of Y." This prevents returning to dead ends and clarifies your thinking. In interviews, stating eliminations aloud demonstrates mature problem-solving.

Eliminating Specific Algorithm Families

Beyond complexity elimination, certain constraint patterns eliminate entire algorithm families regardless of their complexity.

Shortest Path Algorithm Elimination:

When to Eliminate Shortest Path Algorithms
Constraint/Scenario	Eliminate	Use Instead
V > 500	Floyd-Warshall (O(V³))	Dijkstra or Bellman-Ford per source
E > V, negative edges	Dijkstra (doesn't handle negatives)	Bellman-Ford
V × E > 10⁸, negative edges	Bellman-Ford (too slow)	SPFA or problem-specific approach
Unweighted graph	Dijkstra (overkill)	BFS (simpler, same complexity)
Single source needed	Floyd-Warshall (overkill)	Dijkstra from one source

Sorting Algorithm Elimination:

Constraint	Eliminate	Use Instead
Already sorted input	Any sorting (unnecessary overhead)	Direct processing
Values in [0, k] with k ≤ n	Comparison sorts O(n log n)	Counting sort O(n + k)
n > 10⁷	Any comparison sort (log factor hurts)	Counting/Radix if applicable
Need stable sort	Quick sort (unstable)	Merge sort
Memory constrained	Merge sort (O(n) extra space)	Heap sort (in-place)

Data Structure Elimination:

Constraint	Eliminate	Use Instead
n > 10⁷ with many operations	Hash map with high overhead	Direct array if values bounded
Need ordered iteration	Hash map / Hash set	BST / TreeSet / sorted vector
Need range queries + updates	Simple array (O(n) per query)	Segment tree, Fenwick tree
Static data, range queries	Segment tree (overkill for static)	Sparse table (simpler, O(1) query)
Values > 10⁹	Array indexed by value	Hash map or coordinate compression

Elimination Isn't Always Clear-Cut

Sometimes an algorithm at the complexity boundary might work with good constants and optimization. When in doubt, implement the clearly-viable approach first. Only consider boundary algorithms if no better option exists.

Value-Based Elimination

The range of values (not sizes) creates its own elimination criteria. This is often overlooked but equally important.

Large Value Ranges (a[i] ≤ 10⁹):

Eliminated by Large Values

•Direct array indexing by value — Cannot allocate 10⁹-sized array
•Value-based DP states — dp[value] with value up to 10⁹ is impossible
•Counting sort — Requires array sized to value range
•Sieve of Eratosthenes up to max value — Only viable if max value ≤ 10⁷
•Iterating through all values — 10⁹ iterations is too slow

What to Use Instead:

Coordinate Compression — Map n distinct values to [0, n-1], then use value-indexed approaches on compressed values.
Hash Maps — O(1) amortized access for arbitrary keys. Higher constant factor but handles any value range.
Sorting + Binary Search — Sort values, then binary search for positions. O(log n) per lookup.
Value-Independent Algorithms — Many algorithms only compare values, never index by them. Sorting, segment trees with comparison, etc.

Small Value Ranges (a[i] ≤ 100):

Conversely, small value ranges enable approaches:

✓ Direct array indexing by value — 100-sized arrays are trivial ✓ Value-based DP — dp[n][100] = 100n states, manageable ✓ Frequency counting — Exact counts for each value ✓ Nested loops over value range — 100 × 100 = 10⁴ is nothing

Coordinate Compression Example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// Problem: Count inversions where a[i] ≤ 10^9
// Cannot use value-indexed Fenwick tree directly
// Solution: Compress values to [0, n-1], then use Fenwick tree
 
function countInversions(arr: number[]): number {
    const n = arr.length;
    
    // Step 1: Coordinate compression
    const sorted = [...arr].sort((a, b) => a - b);
    const valueToRank = new Map<number, number>();
    let rank = 0;
    for (const val of sorted) {
        if (!valueToRank.has(val)) {
            valueToRank.set(val, rank++);
        }
    }
    
    // Step 2: Map original values to ranks
    const compressed = arr.map(v => valueToRank.get(v)!);
    
    // Step 3: Now use Fenwick tree indexed by compressed values
    // (Fenwick tree implementation omitted for brevity)
    // Count elements > current that appeared before
    
    // Values now in [0, n-1], Fenwick tree of size n is feasible
    // Original values up to 10^9 would require 10^9-sized tree!
    
    return countWithFenwick(compressed);
}
 
// Key insight: We only care about relative order, not absolute values
// Compression preserves relative order while enabling value-indexed structures

Memory-Based Elimination

Memory constraints eliminate algorithms independently of time complexity. An algorithm can be fast enough but still fail due to space requirements.

Memory Calculation Quick Reference:

1 int = 4 bytes
1 long long = 8 bytes
1 pointer = 8 bytes (64-bit)
1 object in Java/C# = ~16+ bytes overhead + fields

1 MB = 10^6 bytes ≈ 250,000 ints
64 MB ≈ 16 million ints
256 MB ≈ 64 million ints
1 GB ≈ 250 million ints

Memory Elimination Scenarios
Memory Limit	Maximum Viable	Eliminate
64 MB	~1.5 × 10⁷ ints, 2D: 4000 × 4000	Large graphs as matrix, full 2D DP for n > 4000
128 MB	~3 × 10⁷ ints, 2D: 5500 × 5500	n × n matrices for n > 5500
256 MB	~6 × 10⁷ ints, 2D: 8000 × 8000	Very large 2D structures
512 MB	~1.2 × 10⁸ ints	Only the most extreme cases

Common Memory Elimination Patterns:

1. Graph Representation:

Adjacency matrix: O(V²) space. For V = 10,000: 400 MB just for the matrix.
Solution: Adjacency list. O(V + E) space.

2. 2D DP Optimization:

Standard 2D DP: O(n × m) space.
If current row only depends on previous row: O(m) space with rolling array.

3. Recursion Stack:

Deep recursion can cause stack overflow before memory limit is hit.
Recursion depth > 10⁵ is risky, > 10⁶ often fails.
Solution: Convert to iterative or increase stack size (where allowed).

4. Object Overhead:

Each Java/C# object has 16-24 bytes overhead.
10⁷ trivial objects = 160-240 MB just for overhead.
Solution: Use primitive arrays instead of object arrays.

The Rolling Array Technique

When a DP recurrence only uses the previous 1-2 rows, replace dp[n][m] with dp[2][m] and alternate rows. This reduces O(n×m) space to O(m), often the difference between passing and failing memory limits.

Communicating Elimination in Interviews

In technical interviews, explicitly stating what you're eliminating and why demonstrates structured thinking and earns credit even before you solve the problem.

The Elimination Dialogue:

Interviewer: "Find all pairs in an array that sum to a target. The array can have up to 10 million elements."

Strong Candidate Response:

"Ten million elements means n = 10⁷. Let me think about complexity constraints first.

A brute-force approach checking all pairs would be O(n²), which is 10¹⁴ operations—way too slow. That's eliminated immediately.

I need O(n log n) or better. Sorting plus two pointers would give O(n log n)—that's about 2.3 × 10⁸ operations, borderline but likely acceptable.

Even better, using a hash set for O(1) lookups gives me O(n) overall—just 10⁷ operations, very safe.

I'll go with the hash set approach. Does that sound reasonable before I implement?"

What This Demonstrates

•Complexity awareness — Immediate recognition that n² is infeasible for n = 10⁷
•Quantitative reasoning — Specific operation counts, not just "too slow"
•Alternative identification — Multiple viable approaches considered
•Decision confidence — Clear choice with justification
•Communication skills — Thinking out loud, seeking confirmation

Phrases That Signal Strong Elimination Skills:

"That's O(n²), and with n = 10⁵, that's 10¹⁰ operations—definitely too slow."
"I'm eliminating the recursive solution because the depth could be 10⁶, risking stack overflow."
"The values go up to 10⁹, so I can't use direct indexing—I'll need a hash map or coordinate compression."
"The memory limit is 256 MB, and an n × n matrix would be 400 MB—I need adjacency lists."
"Since this needs to handle updates, prefix sums alone won't work—I need a segment tree or similar."

Handling Follow-Up Eliminators:

Interviewers often follow up with: "What if the array is sorted?" or "What if memory is limited?"

These are elimination questions in disguise:

Sorted array → eliminate hash map (sorting was the expensive part)
Limited memory → eliminate auxiliary data structures
Multiple queries → eliminate solutions that don't preprocess

Elimination Builds Trust

When you correctly eliminate approaches, interviewers trust your final solution more. They know you've considered alternatives. Even if you struggle with implementation, demonstrated elimination skills show senior-level thinking.

The Elimination-First Workflow

Integrate elimination into your standard problem-solving workflow for maximum efficiency.

The Workflow:

Elimination-First Problem-Solving
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// STEP 1: Read constraints BEFORE reading the problem details
// Note: n = ?, m = ?, values = ?, memory = ?, time = ?
 
// STEP 2: Immediate complexity elimination
// Ask: What's the maximum viable complexity?
//      n <= 10^5 → need O(n log n) or better
//      -> ELIMINATE: all O(n²) approaches
 
// STEP 3: Read the problem
// Understand what's asked
 
// STEP 4: Structural elimination
// Ask: What structural constraints exist?
//      Is it a tree? Graph? Sorted? Static?
//      -> ELIMINATE: algorithms requiring structures we don't have
 
// STEP 5: Value-based elimination
// Ask: What are the value ranges?
//      a[i] <= 10^9 → ELIMINATE: value-indexed arrays
//      a[i] <= 100  → ENABLE: value-based DP
 
// STEP 6: Memory elimination
// Ask: What space can I afford?
//      256 MB, n = 10^5 → 2D array up to ~8000 x 8000
//      -> ELIMINATE: n x n matrix if n > 8000
 
// STEP 7: Generate solutions within surviving space
// Only consider algorithms that passed all elimination criteria
 
// STEP 8: Verify chosen solution
// Calculate exact complexity, confirm it passes
 
// STEP 9: Implement

The Decision Matrix:

After elimination, you often narrow down to 1-3 viable approaches. Create a mental decision matrix:

Approach	Time	Space	Implementation Difficulty	Verdict
Segment Tree	O(n log n) ✓	O(n) ✓	High	Viable
Mo's Algorithm	O(n √n) ✓	O(n) ✓	Medium	Viable
Brute Force	O(n²) ✗	O(1)	Low	Eliminated

If multiple approaches are viable, choose based on:

Implementation time/complexity
Your comfort with the algorithm
Room for optimization if tests are tight

The Elimination Advantage

Elimination-first solvers are faster not because they know more algorithms, but because they waste no mental energy on dead ends. In a 45-minute interview, eliminating bad approaches in the first 2 minutes leaves 43 minutes for viable solutions. That's a competitive advantage.

Summary: Mastering Constraint-Based Elimination

You've now completed the full toolkit for constraint-based algorithm selection. Let's consolidate the key principles from this module:

Module Key Takeaways

•Page 1 — Reading Constraints: Constraints encode solutions. Learn to extract maximum information from every constraint before solving.
•Page 2 — Estimating Complexity: Calculate operation budgets (10⁸/sec), derive maximum viable n for each complexity class, account for constants and language speed.
•Page 3 — Constraint Mappings: Use the reference table to immediately identify viable algorithms for any constraint range.
•Page 4 — Elimination: Aggressively eliminate infeasible approaches first. What you don't try saves more time than what you optimize.

The Elimination Checklist

•Time elimination: Calculate n × operations, eliminate complexities over 10⁸
•Space elimination: Calculate bytes needed, eliminate structures over memory limit
•Value elimination: Check value ranges, eliminate value-indexed approaches if values > 10⁶
•Structural elimination: Match algorithm requirements to input structure
•Algorithm family elimination: Eliminate specific algorithms based on problem characteristics

The Master Problem-Solving Loop:

1. Read constraints
2. Eliminate infeasible approaches
3. Identify viable complexity classes
4. Match algorithms to problem requirements
5. Choose the simplest viable solution
6. Verify complexity against budget
7. Implement with confidence

What's Next:

With constraint-based algorithm selection mastered, the next module explores Edge Cases & Testing Strategies—learning to identify the inputs that break solutions and systematically verify correctness.

You now possess one of the most valuable skills in algorithmic problem-solving: the ability to look at constraints and immediately know which algorithms to consider and which to reject. This skill compounds with experience; every problem you solve reinforces your constraint intuition.

Module Complete

Congratulations on completing Module 4: Constraint-Based Algorithm Selection. You've learned to read constraints as hidden solution hints, estimate required complexities, map constraints to algorithms, and eliminate infeasible approaches. These skills will serve you in every coding interview, competitive programming contest, and real-world engineering challenge you face.

Using Constraints to Eliminate Approaches

The Power of Elimination

What You Will Learn

The Elimination Mindset

Elimination is not about being pessimistic—it's about being efficient. Every approach you eliminate saves time that would have been wasted on:

Designing a solution that will fail
Implementing code that will TLE
Debugging performance issues that can't be fixed
Frustration from the cycle of hope and failure

The Cost of Not Eliminating:

Consider a developer who doesn't practice elimination. Facing a problem with n ≤ 10⁵:

First idea: nested loops → implements → TLE
Second idea: optimize with hash map → implements → still TLE (O(n²) with O(1) inner work is still O(n²))
Third idea: finally realizes n² is fundamentally impossible
Fourth idea: segment tree → finally works

Time wasted: potentially hours on approaches 1-3.

An elimination-first solver sees n ≤ 10⁵ and immediately knows:

NO nested loops over the full array
NO algorithms with O(n²) complexity
YES to O(n log n) structures if needed
MAYBE O(n √n) if nothing better exists

They skip directly to approach 4 or equivalent.

Elimination Before Exploration

The Complete Elimination Checklist

Use this systematic checklist when analyzing any problem. Work through each elimination category to narrow your solution space.

Step 1: Time Complexity Elimination

Based on primary constraint n:

n Range	Eliminate These Complexities
n > 25	O(2ⁿ), O(n!), O(n × 2ⁿ) — all exponential
n > 500	O(n³), O(n⁴) — cubic and higher
n > 10,000	O(n²), O(n² log n) — quadratic
n > 10⁶	O(n √n), O(n log² n) — sub-linear but super-log
n > 10⁷	O(n log n) — log factor eliminated
n > 10⁸	Anything that reads all input — need formula

Instant Eliminations by Constraint

•n > 10,000 → Eliminate: nested for-loops, O(n²) DP, all-pairs algorithms
•n > 10⁶ → Eliminate: balanced tree operations in tight loops, repeated sorting
•n > 10⁸ → Eliminate: reading all input, any algorithm with linear scan
•Values > 10⁹ → Eliminate: direct array indexing by value, value-based DP arrays
•Memory ≤ 64MB → Eliminate: large 2D arrays, storing full graph adjacency matrix for large n
•Multiple test cases → Eliminate: heavy preprocessing that can't be reused

Step 2: Space Complexity Elimination

Memory limits constrain data structures:

64 MB limit:
- Cannot store 10⁷ integers (40 MB for ints, but limited headroom)
- Cannot use adjacency matrix for graph with V > 4000
- 2D DP table limited to roughly 4000 × 4000

256 MB limit:
- Can store ~6 × 10⁷ integers
- Adjacency matrix up to ~8000 × 8000
- 2D DP up to ~8000 × 8000

1 GB limit:
- Can store ~2.5 × 10⁸ integers
- Most practical limits removed

Step 3: Structural Elimination

Problem structure eliminates algorithm categories:

Not a tree → Eliminate: tree DP, LCA queries, tree-specific traversals
Has cycles → Eliminate: topological sort, simple tree algorithms
Graph is dense (E ≈ V²) → Eliminate: sparse graph algorithms that assume E ≪ V²
Online queries → Eliminate: offline algorithms (Mo's), approaches requiring all queries upfront
No sorting allowed → Eliminate: sorting-dependent approaches

Common Elimination Scenarios

Let's work through realistic constraint sets and practice elimination thinking.

Scenario 1: Large Array with Queries

Constraints:
n ≤ 10⁵ (array size)
q ≤ 10⁵ (number of queries)
Time limit: 2 seconds

Elimination Analysis:

✗ O(n × q) = 10¹⁰ — ELIMINATED (100× over budget) ✗ O(n² + q) = 10¹⁰ — ELIMINATED ✗ Per-query O(n) with no preprocessing — ELIMINATED

✓ O(n + q log n) — Segment tree with build + queries ✓ O((n + q) √n) — Mo's algorithm for offline queries ✓ O(n log n + q) — Preprocessing + O(1) queries (prefix sums, sparse table)

Scenario 2: Small n, Complex Problem

Constraints:
n ≤ 15
m ≤ 100
Time limit: 1 second

Elimination Analysis:

✗ Polynomial algorithms that don't use n's smallness — likely not the intended solution

✓ O(2ⁿ × m) = 32768 × 100 = 3.3 × 10⁶ — acceptable ✓ O(n! × something small) — up to ~1.3 × 10¹² / something = depends on "something" ✓ Bitmask DP with m factor

Insight: n = 15 is screaming for exponential-in-n approach. Look for subset structure.

Scenario 3: Graph Problem

Constraints:
V ≤ 10⁵ (vertices)
E ≤ 2 × 10⁵ (edges)
Time limit: 2 seconds

Elimination Analysis:

✗ Floyd-Warshall O(V³) = 10¹⁵ — ELIMINATED ✗ Bellman-Ford O(V × E) = 2 × 10¹⁰ — ELIMINATED ✗ Adjacency matrix (V² space) — ELIMINATED (4 × 10¹⁰ bytes)

✓ Dijkstra O((V + E) log V) ≈ 5 × 10⁶ — works ✓ BFS O(V + E) ≈ 3 × 10⁵ — works ✓ DFS O(V + E) — works ✓ Adjacency list representation — required

Scenario 4: String Problem with Large Values

Constraints:
n ≤ 10⁵ (string length)
Characters: lowercase English letters (26)
Time limit: 1 second

Elimination Analysis:

✗ O(n²) substring enumeration — ELIMINATED ✗ O(n × 26ⁿ) anything — obviously eliminated ✗ Suffix tree/array with O(n²) construction — need efficient construction

✓ O(n × 26) = 2.6 × 10⁶ — alphabet-sized inner loop per character ✓ O(n log n) — sorting-based approaches ✓ O(n) with O(26) state — linear with bounded auxiliary

Insight: The 26-letter alphabet means O(n × 26) is essentially O(n). Look for character-frequency or per-character-type solutions.

Document Your Eliminations

Eliminating Specific Algorithm Families

Beyond complexity elimination, certain constraint patterns eliminate entire algorithm families regardless of their complexity.

Shortest Path Algorithm Elimination:

When to Eliminate Shortest Path Algorithms
Constraint/Scenario	Eliminate	Use Instead
V > 500	Floyd-Warshall (O(V³))	Dijkstra or Bellman-Ford per source
E > V, negative edges	Dijkstra (doesn't handle negatives)	Bellman-Ford
V × E > 10⁸, negative edges	Bellman-Ford (too slow)	SPFA or problem-specific approach
Unweighted graph	Dijkstra (overkill)	BFS (simpler, same complexity)
Single source needed	Floyd-Warshall (overkill)	Dijkstra from one source

Sorting Algorithm Elimination:

Constraint	Eliminate	Use Instead
Already sorted input	Any sorting (unnecessary overhead)	Direct processing
Values in [0, k] with k ≤ n	Comparison sorts O(n log n)	Counting sort O(n + k)
n > 10⁷	Any comparison sort (log factor hurts)	Counting/Radix if applicable
Need stable sort	Quick sort (unstable)	Merge sort
Memory constrained	Merge sort (O(n) extra space)	Heap sort (in-place)

Data Structure Elimination:

Constraint	Eliminate	Use Instead
n > 10⁷ with many operations	Hash map with high overhead	Direct array if values bounded
Need ordered iteration	Hash map / Hash set	BST / TreeSet / sorted vector
Need range queries + updates	Simple array (O(n) per query)	Segment tree, Fenwick tree
Static data, range queries	Segment tree (overkill for static)	Sparse table (simpler, O(1) query)
Values > 10⁹	Array indexed by value	Hash map or coordinate compression

Elimination Isn't Always Clear-Cut

Value-Based Elimination

The range of values (not sizes) creates its own elimination criteria. This is often overlooked but equally important.

Large Value Ranges (a[i] ≤ 10⁹):

Eliminated by Large Values

•Direct array indexing by value — Cannot allocate 10⁹-sized array
•Value-based DP states — dp[value] with value up to 10⁹ is impossible
•Counting sort — Requires array sized to value range
•Sieve of Eratosthenes up to max value — Only viable if max value ≤ 10⁷
•Iterating through all values — 10⁹ iterations is too slow

What to Use Instead:

Coordinate Compression — Map n distinct values to [0, n-1], then use value-indexed approaches on compressed values.
Hash Maps — O(1) amortized access for arbitrary keys. Higher constant factor but handles any value range.
Sorting + Binary Search — Sort values, then binary search for positions. O(log n) per lookup.
Value-Independent Algorithms — Many algorithms only compare values, never index by them. Sorting, segment trees with comparison, etc.

Small Value Ranges (a[i] ≤ 100):

Conversely, small value ranges enable approaches:

Coordinate Compression Example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// Problem: Count inversions where a[i] ≤ 10^9
// Cannot use value-indexed Fenwick tree directly
// Solution: Compress values to [0, n-1], then use Fenwick tree
 
function countInversions(arr: number[]): number {
    const n = arr.length;
    
    // Step 1: Coordinate compression
    const sorted = [...arr].sort((a, b) => a - b);
    const valueToRank = new Map<number, number>();
    let rank = 0;
    for (const val of sorted) {
        if (!valueToRank.has(val)) {
            valueToRank.set(val, rank++);
        }
    }
    
    // Step 2: Map original values to ranks
    const compressed = arr.map(v => valueToRank.get(v)!);
    
    // Step 3: Now use Fenwick tree indexed by compressed values
    // (Fenwick tree implementation omitted for brevity)
    // Count elements > current that appeared before
    
    // Values now in [0, n-1], Fenwick tree of size n is feasible
    // Original values up to 10^9 would require 10^9-sized tree!
    
    return countWithFenwick(compressed);
}
 
// Key insight: We only care about relative order, not absolute values
// Compression preserves relative order while enabling value-indexed structures

Memory-Based Elimination

Memory constraints eliminate algorithms independently of time complexity. An algorithm can be fast enough but still fail due to space requirements.

Memory Calculation Quick Reference:

1 int = 4 bytes
1 long long = 8 bytes
1 pointer = 8 bytes (64-bit)
1 object in Java/C# = ~16+ bytes overhead + fields

1 MB = 10^6 bytes ≈ 250,000 ints
64 MB ≈ 16 million ints
256 MB ≈ 64 million ints
1 GB ≈ 250 million ints

Memory Elimination Scenarios
Memory Limit	Maximum Viable	Eliminate
64 MB	~1.5 × 10⁷ ints, 2D: 4000 × 4000	Large graphs as matrix, full 2D DP for n > 4000
128 MB	~3 × 10⁷ ints, 2D: 5500 × 5500	n × n matrices for n > 5500
256 MB	~6 × 10⁷ ints, 2D: 8000 × 8000	Very large 2D structures
512 MB	~1.2 × 10⁸ ints	Only the most extreme cases

Common Memory Elimination Patterns:

1. Graph Representation:

Adjacency matrix: O(V²) space. For V = 10,000: 400 MB just for the matrix.
Solution: Adjacency list. O(V + E) space.

2. 2D DP Optimization:

Standard 2D DP: O(n × m) space.
If current row only depends on previous row: O(m) space with rolling array.

3. Recursion Stack:

Deep recursion can cause stack overflow before memory limit is hit.
Recursion depth > 10⁵ is risky, > 10⁶ often fails.
Solution: Convert to iterative or increase stack size (where allowed).

4. Object Overhead:

Each Java/C# object has 16-24 bytes overhead.
10⁷ trivial objects = 160-240 MB just for overhead.
Solution: Use primitive arrays instead of object arrays.

The Rolling Array Technique

Communicating Elimination in Interviews

In technical interviews, explicitly stating what you're eliminating and why demonstrates structured thinking and earns credit even before you solve the problem.

The Elimination Dialogue:

Interviewer: "Find all pairs in an array that sum to a target. The array can have up to 10 million elements."

Strong Candidate Response:

"Ten million elements means n = 10⁷. Let me think about complexity constraints first.

A brute-force approach checking all pairs would be O(n²), which is 10¹⁴ operations—way too slow. That's eliminated immediately.

I need O(n log n) or better. Sorting plus two pointers would give O(n log n)—that's about 2.3 × 10⁸ operations, borderline but likely acceptable.

Even better, using a hash set for O(1) lookups gives me O(n) overall—just 10⁷ operations, very safe.

I'll go with the hash set approach. Does that sound reasonable before I implement?"

What This Demonstrates

•Complexity awareness — Immediate recognition that n² is infeasible for n = 10⁷
•Quantitative reasoning — Specific operation counts, not just "too slow"
•Alternative identification — Multiple viable approaches considered
•Decision confidence — Clear choice with justification
•Communication skills — Thinking out loud, seeking confirmation

Phrases That Signal Strong Elimination Skills:

"That's O(n²), and with n = 10⁵, that's 10¹⁰ operations—definitely too slow."
"I'm eliminating the recursive solution because the depth could be 10⁶, risking stack overflow."
"The values go up to 10⁹, so I can't use direct indexing—I'll need a hash map or coordinate compression."
"The memory limit is 256 MB, and an n × n matrix would be 400 MB—I need adjacency lists."
"Since this needs to handle updates, prefix sums alone won't work—I need a segment tree or similar."

Handling Follow-Up Eliminators:

Interviewers often follow up with: "What if the array is sorted?" or "What if memory is limited?"

These are elimination questions in disguise:

Sorted array → eliminate hash map (sorting was the expensive part)
Limited memory → eliminate auxiliary data structures
Multiple queries → eliminate solutions that don't preprocess

Elimination Builds Trust

The Elimination-First Workflow

Integrate elimination into your standard problem-solving workflow for maximum efficiency.

The Workflow:

Elimination-First Problem-Solving
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// STEP 1: Read constraints BEFORE reading the problem details
// Note: n = ?, m = ?, values = ?, memory = ?, time = ?
 
// STEP 2: Immediate complexity elimination
// Ask: What's the maximum viable complexity?
//      n <= 10^5 → need O(n log n) or better
//      -> ELIMINATE: all O(n²) approaches
 
// STEP 3: Read the problem
// Understand what's asked
 
// STEP 4: Structural elimination
// Ask: What structural constraints exist?
//      Is it a tree? Graph? Sorted? Static?
//      -> ELIMINATE: algorithms requiring structures we don't have
 
// STEP 5: Value-based elimination
// Ask: What are the value ranges?
//      a[i] <= 10^9 → ELIMINATE: value-indexed arrays
//      a[i] <= 100  → ENABLE: value-based DP
 
// STEP 6: Memory elimination
// Ask: What space can I afford?
//      256 MB, n = 10^5 → 2D array up to ~8000 x 8000
//      -> ELIMINATE: n x n matrix if n > 8000
 
// STEP 7: Generate solutions within surviving space
// Only consider algorithms that passed all elimination criteria
 
// STEP 8: Verify chosen solution
// Calculate exact complexity, confirm it passes
 
// STEP 9: Implement

The Decision Matrix:

After elimination, you often narrow down to 1-3 viable approaches. Create a mental decision matrix:

Approach	Time	Space	Implementation Difficulty	Verdict
Segment Tree	O(n log n) ✓	O(n) ✓	High	Viable
Mo's Algorithm	O(n √n) ✓	O(n) ✓	Medium	Viable
Brute Force	O(n²) ✗	O(1)	Low	Eliminated

If multiple approaches are viable, choose based on:

Implementation time/complexity
Your comfort with the algorithm
Room for optimization if tests are tight

The Elimination Advantage

Summary: Mastering Constraint-Based Elimination

You've now completed the full toolkit for constraint-based algorithm selection. Let's consolidate the key principles from this module:

Module Key Takeaways

•Page 1 — Reading Constraints: Constraints encode solutions. Learn to extract maximum information from every constraint before solving.
•Page 2 — Estimating Complexity: Calculate operation budgets (10⁸/sec), derive maximum viable n for each complexity class, account for constants and language speed.
•Page 3 — Constraint Mappings: Use the reference table to immediately identify viable algorithms for any constraint range.
•Page 4 — Elimination: Aggressively eliminate infeasible approaches first. What you don't try saves more time than what you optimize.

The Elimination Checklist

•Time elimination: Calculate n × operations, eliminate complexities over 10⁸
•Space elimination: Calculate bytes needed, eliminate structures over memory limit
•Value elimination: Check value ranges, eliminate value-indexed approaches if values > 10⁶
•Structural elimination: Match algorithm requirements to input structure
•Algorithm family elimination: Eliminate specific algorithms based on problem characteristics

The Master Problem-Solving Loop:

1. Read constraints
2. Eliminate infeasible approaches
3. Identify viable complexity classes
4. Match algorithms to problem requirements
5. Choose the simplest viable solution
6. Verify complexity against budget
7. Implement with confidence

What's Next:

Module Complete