Lessons · TypeScript · two pointers
Two fingers, one pass
Instead of comparing every pair with two nested loops, put one index at each end and move them toward each other, deciding at each step which one to move.
Hone is a place to practise programming. This is one of its lessons, written out in full and free to read without an account.
What it is for
It turns a comparison of every pair, which is n squared, into one pass. The catch is that it only works when order tells you something, so the data is sorted or can be.
How to think about it
Ask what the current pair tells you. If one of the two can never be part of any answer, move past it. If you cannot say that, this is the wrong tool.
Worked example
function pairSummingTo(values, target) {values is SORTED; that is what makes the move safe.let left = 0, right = values.length - 1;One at each end.
while (left < right) {Stop when they meet.const total = values[left] + values[right];
if (total === target) return [values[left], values[right]];
if (total < target) left++;Too small: only a bigger left can help.
else right--;Too big: only a smaller right can help.
}
return null;
}
console.log(String(pairSummingTo([1, 3, 5, 8, 12], 17)));5,12
console.log(String(pairSummingTo([1, 3, 5, 8, 12], 100)));null
Your turn
The pair is too small; move the pointer that can help.
if (total < target) ++; else right--;
Solve one with the tests running
The trap
On UNSORTED data the move is not safe: stepping past a value throws away a real answer, and the function returns null with total confidence.