Fix One Variable Technique

Fix One Variable is a practical strategy for problems that involve choosing multiple elements (like pairs, triples, or parameters) to optimize an objective or satisfy a condition. Instead of naively checking all combinations, we deliberately enumerate one dimension (one variable) and leverage structure—such as sorted order, prefix/suffix aggregates, two pointers, or a data structure—to efficiently find the best partner(s) in the remaining dimensions. For example, to find a pair (i, j) maximizing a[j] − a[i] with i < j, you can scan from left to right while tracking the minimum a[i] seen so far; when considering position j, the best i is simply that minimum. This transforms the quadratic approach into a linear pass. The method generalizes to more complex tasks like three-sum (fix one index, use two pointers for the other two) and parametric optimization (fix a candidate answer and test feasibility via a monotone predicate, then binary search the best value). The recurring theme is dimension reduction: reduce a k-variable search to repeated (k−1)-variable optimizations that are fast, often after a one-time preprocessing step like sorting. When carefully applied, this yields substantial speedups while preserving correctness.

Imagine shopping for an outfit consisting of a shirt and pants. Instead of trying on every shirt–pants pair, you could fix a shirt you like and then quickly check which pants match it best. If you repeat this with each shirt but use a trick—like arranging pants by color or size so you can jump to the best match—you avoid trying every pair. That’s the Fix One Variable idea: control one choice, and exploit structure to handle the rest efficiently. In a number line analogy, suppose you want the pair of points (i, j) with i < j that maximizes a[j] − a[i]. If you stand at position j and ask, "Which earlier point gives me the biggest gain?", the answer is always the smallest earlier value. So you just carry along the smallest value as you walk forward—no need to re-check all previous points. In 3-variable scenarios like three-sum, you start by fixing one element; now finding two other elements to hit a target becomes simpler when the array is sorted, because the sum moves predictably with pointer motions. In parametric problems—like placing Wi‑Fi routers to maximize minimum coverage—you can fix a candidate distance d and ask, "Is it possible to place routers at least d apart?" If the answer is yes for d, it will remain yes for smaller distances; this monotonicity lets you zoom in with binary search instead of guessing blindly. Across these examples, the core intuition is: lock one knob, and the rest become predictable enough to optimize quickly.

Use this technique when the brute-force space grows as pairs, triples, or higher tuples, but the problem has structure after one choice is fixed. Common triggers include: (1) Pair optimization with an ordering constraint, like maximizing a[j] − a[i] for i < j—tracking a prefix minimum or suffix maximum transforms the problem into a linear scan. (2) Sum problems (two-sum, three-sum) where sorting enables predictable pointer movement; by fixing one index, you can often reduce O(n^3) to O(n^2). (3) 2D or geometric sweeping, where fixing one coordinate (e.g., x) reduces the problem to managing a set ordered by the other coordinate (e.g., y) using a balanced BST or window. (4) Parametric optimization with a monotone feasibility predicate—fix a candidate answer and run a greedy or two-pointer check; binary search refines the parameter to optimality, yielding O(C(n) \log R). (5) Problems that decompose additively or have separable constraints such that, given a fixed part, the best complement can be computed from a precomputed summary (prefix sums, segment trees, Fenwick trees). Avoid the technique when fixing one variable doesn’t simplify the remainder—e.g., when no monotonicity, ordering, or efficient oracle exists; then the per-fixed cost remains large and no real savings occur.