Two Pointers

La technique Two Pointers (ou double pointeur) est l'un de ces patterns algorithmiques qui font passer un code de lent à fulgurant en changeant simplement la façon d'explorer les données. L'idée : au lieu de parcourir une structure linéaire avec deux boucles imbriquées, on utilise deux indices qui se déplacent simultanément — et on réduit la complexité de O(N²) à O(N).

Le problème : les boucles imbriquées et leur coût

Imaginons un problème classique : dans un tableau trié, trouver deux nombres dont la somme est égale à une cible donnée.

L'approche naïve ? Tester toutes les paires possibles avec deux boucles :

function twoSumNaif(nums: number[], target: number): [number, number] | null {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
  return null;
}

Cette approche fonctionne, mais elle a un coût : pour un tableau de 10 000 éléments, on effectue jusqu'à 50 millions de comparaisons. La complexité est O(N²). Sur de grands volumes, c'est rédhibitoire.

Le problème des boucles imbriquées, c'est qu'elles ignorent toute information structurelle. Chaque paire est testée indépendamment, sans exploiter le fait que le tableau est trié. Or, si on sait que les éléments sont ordonnés, on peut raisonner autrement : si la somme est trop grande, on peut éliminer d'un coup toutes les paires qui commencent par cet élément.

Le principe : deux indices, un seul passage

La technique Two Pointers exploite précisément cette structure. On place un pointeur left au début du tableau et un pointeur right à la fin. À chaque étape, on calcule la somme des deux éléments pointés et on décide comment déplacer les indices :

• Si la somme est trop petite : on avance left vers la droite (des valeurs plus grandes).
• Si la somme est trop grande : on recule right vers la gauche (des valeurs plus petites).
• Si la somme est exactement égale à la cible : on a trouvé.

À chaque étape, un seul indice bouge. Les deux pointeurs avancent l'un vers l'autre et se rejoignent en O(N). On a remplacé l'exploration exhaustive par un raisonnement directionnel.

Exemple concret : Two Sum sur tableau trié

function twoSum(nums: number[], target: number): [number, number] | null {
  let left = 0;
  let right = nums.length - 1;
 
  while (left < right) {
    const sum = nums[left] + nums[right];
 
    if (sum === target) {
      // Paire trouvée : on retourne les indices
      return [left, right];
    } else if (sum < target) {
      // Somme trop petite : on avance left pour augmenter la somme
      left++;
    } else {
      // Somme trop grande : on recule right pour diminuer la somme
      right--;
    }
  }
 
  // Aucune paire ne satisfait la condition
  return null;
}
 
// Exemple d'utilisation
const nums = [2, 3, 5, 8, 11, 17];
const target = 19;
 
console.log(twoSum(nums, target));
// [2, 4] → nums[2] + nums[4] = 5 + 11 = 16... non, essayons :
// left=0(2), right=5(17) → 19 ✓
// [0, 5] → nums[0] + nums[5] = 2 + 17 = 19

Déroulons l'exécution sur [2, 3, 5, 8, 11, 17] avec target = 19 :

left=0 (2), right=5 (17) → 2 + 17 = 19 ✓  Trouvé ! Retourne [0, 5]

Un seul passage, un seul test. Contre potentiellement 15 comparaisons avec la méthode naïve.

Les deux variantes principales

Sens opposé (Opposite Direction)

C'est la variante que nous venons de voir. Les deux pointeurs partent des extrémités et convergent vers le centre. Elle s'applique sur des tableaux triés et permet de prendre des décisions directionnelles grâce à l'ordre.

Cas d'usage typiques : Two Sum sur tableau trié, vérifier si un tableau est un palindrome, trouver des triplets dont la somme vaut zéro (Three Sum).

Même direction (Sliding / Fast-Slow)

Ici, les deux pointeurs partent du même côté mais progressent à des vitesses ou des rythmes différents. Un pointeur "rapide" avance conditionnellement, un pointeur "lent" ne progresse que lorsqu'une condition est remplie.

Cette variante est idéale pour modifier un tableau en place — notamment pour supprimer des doublons — ou pour trouver des cycles dans une liste chaînée (algorithme de Floyd).

Autre exemple : suppression de doublons en place

Donnons un tableau trié, et supprimons les doublons en place sans allouer de mémoire supplémentaire.

function removeDuplicates(nums: number[]): number {
  if (nums.length === 0) return 0;
 
  // `slow` pointe vers la dernière position valide écrite
  // `fast` explore le reste du tableau
  let slow = 0;
 
  for (let fast = 1; fast < nums.length; fast++) {
    if (nums[fast] !== nums[slow]) {
      // Nouvel élément unique trouvé : on l'écrit à la prochaine position valide
      slow++;
      nums[slow] = nums[fast];
    }
    // Si nums[fast] === nums[slow] : c'est un doublon, on avance fast sans toucher slow
  }
 
  // Le tableau valide occupe les indices 0 à slow inclus
  return slow + 1;
}
 
// Exemple d'utilisation
const nums = [1, 1, 2, 2, 3, 4, 4, 5];
const length = removeDuplicates(nums);
 
console.log(length);        // 5
console.log(nums.slice(0, length)); // [1, 2, 3, 4, 5]

fast parcourt le tableau une seule fois. slow n'avance que quand il rencontre un nouvel élément unique. À la fin, les slow + 1 premiers éléments du tableau contiennent les valeurs dédupliquées, sans avoir alloué un nouveau tableau.

Complexité

Two Pointers offre le meilleur des deux mondes : la rapidité de la table de hachage sans son coût en mémoire. C'est un algorithme en place — il n'utilise que les deux variables d'index, quelle que soit la taille du tableau.

La condition préalable est souvent un tri du tableau, qui coûte O(N log N). Au total, une solution Two Pointers est donc généralement en O(N log N) si le tri est nécessaire, ou en O(N) si le tableau est déjà ordonné.

Quand utiliser Two Pointers ?

La technique Two Pointers est le bon réflexe dans ces situations :

Le tableau (ou la chaîne) est trié — ou peut l'être sans dommage. L'ordre est ce qui rend les décisions directionnelles possibles.

On cherche des paires ou des triplets respectant une contrainte (somme égale à une cible, somme nulle, distance minimale). Two Sum, Three Sum, Closest Sum sont des classiques des entretiens techniques.

On doit modifier un tableau en place : supprimer des doublons, retirer des éléments satisfaisant une condition, déplacer les zéros en fin de tableau.

On travaille sur une chaîne de caractères : vérifier si c'est un palindrome, inverser une chaîne, comparer deux chaînes de façon symétrique.

On cherche un sous-tableau ou une fenêtre satisfaisant une contrainte — dans ce cas, on parle souvent de "sliding window", une variante proche qui mérite son propre article.

À l'inverse, Two Pointers n'est pas adapté si la structure n'est pas linéaire (graphes, arbres), si elle n'est pas triée et que le tri n'est pas acceptable, ou si les éléments doivent être consultés dans un ordre non séquentiel.

Repérer le pattern en entretien

Lors d'un entretien technique, certains indices trahissent qu'un problème est résolu par Two Pointers :

• L'énoncé mentionne un tableau trié et cherche des éléments respectant une condition numérique.
• On doit opérer en place sans mémoire supplémentaire.
• La solution naïve est O(N²) et l'interviewer suggère qu'on peut faire mieux.
• Le problème implique de comparer des éléments aux deux extrémités d'une structure.

La technique Two Pointers illustre un principe général de l'algorithmique : exploiter la structure des données pour réduire l'espace de recherche. Les boucles imbriquées ignorent tout de l'ordre ou des propriétés du tableau — elles testent aveuglément. Les deux pointeurs, eux, raisonnent : chaque déplacement élimine des candidats impossibles de façon certaine. C'est ce saut conceptuel, de la force brute au raisonnement structuré, qui fait passer un algorithme de lent à efficace.