Problem Constraints & Algorithmic Trade-offs

Every coding problem—whether in a competitive programming contest, a technical interview, or a real production system—comes with constraints. And here's a secret that separates novices from engineers:

Constraints aren't obstacles. They're clues.

A beginner looks at "n ≤ 10⁶" and feels limited. An engineer looks at the same constraint and immediately knows: "I need O(n log n) or better; O(n²) won't work here." The constraint tells you what algorithms are viable before you write a single line of code.

This module teaches you to read constraints like an engineer—extracting maximum information to guide your algorithmic decisions. By the end, you'll never dive into implementation without first asking: "What do the constraints tell me?"

Almost every computational problem operates under three fundamental constraints. Understanding each, and how they interact, is essential for algorithm selection.

1. Input Size Constraints

These specify the scale of data your algorithm must handle:

• "n ≤ 10⁵" — Array can have up to 100,000 elements
• "1 ≤ n ≤ 10⁶" — Up to 1 million elements
• "1 ≤ n, m ≤ 10³" — Two dimensions, each up to 1,000
• "String length ≤ 10⁴" — Up to 10,000 characters
• "Number of queries: Q ≤ 10⁵" — 100,000 operations to process

Input size is the most important constraint because it directly determines which complexity classes are feasible. The relationship is mathematical: if n = 10⁶ and your algorithm is O(n²), that's 10¹² operations—typically far too many.

2. Time Limit Constraints

These specify how quickly your solution must complete:

• "Time limit: 1 second" — Most common in competitive programming
• "Time limit: 2 seconds" — Slightly relaxed
• "Response time: < 100ms" — Real-time systems
• "Request must complete within 30 seconds" — Web services
• "Daily batch job, 8-hour window" — Overnight processing

Time limits translate to operation counts through a rule of thumb:

Modern computers execute roughly 10⁸ to 10⁹ simple operations per second.

This means:

• 1 second ≈ 10⁸ operations budget
• 2 seconds ≈ 2 × 10⁸ operations budget
• 100ms ≈ 10⁷ operations budget

These are approximations—actual speed depends on hardware, operation complexity, and memory access patterns—but they're accurate enough for algorithm selection.

3. Memory Limit Constraints

These specify how much RAM your solution may use:

• "Memory limit: 256 MB" — Typical competitive programming
• "Memory limit: 512 MB" — More generous
• "Must fit in L3 cache: 8 MB" — Performance-critical systems
• "Device has 128 MB RAM" — Embedded systems
• "No additional memory beyond input" — In-place algorithms required

Memory translates to element counts:

• 1 integer (4 bytes) → 256 MB ≈ 64 million integers
• 1 long/double (8 bytes) → 256 MB ≈ 32 million values
• 1 boolean (1 byte typically) → 256 MB ≈ 256 million booleans
• n×n matrix of integers → 256 MB ≈ n ≤ 8,000 for 2D array

Memory constraints often eliminate algorithms that require large auxiliary data structures.

This is the most important mental model in this entire module. Memorize it. Given an input size n and a time limit (usually ~1 second), there's a maximum complexity that's feasible:

The Constraint-Complexity Table:

How to use this table:

1. Read the constraint: "Array size n ≤ 10⁵"
2. Find target row: n ≤ 100,000 → O(n log n) is safe
3. Eliminate algorithms: O(n²) comparison sort? Too slow.
4. Select viable approaches: Merge sort, binary search-based solutions, divide and conquer

Example reasoning:

Problem: "Given an array of n integers (n ≤ 10⁵), find if any two elements sum to a target."

• n ≤ 10⁵ → need O(n log n) or better
• Brute force O(n²)? 10¹⁰ operations → too slow ❌
• Sort + two pointers O(n log n)? ~1.7M operations → fine ✓
• Hash set O(n)? ~10⁵ operations → even better ✓

The constraint eliminated the naive approach before you'd waste time implementing it.

The 10⁸ operations per second rule lets you translate time limits into operation budgets:

The calculation:

Operation Budget = Time Limit (seconds) × 10⁸

Examples:

• 1 second limit → 10⁸ operations
• 2 second limit → 2 × 10⁸ operations
• 0.5 second limit → 5 × 10⁷ operations
• 5 second limit → 5 × 10⁸ operations

Then check if your algorithm fits:

Given n = 10⁶ and time limit = 2 seconds:

• Budget = 2 × 10⁸ operations
• O(n) → 10⁶ operations → ✓ plenty of room
• O(n log n) → 10⁶ × 20 ≈ 2 × 10⁷ → ✓ comfortable
• O(n²) → 10¹² → ❌ 5000x over budget
• O(n sqrt(n)) → 10⁶ × 10³ = 10⁹ → ❌ 5x over budget (risky)

Safety margins:

The 10⁸ rule is an approximation. Account for:

• Constant factors: An O(n) algorithm might do 10 operations per element, effectively 10n
• Memory access: Cache misses can slow execution 10-100x
• Complex operations: Division, modulo, function calls are slower than addition
• Input/output: Reading large inputs can consume a significant portion of time

Conservative approach: Plan for 10⁷ to 5 × 10⁷ for safety, especially in competitive programming where time limits are tight.

Memory limits are often overlooked by beginners, but they're just as important as time limits. Understanding memory helps you:

1. Avoid "Memory Limit Exceeded" errors
2. Choose between O(n²) space and O(n) space algorithms
3. Decide when in-place algorithms are required
4. Understand when precomputation is feasible

Memory calculation basics:

Common memory scenarios:

Scenario 1: Linear array

• n = 10⁶ integers (4 bytes each)
• Memory = 4 × 10⁶ = 4 MB ✓ (easily fits in 256 MB)

Scenario 2: 2D matrix

• n × n matrix where n = 10,000
• Memory = 4 × 10,000 × 10,000 = 400 MB ❌ (exceeds 256 MB limit)
• For n × n in 256 MB: n ≤ √(64M) ≈ 8,000

Scenario 3: Adjacency matrix for graph

• n = 10,000 nodes, dense graph
• Memory = 4 × 10,000 × 10,000 = 400 MB ❌
• Need adjacency list instead: O(n + edges) space

Scenario 4: Memoization table

• DP with states n × m where n, m = 10,000
• Memory = 4 × 10⁸ = 400 MB ❌
• May need space optimization (keeping only recent rows)

Hidden memory costs:

Languages have overhead beyond raw data:

• Object headers: Java objects have 12-16 bytes overhead each
• Pointer indirection: ArrayList<Integer> uses 20+ bytes per integer vs 4 for int[]
• Garbage collection: GC needs headroom; 256 MB limit may effectively be 180 MB usable
• Recursion stack: Each recursive call uses stack space (~100-1000 bytes per frame)
• Hash table overhead: Typically 20-50% space overhead for load factor < 1

In competitive programming, prefer primitive arrays. In production, balance memory with code clarity and maintainability.

Real problems often have multiple interacting constraints. Reading them carefully reveals exactly what's feasible.

Example 1: Array with queries

Given an array of n ≤ 10⁵ elements and Q ≤ 10⁵ queries, answer each query in time.

Analysis:

• Total operations = n (preprocessing) + Q × (query time)
• If query is O(n): total = 10⁵ + 10⁵ × 10⁵ = 10¹⁰ ❌
• If query is O(log n): total = 10⁵ + 10⁵ × 17 ≈ 1.8 × 10⁶ ✓
• If query is O(1) with O(n) preprocessing: total = 10⁵ + 10⁵ = 2 × 10⁵ ✓✓

The constraint pattern (large n AND large Q) signals: "You need O(log n) or O(1) per query."

Example 2: Graph problem

Given a graph with n ≤ 1000 nodes and m ≤ 100,000 edges...

• n² = 10⁶ — O(n²) algorithms are fine
• But O(m × n) = 10⁸ — borderline, might TLE
• Adjacency matrix? n² = 10⁶ entries × 4 bytes = 4 MB ✓
• Or adjacency list using O(n + m) ≈ 0.5 MB ✓

Both representations are feasible here because n is moderate.

Example 3: Heavy constraint disparity

Given n ≤ 100,000 integers, perform up to m ≤ 10 operations.

Key insight: m is tiny! Even O(n) per operation is fine:

• Total = 10 × 10⁵ = 10⁶ ✓

Don't over-engineer. When one dimension is small, simpler algorithms suffice.

Constraints look different depending on where you encounter them. Learn to recognize them in each context.

Competitive Programming:

Explicit and precise:

Constraints:
1 ≤ n ≤ 10⁵
1 ≤ m ≤ 2 × 10⁵
Time limit: 1 second
Memory limit: 256 MB

These constraints are intentionally set to allow specific algorithm classes. Problem setters calibrate limits so that O(n log n) passes and O(n²) fails. Read them as hints!

Technical Interviews:

Usually conversational:

• Interviewer: "Assume the array has up to 10 million elements."
• Hidden constraint: You need O(n) or O(n log n)
• Interviewer: "This function is called thousands of times per second."
• Hidden constraint: Amortize expensive work; optimize the hot path

Always ask clarifying questions:

• "What's the expected input size?"
• "What's the acceptable latency?"
• "Is memory a concern?"
• "Is this called once or repeatedly?"

These questions show engineering maturity. Interviewers expect and appreciate them.

Real-World Production:

Constraints are discovered, not given:

• "Our database has 50 million user records."
• "The API must respond within 200ms."
• "We have 4 GB of memory available per container."
• "The batch job must complete in 4 hours."
• "We process 10,000 requests per second."

Production constraints often include:

• Concurrency: Multiple simultaneous requests share resources
• Durability: Operations must survive crashes
• Consistency: Distributed system constraints
• Cost: Compute/storage costs real money

The analytical skills transfer directly—you're still mapping resources to algorithm viability.

Let's practice translating constraints into algorithm requirements. For each scenario, determine which algorithms are viable.

Exercise 1:

n ≤ 10⁵, time limit 1 second. Find pair summing to target.

• O(n²) brute force: 10¹⁰ operations ❌ (100x over budget)
• O(n log n) sort + two pointers: ~2 × 10⁶ ✓
• O(n) hash set: ~10⁵ ✓ (optimal)

Exercise 2:

n ≤ 3,000, time limit 2 seconds. Find longest increasing subsequence.

• O(n²) DP: 9 × 10⁶ operations ✓ (fits comfortably)
• O(n log n) binary search DP: ~5 × 10⁴ ✓ (overkill but works)

N is small enough that O(n²) is fine here!

Exercise 3:

n ≤ 20, find subset with maximum sum ≤ target.

• O(2ⁿ) enumerate all subsets: 2²⁰ ≈ 10⁶ ✓ (small n means exponential is viable)
• Meet in the middle: 2 × 2¹⁰ = 2 × 10³ ✓ (even better)

Exercise 4:

n × m grid where n, m ≤ 10,000. Find shortest path.

• Grid size: 10⁸ cells
• BFS is O(V + E) = O(n × m) = 10⁸ operations — borderline ⚠️
• Memory for grid: 10⁸ bytes = 100 MB — might be okay, check limit
• If n, m ≤ 1,000: 10⁶ cells, perfectly fine ✓

Exercise 5:

Q ≤ 10⁵ queries on array of n ≤ 10⁵ elements. Each query: range sum.

• O(n) per query: 10¹⁰ total ❌
• O(1) per query with prefix sums: O(n) preprocess + O(Q) queries = 2 × 10⁵ ✓

This constraint pattern (large n, large Q) signals: precompute!

We've established the foundation of constraint-based thinking. Constraints aren't limitations—they're the problem statement telling you which algorithms can work.

What's next:

Now that you can read constraints, we'll explore how they guide algorithm selection. The next page examines how to use constraints to narrow down algorithm choices systematically—eliminating infeasible options and identifying viable approaches before writing any code.