Pattern Guide
Two Pointer — Advanced Patterns
"3Sum, 4Sum, remove duplicates, partition. Multiple pointer coordination."
Advanced two-pointer problems beyond the basic "find pair with sum k": 3Sum/4Sum via reduction, removing duplicates with write pointer, Dutch National Flag 3-way partition, partitioning by predicate, and merging sorted arrays in-place. Key insight: combining sort + two pointers reduces many O(n²) problems to O(n log n), and multiple coordinated pointers handle more complex conditions.
Problems you can solve with this pattern
4 problems · click any to start solving
// 3Sum — sorted + two pointers, O(n²)
function threeSum(nums) {
nums.sort((a, b) => a - b);
const result = [];
for (let i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] === nums[i-1]) continue; // skip duplicates
let l = i + 1, r = nums.length - 1;
while (l < r) {
const sum = nums[i] + nums[l] + nums[r];
if (sum === 0) {
result.push([nums[i], nums[l], nums[r]]);
while (l < r && nums[l] === nums[l+1]) l++;
while (l < r && nums[r] === nums[r-1]) r--;
l++; r--;
} else if (sum < 0) l++;
else r--;
}
}
return result;
}
// Dutch National Flag — 3-way partition in O(n)
function dutchNationalFlag(arr, pivot) {
let lo = 0, mid = 0, hi = arr.length - 1;
while (mid <= hi) {
if (arr[mid] < pivot) [arr[lo++], arr[mid++]] = [arr[mid], arr[lo]];
else if (arr[mid] > pivot) [arr[mid], arr[hi--]] = [arr[hi], arr[mid]];
else mid++;
}
}
// Write pointer — in-place deduplication
function removeDuplicates(arr) {
let write = 0;
for (const x of arr) {
if (write === 0 || arr[write-1] !== x) arr[write++] = x;
}
return write; // new length
}3Sum: sort, fix first element, then two-pointer for remaining pair. Skip duplicates carefully. 4Sum: fix two elements (two nested loops), then two-pointer. Dutch National Flag: three pointers (lo, mid, hi) for 3-way partition. "Write pointer" pattern: read pointer scans all elements, write pointer marks where next valid element goes. O(n) in-place without extra space.
// 3Sum — sorted + two pointers, O(n²)
function threeSum(nums) {
nums.sort((a, b) => a - b);
const result = [];
for (let i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] === nums[i-1]) continue; // skip duplicates
let l = i + 1, r = nums.length - 1;
while (l < r) {
const sum = nums[i] + nums[l] + nums[r];
if (sum === 0) {
result.push([nums[i], nums[l], nums[r]]);
while (l < r && nums[l] === nums[l+1]) l++;
while (l < r && nums[r] === nums[r-1]) r--;
l++; r--;
} else if (sum < 0) l++;
else r--;
}
}
return result;
}
// Dutch National Flag — 3-way partition in O(n)
function dutchNationalFlag(arr, pivot) {
let lo = 0, mid = 0, hi = arr.length - 1;
while (mid <= hi) {
if (arr[mid] < pivot) [arr[lo++], arr[mid++]] = [arr[mid], arr[lo]];
else if (arr[mid] > pivot) [arr[mid], arr[hi--]] = [arr[hi], arr[mid]];
else mid++;
}
}
// Write pointer — in-place deduplication
function removeDuplicates(arr) {
let write = 0;
for (const x of arr) {
if (write === 0 || arr[write-1] !== x) arr[write++] = x;
}
return write; // new length
}- 2-pointer: O(n) after sorting for pair sum
- 3Sum: O(n²) — fix one + 2-pointer on rest
- kSum: O(n^(k-1)) — fix k-2 elements + 2-pointer
- Dutch flag: 3 pointers (lo, mid, hi) for 3-way partition
- Write pointer: 1 read, 1 write — in-place filtering/dedup
Duplicate skipping in kSum: After placing a triplet/quadruplet in results, advance all pointers and skip duplicates at each level. Order matters: skip outer duplicates before outer loop body, skip inner duplicates after placing a result.