03 — Le pattern des deux pointeurs

Ce que tu vas apprendre

• Le principe des deux pointeurs, convergents et parallèles
• Trouver une paire de somme donnée en O(n) sur un tableau trié
• Vérifier un palindrome et fusionner deux tableaux triés
• Quand ce pattern s'applique et pourquoi il économise la mémoire

Prérequis

• 02 — Dichotomie avancée

Le pattern des deux pointeurs remplace une boucle imbriquée par deux indices qui se déplacent intelligemment dans le tableau. Là où l'approche naïve teste toutes les paires en O(n²), les deux pointeurs font une seule passe en O(n), souvent sans aucune mémoire supplémentaire. C'est l'un des patterns les plus élégants et les plus demandés, en prod comme en entretien.

Les deux variantes

Il existe deux usages principaux du pattern.

Pointeurs convergents : un pointeur part du début, l'autre de la fin, et ils se rapprochent. C'est le cas pour les problèmes de paires sur un tableau trié, ou les palindromes.

Pointeurs parallèles : les deux pointeurs avancent dans le même sens, à des vitesses différentes. C'est le cas pour fusionner deux séquences, ou supprimer des doublons en place.

Trouver une paire de somme donnée

Le problème : dans un tableau trié, existe-t-il deux éléments qui somment à une cible ? L'approche naïve teste toutes les paires, O(n²). Avec deux pointeurs convergents, on exploite le tri : si la somme courante est trop petite, on avance le pointeur gauche (pour augmenter) ; si elle est trop grande, on recule le pointeur droit (pour diminuer).

typescriptfunction paireSomme(arr: number[], cible: number): [number, number] | null {
  let gauche = 0;
  let droite = arr.length - 1;
  while (gauche < droite) {
    const somme = arr[gauche] + arr[droite];
    if (somme === cible) return [gauche, droite];
    if (somme < cible) gauche++; // besoin de plus grand
    else droite--;                // besoin de plus petit
  }
  return null;
}

Chaque tour avance ou recule un pointeur, et ils ne se croisent qu'une fois : O(n). Pas de Set, pas de mémoire supplémentaire, contrairement à la version avec table de hachage de l'article 00. Le prix d'entrée est que le tableau doit être trié.

Vérifier un palindrome

Les pointeurs convergents vérifient naturellement la symétrie. On compare le premier et le dernier caractère, puis on resserre.

pythondef est_palindrome(s: str) -> bool:
    gauche, droite = 0, len(s) - 1
    while gauche < droite:
        if s[gauche] != s[droite]:
            return False
        gauche += 1
        droite -= 1
    return True

On parcourt la chaîne une demi-fois : O(n), avec O(1) de mémoire.

Fusionner deux tableaux triés

Ici les pointeurs sont parallèles, un sur chaque tableau. À chaque étape, on prend le plus petit des deux éléments en tête. C'est exactement l'étape de fusion du tri par fusion vue dans la série Tri.

pythondef fusionner(a: list[int], b: list[int]) -> list[int]:
    i = j = 0
    result = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i]); i += 1
        else:
            result.append(b[j]); j += 1
    result.extend(a[i:])
    result.extend(b[j:])
    return result

Chaque élément des deux tableaux est traité une fois : O(n + m).

Supprimer les doublons en place

Variante parallèle classique sur un tableau trié : un pointeur « lent » marque la position d'écriture, un pointeur « rapide » explore. On n'écrit que quand on rencontre une nouvelle valeur.

typescriptfunction dedupeTrie(arr: number[]): number {
  if (arr.length === 0) return 0;
  let lent = 0;
  for (let rapide = 1; rapide < arr.length; rapide++) {
    if (arr[rapide] !== arr[lent]) {
      lent++;
      arr[lent] = arr[rapide];
    }
  }
  return lent + 1; // nombre d'éléments uniques
}

O(n) en temps, O(1) en espace, et la déduplication se fait sans tableau auxiliaire.

Quand l'appliquer

Le pattern des deux pointeurs s'applique quand ces signaux apparaissent :

• le tableau est trié (ou peut l'être), et on cherche des paires, des triplets ou une frontière ;
• le problème porte sur une symétrie (palindrome) ;
• on fusionne ou compare deux séquences ordonnées ;
• on doit modifier un tableau en place en distinguant lecture et écriture.

L'avantage récurrent : O(1) de mémoire là où une approche par Set ou par copie demanderait O(n). Quand la mémoire compte, les deux pointeurs sont préférables à l'indexation par hachage.

L'article suivant présente un cousin du pattern : la fenêtre glissante, pour les problèmes de sous-tableaux et sous-chaînes contigus.

Sources

• Laakmann McDowell, G. (2015). Cracking the Coding Interview (6th ed.), Chapitre "Arrays and Strings". CareerCup.
• Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.), Section 2.3.1 (procédure de fusion). MIT Press.
• Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.), Section 1.4. Addison-Wesley.