An algorithm begins with a precise statement of the problem. The goal is to define the task so clearly that both correctness and complexity follow from the definition. Ambiguity at this stage propagates into proofs, implementations, and tests.
A problem statement consists of four parts: input, output, constraints, and guarantees.
Input specifies the structure and domain of data. You describe types, sizes, ordering, and any preconditions. For example, an input may be an array of integers of length (n), a directed graph with (m) edges, or a string over a fixed alphabet.
Output defines the required result. It must be unambiguous and verifiable. If multiple valid outputs exist, you must state the acceptance condition. For example, returning any shortest path, or returning the lexicographically smallest solution.
Constraints bound the problem. They include limits on size, value ranges, and time or space expectations. Constraints guide the choice of algorithm. A method that works for (n \le 10^3) may fail for (n \le 10^6).
Guarantees describe assumptions that simplify reasoning. Examples include sorted input, absence of negative cycles, or connectivity of a graph. If guarantees are absent, the algorithm must handle all cases explicitly.
Canonical Form
A useful pattern is to normalize every problem into a standard template:
| Component | Description |
|---|---|
| Input | Typed objects with size parameters |
| Output | Required result with acceptance criteria |
| Constraints | Bounds on size and values |
| Objective | What must be optimized or satisfied |
This normalization reduces variation and makes patterns easier to recognize.
Example
Problem: Given an array of integers, find the maximum subarray sum.
Input: Array (A) of length (n), where (A[i] \in \mathbb{Z})
Output: Maximum value of (\sum_{i=l}^{r} A[i]) for some (0 \le l \le r < n)
Constraints: (1 \le n \le 10^6), values bounded by machine integers
Guarantees: None
Validity Conditions
A well-formed problem satisfies the following:
- Every valid input produces at least one valid output
- The output can be checked efficiently
- Constraints are sufficient to choose an approach
- Edge cases are covered by the specification
If any of these fail, the problem statement is incomplete.
Edge Case Encoding
Edge cases should be part of the definition, not added later:
- Empty input
- Single element
- All elements equal
- Extreme values
- Degenerate structures (e.g., disconnected graph)
Explicit inclusion prevents hidden assumptions.
Reduction Readiness
A strong problem statement supports reduction. You should be able to map the problem to known forms such as:
- Search
- Optimization
- Decision
- Counting
For example, optimization problems can often be reframed as decision problems using a predicate and binary search.
Checklist
Before implementing, verify:
- Input is fully typed and bounded
- Output is uniquely defined or clearly flexible
- Constraints match intended complexity
- Edge cases are explicit
- Objective is formal
Takeaway
A precise problem statement acts as a specification, a proof target, and a testing oracle. It defines what correctness means and constrains how algorithms can be designed. Every efficient solution begins with a well-structured problem.