Squeeze from both sides
Many "find a pair" problems are O(n²) with nested loops. If the data is sorted, put one pointer at each end: if the sum is too big, move the right one left; too small, move the left one right. Every step rules out a whole row of pairs — two pointers, O(n).
Pairs, duplicates, merging
function pairWithSum(sorted, target) {
let i = 0, j = sorted.length - 1;
while (i < j) {
const sum = sorted[i] + sorted[j];
if (sum === target) return [sorted[i], sorted[j]];
if (sum < target) i++;
else j--;
}
return null;
}
console.log(pairWithSum([50, 60, 90, 160, 180, 220], 270));
// Same direction: a slow "write" pointer and a fast "read" pointer.
function dedupeSorted(a) {
let write = 0;
for (let read = 0; read < a.length; read++) {
if (read === 0 || a[read] !== a[read - 1]) a[write++] = a[read];
}
a.length = write;
return a;
}
console.log(dedupeSorted([1, 1, 2, 3, 3, 3, 7]));
function isPalindrome(s) {
const t = s.toLowerCase().replace(/[^a-z0-9]/g, "");
for (let i = 0, j = t.length - 1; i < j; i++, j--) if (t[i] !== t[j]) return false;
return true;
}
console.log(isPalindrome("Was it a car or a cat I saw?"));