Loading section...

3Sum: Fix One, Scan Two

Concepts: py3Sum, pyFixAndScan

3Sum is the single most asked medium-difficulty two-pointer problem in technical interviews. Given an array of integers, find all unique triplets that sum to zero. The naive approach tries every triple: O(n^3). The optimized approach sorts the array, fixes one element, and uses two pointers to find the remaining pair: O(n^2). This is a reduction technique: reduce a 3-element problem to a 2-element problem you already know how to solve. Here is the mental model. Sort the array first. Then loop through each element as the 'fixed' element. For each fixed element, you have a sorted subarray to its right. Run two pointers (left and right) on that subarray to find a pair that sums to negative of the fixed element. If fixed + left + right = 0, you found a triplet. If the sum is too small, move le