← Data structures from scratch · Lesson 6/32
Two pointers and sliding windows
One at each end
Many array problems are solved with two indexes instead of two nested loops. The simplest: one starts on the left (i), the other on the right (j), and they move toward each other.
To know whether a word is a palindrome (reads the same backwards), compare the ends: if they match, both step toward the middle; if not, you already know it isn't. Each letter is looked at once: O(n).
$ node leccion.js
Press RUN (or Ctrl+Enter).
What to look at
- "reconocer" compares four pairs and reaches the middle:
true. - "sahuayo" fails on the first comparison (s vs o) and stops there.
The whole lesson on one page
One at each end
Many array problems are solved with two indexes instead of two nested loops. The simplest: one starts on the left (i), the other on the right (j), and they move toward each other.
To know whether a word is a palindrome (reads the same backwards), compare the ends: if they match, both step toward the middle; if not, you already know it isn't. Each letter is looked at once: O(n).
function esPalindromo(texto) {
let i = 0, j = texto.length - 1;
while (i < j) {
console.log(" ", texto[i], "vs", texto[j]);
if (texto[i] !== texto[j]) return false;
i++;
j--;
}
return true;
}
console.log(esPalindromo("reconocer"));
console.log(esPalindromo("sahuayo"));
- "reconocer" compares four pairs and reaches the middle:
true. - "sahuayo" fails on the first comparison (s vs o) and stops there.
In a sorted array
With a sorted array, two pointers find two numbers that add up to a target without trying every pair. If the ends add up to too little, move i right (a bigger number); if they overshoot, move j left (a smaller one).
Each step discards one item for good, so it's at most n steps instead of n²/2 pairs. The ordering is what lets you discard.
function parQueSuma(ordenado, objetivo) {
let i = 0, j = ordenado.length - 1;
while (i < j) {
const suma = ordenado[i] + ordenado[j];
console.log(" i =", i, "j =", j, "suma =", suma);
if (suma === objetivo) return [i, j];
if (suma < objetivo) i++; // too little: a bigger one
else j--; // too much: a smaller one
}
return null;
}
console.log(parQueSuma([1, 3, 4, 6, 8, 11], 10));
1 + 11 = 12 overshoots, so 11 is out; 1 + 8 = 9 falls short, so 1 is out; 3 + 8 = 11 overshoots and 8 is out; 3 + 6 = 9 falls short and 3 is out; 4 + 6 = 10. Five steps and it answers [ 2, 3 ].
The sliding window
Another flavor of two pointers: both move in the same direction and mark a window [start, end]. end moves forward to bring items in; start moves forward to drop them when the window stops meeting the condition.
Example: the longest stretch of a text with no repeated letters. The window grows while there are no repeats; when a repeat comes in, start slides until it's gone. Each letter enters once and leaves at most once: O(n).
function masLargoSinRepetir(s) {
const dentro = new Set();
let inicio = 0, mejor = 0;
for (let fin = 0; fin < s.length; fin++) {
while (dentro.has(s[fin])) { // repeat: shrink from the left
dentro.delete(s[inicio]);
inicio++;
}
dentro.add(s[fin]);
mejor = Math.max(mejor, fin - inicio + 1);
console.log(" window:", s.slice(inicio, fin + 1));
}
return mejor;
}
console.log(masLargoSinRepetir("abcabcbb"));
The window grows to "abc", and each time a repeated letter comes in it drops the leftmost one: "bca", "cab", "abc"… The best one is 3 long.