Pattern Guide
Constructive Algorithms
"Build a valid answer from constraints. Greedy construction, invariant maintenance."
Constructive algorithm problems ask you to produce an output (array, permutation, sequence) satisfying given constraints, rather than compute a value. Techniques: greedy construction (build left to right, always making the locally valid choice), invariant-based construction (maintain a property throughout), parity arguments, and reachability arguments. Often requires mathematical insight to see that a greedy construction always works.
Problems you can solve with this pattern
4 problems · click any to start solving
// Construct a permutation where |perm[i] - perm[i+1]| is in {1, n-1}
// The "wiggle" between 1 and n: arrange as [1, n, 2, n-1, 3, n-2, ...]
function constructPermutation(n) {
const result = [];
let lo = 1, hi = n;
while (lo <= hi) {
if (lo === hi) { result.push(lo); break; }
result.push(lo++, hi--); // alternate low and high
}
return result;
}
// Construct array with given prefix XOR — O(n)
function constructFromPrefixXor(pXor) {
const arr = [pXor[0]];
for (let i = 1; i < pXor.length; i++)
arr.push(pXor[i-1] ^ pXor[i]);
return arr;
}Constructive problems: "does there exist X satisfying Y, and if so, output it." Strategy: find invariant that must hold (necessary condition). If invariant satisfied, construct greedily. If construction always works when invariant holds, you've found necessary and sufficient conditions. Common invariants: parity (sum must be even), reachability (enough elements to fill positions), balance (equal counts of two types).
// Construct a permutation where |perm[i] - perm[i+1]| is in {1, n-1}
// The "wiggle" between 1 and n: arrange as [1, n, 2, n-1, 3, n-2, ...]
function constructPermutation(n) {
const result = [];
let lo = 1, hi = n;
while (lo <= hi) {
if (lo === hi) { result.push(lo); break; }
result.push(lo++, hi--); // alternate low and high
}
return result;
}
// Construct array with given prefix XOR — O(n)
function constructFromPrefixXor(pXor) {
const arr = [pXor[0]];
for (let i = 1; i < pXor.length; i++)
arr.push(pXor[i-1] ^ pXor[i]);
return arr;
}1. Find necessary condition (invariant that must hold)
2. Verify it's also sufficient (if condition holds, construction exists)
3. Build greedily while maintaining invariant
4. Prove greedy choice is safe (exchange argument or induction)
Common constructions:
- Interleave sorted halves for wiggle/alternating patterns
- Mirror first half for palindromes
- Place elements at parity-specific indices for sign-alternating
- Assign greedily to "most needy" slot (greedy + priority queue)