Formal Correctness: Proving Your Algorithm

Concepts: pyInvariantProof, pyProofByContradiction

At the L5/L6 level, the interviewer will ask you to prove your algorithm is correct. Not just run through examples. Prove it. This is the skill that separates senior from mid-level. There are two proof techniques that cover every two-pointer problem: invariant-based reasoning and proof by contradiction. You need to be comfortable with both. Invariant-Based Reasoning An invariant is a property that is true at every step of the algorithm. For Two Sum on sorted input, the invariant is: 'the answer, if it exists, is always between the two pointers.' You prove this by showing that each pointer movement preserves the invariant. Moving left right when the sum is too small: the pair (left, right) has a sum less than target. Because the array is sorted, the pair (left, any right' <= right) also has