Two pointers : deux index au lieu d'une boucle imbriquée
Remplacer un O(n²) par un O(n) en faisant avancer deux index intelligemment.
Le two pointers utilise deux index qui parcourent une structure — souvent un tableau trié — au lieu d'une boucle imbriquée. Chaque élément n'est visité qu'un nombre constant de fois, ce qui ramène une complexité O(n²) à O(n).
Deux variantes principales : (a) des pointeurs aux deux extrémités qui se rapprochent — utile pour vérifier un palindrome ou trouver une paire dont la somme vaut une cible dans un tableau trié ; (b) des pointeurs qui avancent dans le même sens à des vitesses différentes — utile pour détecter un cycle dans une liste chaînée (pointeur lent/rapide) ou supprimer des doublons en place.
Condition clé pour la variante « extrémités qui se rapprochent » : le tableau doit être trié (ou triable), sinon déplacer un pointeur n'a pas de sens logique par rapport à la valeur cherchée.
Exemple — Two Sum II (tableau trié) : un pointeur à gauche, un à droite. Si la somme est trop grande, on recule le pointeur droit ; si elle est trop petite, on avance le pointeur gauche. Chaque élément est visité au plus une fois → O(n).
Piège fréquent : appliquer le two pointers sur un tableau non trié sans y penser. Dans ce cas, il faut soit trier d'abord (coût O(n log n)), soit passer par un hashmap si l'ordre des éléments compte.
Vidéo
NeetCode — Two Pointers (playlist) — NeetCodeQuiz
1. Le two pointers permet typiquement de transformer une solution en :
2. Pour la variante « deux extrémités qui se rapprochent », quelle condition est généralement nécessaire ?
3. Le pointeur lent/rapide (« tortue et lièvre ») sert typiquement à :
4. Dans Two Sum II sur un tableau trié, si la somme des deux pointeurs est trop grande, on :