234: Problem-Solving Patterns: Invariants, Constraints, Reduction, and Counterexamples

Learning outcomes

By the end of this lesson, you can:

explain and apply how to clarify the contract in a realistic implementation;
explain and apply how to start with brute force in a realistic implementation;
explain and apply how to identify invariants in a realistic implementation;
explain and apply reduction in a realistic implementation;
explain and apply counterexamples in a realistic implementation.

Prerequisites and retrieval

This lesson assumes the 01–06 foundation and the preceding lessons in this module. Before you begin, retrieve one concrete example from an earlier project in which one of these concerns appeared. The point is not to memorize a set of labels. It is to make a defensible choice in both an interview-sized problem and a production data-processing problem, reasoning from the constraints instead of reaching for a memorized template.

Terminology

Clarify the contract: Confirm the input size, mutability, duplicate behavior, ordering, numeric range, output requirements, and whether the caller needs one solution or all solutions.
Start with brute force: Describe a correct baseline and its complexity before optimizing it.
Identify invariants: State what remains true after each pointer move, stack operation, traversal step, or dynamic-programming transition.
Reduction: Map a new problem to a known primitive such as interval scheduling, shortest path, connectivity, range query, top-K selection, or substring frequency.
Counterexamples: Try to break your own approach with empty or minimum input, duplicates, sorted or reverse-sorted data, negative values, overflow, disconnected graphs, and adversarial ordering.
Complexity narrative: Explain why each element, state, or edge is processed a bounded number of times. Include the memory costs of sorting, heaps, and hash-based structures instead of quoting a memorized complexity in isolation.

Mental model

Treat Problem-Solving Patterns: Invariants, Constraints, Reduction, and Counterexamples as a design problem with observable inputs, outputs, invariants, and failure modes. Strong DSA work is not just pattern recognition. It is a repeatable process: turn constraints into candidate data structures, then establish correctness before writing the implementation. A strong implementation makes its assumptions visible, narrows uncertainty at boundaries, and leaves enough evidence—tests, types, constraints, metrics, or diagrams—to show why the design is safe.

A useful sequence for both interviews and production work is:

requirement -> constraints -> model -> implementation -> failure analysis -> verification

Do not move straight from a requirement to a library call. First identify what must remain true as the algorithm runs. Then choose the mechanism that maintains that property and makes it possible to verify.

Deep dive

1. Clarify the contract

Start by confirming the input size, mutability, duplicate behavior, ordering, numeric range, output requirements, and whether one solution or every solution is required. These details are not paperwork; a hidden assumption in any one of them can change the appropriate algorithm or data structure.

Decision rule: Use clarify the contract deliberately when it makes the contract or its invariant easier to state and prove. If a shortcut merely reduces typing while hiding an assumption, keep the design explicit instead.

2. Start with brute force

Describe a correct baseline and give its complexity before trying to improve it. A brute-force version provides a reference for correctness and exposes the repeated work that hashing, prefix state, sorting, dynamic programming, or another technique might eliminate.

Decision rule: Use start with brute force deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design.

3. Identify invariants

State the property that remains true after each pointer move, stack operation, traversal step, or DP transition. That invariant is the link between the code and the correctness argument. Without it, an implementation can look plausible while its next move quietly discards a required case.

Decision rule: Use identify invariants deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design.

4. Reduction

Look for a known primitive behind the surface wording of a new problem: interval scheduling, shortest path, connectivity, range query, top-K selection, or substring frequency. Reduction is useful only when the new problem satisfies the primitive's preconditions. Do not force a familiar pattern onto a problem whose constraints do not support it.

Decision rule: Use reduction deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design.

5. Counterexamples

Try to break the approach before someone else does. Exercise it with empty or minimum input, duplicates, sorted and reverse-sorted data, negative values, overflow, disconnected graphs, and adversarial ordering. A counterexample is especially valuable when it identifies the exact assumption that the algorithm was relying on.

Decision rule: Use counterexamples deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design.

6. Complexity narrative

Explain why each element, state, or edge is processed only a bounded number of times, and account for the memory used by sorting, heaps, and hash tables. A useful complexity explanation describes the work the implementation actually performs; it is more reliable than reciting a familiar Big-O expression without connecting it to the loops and data structures.

Decision rule: Use complexity narrative deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design.

Worked example

Consider both an interview-sized problem and a production data-processing problem. In each case, reason from constraints rather than memorizing a template. Begin by writing the requirement in one sentence, listing the input and output contracts, and assigning each possible failure mode to the concept that helps you address it. The useful separation is at the boundaries: parsing and validation belong at the boundary; domain rules belong in the domain or service layer; persistence rules belong in the database or repository; presentation rules belong in the client. Mixing these concerns can make a happy-path demo look shorter, but it makes edge cases much harder to locate and explain.

function solve(values: readonly number[]): number {
  let answer = 0;
  // State the invariant before choosing the data structure.
  for (const value of values) {
    answer = Math.max(answer, value);
  }
  return answer;
}

There is a subtle contract issue in this deliberately small example: returning 0 for an empty array is a policy choice, not a fact supplied by the type. If the requirement allows only non-empty input, validate that at the boundary or encode the precondition in the API. If an empty input is valid, decide whether 0, undefined, or an error is the correct result. The loop's invariant is that after processing each value, answer is the greatest value seen so far under the function's chosen initialization rule.

Walk through at least four cases: the normal path; an empty or missing value; a duplicate, retry, or concurrent path where that scenario is relevant; and a dependency failure. For each case, state which layer detects the problem and what the caller observes. That is the level of explanation expected in a senior code review or technical interview: not just which line runs, but which contract and ownership boundary make the behavior correct.

Production perspective

Production correctness is broader than “the code works on my machine.” Ask how the design behaves during deploys, retries, partial failures, stale clients, concurrent requests, malformed data, schema changes, and high-cardinality workloads. Prefer explicit contracts, bounded resource usage, structured errors, and measurable behavior. Optimize only after evidence identifies the bottleneck or risk.

When an external dependency is involved, define both a timeout and a cancellation strategy. When persistence is involved, define the transaction and consistency expectations. When the feature exposes user-visible state, define loading, empty, error, stale, and success states. When security is involved, assume the client can be modified and all network input is untrusted.

Guided lab

Pick five unseen medium-difficulty problems. For each one, spend the first ten minutes on constraints, a brute-force approach, repeated work, the invariant, and test cases before writing code. Keep the reasoning notes; they are part of the exercise, not discarded scratch work.

Complete the lab with this discipline:

Write the requirement and two non-requirements.
List the input, output, and error contracts before implementing anything.
Implement the smallest correct vertical slice.
Add at least one invalid-input test and one edge-case test.
Instrument or inspect the behavior instead of guessing about it.
Refactor one hidden assumption into an explicit type, constraint, function, or configuration value.
Explain one alternative design and why you did not choose it.
Record a short “what would break at 10× scale?” note.

Edge cases and failure modes

Clarify the contract: Test absence, malformed input, duplicates, ordering or concurrency where applicable, and behavior at the smallest and largest credible sizes.
Start with brute force: Test absence, malformed input, duplicates, ordering or concurrency where applicable, and behavior at the smallest and largest credible sizes.
Identify invariants: Test absence, malformed input, duplicates, ordering or concurrency where applicable, and behavior at the smallest and largest credible sizes.
Reduction: Test absence, malformed input, duplicates, ordering or concurrency where applicable, and behavior at the smallest and largest credible sizes.
Counterexamples: Test absence, malformed input, duplicates, ordering or concurrency where applicable, and behavior at the smallest and largest credible sizes.

Common mistakes and debugging

Solving the example instead of the requirement: a copied pattern can be syntactically correct and still be architecturally wrong.
Hiding uncertainty with assertions, broad exception handlers, permissive schemas, or “temporary” any values.
Testing only the happy path, which means discovering the actual contract only after integration.
Optimizing before measuring, or choosing a scalable mechanism without a scale requirement.
Treating client-side behavior as a substitute for server-side authorization, validation, or persistence guarantees.

For debugging, reproduce the smallest failing case first. Inspect the actual value or execution plan, trace the boundary where the invariant first becomes false, and fix the layer that owns the problem rather than adding a downstream patch. The first false invariant is usually more useful than the final error message.

Interview questions

What problem does Clarify the contract solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Start with brute force solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Identify invariants solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Reduction solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Counterexamples solve, and what trade-off or failure mode would make you choose a different approach?

Checkpoint

Without notes, explain Problem-Solving Patterns: Invariants, Constraints, Reduction, and Counterexamples to another developer in five minutes. Include one invariant, one edge case, one production failure mode, and one alternative design. Then implement a small example without copying the lesson's code.

Mastery checklist

I can define the core terms precisely.
I can choose a design from requirements instead of habit.
I can implement and test the normal path and edge cases.
I can explain the runtime, storage, or complexity cost.
I can identify which layer owns validation, errors, and recovery.
I can compare at least two reasonable alternatives.
I can explain how the design changes at larger scale or under stricter reliability requirements.