Pattern Reference
Constructive Algorithms
"Build a valid solution step by step. Grid construction, permutation construction, array construction."
Loading...
Deep Dive Tutorial
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).
Constructive pattern: build valid permutation
// 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;
}Worked Problems
landmark
Constructive algorithm checklist:
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)
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)