CodeWithYash

Foundation · Module 1 · Lesson 6

Problem-solving workflow

Examples, constraints, brute force, invariants, and optimization.

15–25 min readLesson 6 of 123

Lesson 6 of 123

1d streak

Detailed theory

A reliable workflow turns an ambiguous prompt into a correct algorithm: clarify the contract, use constraints to set a budget, establish a brute-force baseline, identify repeated work, and prove the optimized invariant.

By the end, you can

  • Translate constraints into a practical complexity target.
  • Use brute force as a correctness model.
  • Optimize by removing a named source of repeated work.

Vocabulary

Definitions with concrete meaning

Contract

The exact input, output, mutation rules, and behavior for edge cases.

Example: For Two Sum: return indices, use two distinct positions, and decide whether one answer is guaranteed.

Constraint budget

A rough upper bound on operations and memory implied by input limits.

Example: n = 100,000 usually rules out Θ(n²) work.

Brute-force baseline

The simplest clearly correct method used to expose repeated work.

Example: Check every pair for Two Sum in Θ(n²) time.

Invariant

A statement that remains true before and after every algorithm step.

Example: Before processing a[i], the map contains exactly the earlier values and their indices.

Rules to apply

  1. 1Restate the problem with one small example before choosing a technique.
  2. 2Treat constraints as design information, not as decoration.
  3. 3Write brute force and derive its cost before optimizing.
  4. 4Name the repeated work or exploitable property that enables each optimization.
  5. 5Prove initialization, maintenance, termination, and edge-case behavior.
  6. 6Test the smallest inputs, duplicates, no answer, extreme values, and worst-shaped data.

Worked example 1

Two Sum: from pairs to complements

Return two distinct indices whose values sum to target.

seen = map()
for i = 0 to n - 1:
  need = target - a[i]
  if need in seen: return [seen[need], i]
  seen[a[i]] = i
  1. 1

    Clarify

    Return indices; positions must differ; duplicates are allowed.

  2. 2

    Baseline

    Check every i < j pair: Θ(n²) time and Θ(1) auxiliary space.

  3. 3

    Find repeated work

    For each value, we repeatedly scan earlier values looking for one complement.

  4. 4

    Store searchable history

    A hash map answers “have we seen target − a[i]?” in expected Θ(1) time.

  5. 5

    Prove the invariant

    Check before inserting the current value, so any found complement comes from a distinct earlier index.

Expected Θ(n) time and Θ(n) auxiliary space, trading memory for speed.

Worked example 2

Use constraints to reject an approach

n ≤ 200,000 and the time limit suggests roughly tens of millions of simple operations.

  1. 1

    Estimate quadratic work

    n² = 40,000,000,000 operations—far beyond the likely budget.

  2. 2

    Estimate n log n

    n log₂n is about 3.5 million comparison-scale steps.

  3. 3

    Set a target

    Look for Θ(n) or Θ(n log n), then verify constants and memory.

Constraint analysis narrows the search, but it does not prove correctness; the invariant still does.

Comparison table

Rough constraint guide

These are interview-style heuristics, not machine-independent laws. Language, constants, and time limits matter.

Largest nOften feasiblePatterns to considerBe cautious with
≈ 20Θ(2ⁿ)Backtracking, subset DPΘ(n!)
≈ 200Θ(n³)Dense DP, Floyd–WarshallLarge constants
≈ 2,000Θ(n²)Pair DP, all pairsHeavy inner work
≈ 100,000Θ(n log n)Sorting, heaps, divide-and-conquerΘ(n²)
≈ 1,000,000Θ(n)Scanning, counting, two pointersLarge memory per item

Check your understanding

1Why write brute force if it will be too slow?

It establishes correctness, exposes repeated work, and provides a test oracle for small random inputs.

2Does a matching complexity budget prove an algorithm is suitable?

No. It must also be correct, fit memory, and account for constants and input shape.

3What are the three parts of a loop-invariant proof?

Initialization before the loop, maintenance after each iteration, and termination implying the result.

Cost Model

Complexity & Trade-offs

Two Sum — all pairs
Θ(n²)
Θ(1)
Checks n(n−1)/2 candidate pairs.
Two Sum — hash map
Expected Θ(n)
Θ(n)
Stores earlier values to remove repeated complement searches.
Two Sum — sort + pointers
Θ(n log n)
Depends on index storage
Ordering enables a monotonic two-pointer scan but original indices must be preserved.

When to use it

  • Any interview, contest, or production algorithm task.
  • Choosing techniques from constraints instead of keywords alone.
  • Explaining why an optimization is correct and what trade-off it introduces.

Common mistakes

  • Jumping to a memorized pattern before clarifying the contract.
  • Optimizing without naming the repeated work being removed.
  • Giving time complexity without auxiliary space, assumptions, or worst-case behavior.

Practice prompts

  • Apply the workflow to “longest substring without repeating characters.”
  • Derive a budget for n = 10⁵, then compare three candidate approaches.
  • Use brute force as an oracle to test an optimized solution on random small inputs.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.