Fiches › Carte › Partie 09 · Coding › coding 02

Deux pointeurs — éliminer une classe à chaque pas

Sur un tableau trié, une seule comparaison aux deux bords écarte tout un bloc de paires d'un coup : c'est le tri, et rien d'autre, qui rend cette élimination valide. Fil rouge : LC 167, a = [1, 3, 4, 6, 8, 11], t = 10, réponse (2, 3) — 5 comparaisons pour couvrir les 15 paires. Puis la famille : 3Sum, où l'on fixe un indice et où les doublons se sautent au while ; et le container (LC 11), sans tri, où l'élimination se rachète en majorant les deux facteurs. Jamais la solution complète : le squelette, la trace, les quatre phrases.

Ce que cette sheet suppose acquis
  • Le rituel TAP. Invariant, variant, conclusion, complexité — c00, pas 1. Cette sheet ne le redémontre pas, elle l'instancie une fois au pas 4.
  • Invariant = conteneur + tranche + « exactement ». c00, pas 2. Ici il n'y a pas d'accumulateur : le conteneur est la zone encore possible [l, r], et « exactement » devient « et rien en dehors ».
  • Variant = entier ≥ 0 strictement décroissant. c00, pas 3. Celui-ci est le plus simple de toute la partie : r − l.
  • Le dictionnaire en O(1) amorti. c00, pas 5. C'est le remède du pas 7 quand le tableau n'est pas trié et que l'énoncé veut les indices.
  • Trier coûte O(n log n) et détruit les indices d'origine. Les deux faits servent : le premier dans la complexité composée, le second dans le contre-signal.
Hypothèses posées
H1Le tableau est trié par ordre croissant, ou le devient sans perte — c'est-à-dire que l'énoncé demande des valeurs, pas des indices d'origine. C'est cette hypothèse, et elle seule, qui rend l'élimination du pas 3 valide ; elle tombe au pas 7. H2La quantité cherchée porte sur une paire d'indices (l, r), et la comparaison en (l, r) tranche : elle désigne celui des deux bords qui ne peut plus servir. Une quantité qui ne serait monotone en aucun des deux bords sort du pattern. H3Au pas 6, H1 est levée et remplacée : la quantité s'écrit comme un produit de deux facteurs qu'on sait majorer séparément. C'est la seconde justification de l'élimination, et la seule qui survive sans tri. H4On énonce le squelette — les lignes de contrôle — et les quatre phrases. Le corps se remplit devant l'interlocuteur : une sheet de coding ne contient jamais la solution complète.

La chaîne

Le signal, et le contre-signal tronc

Deux marques suffisent : un tableau trié (ou triable sans perte) et une question sur des paires — somme cible, écart, produit. Une troisième porte ouverte, sans tri : une quantité en deux facteurs, du type min(h[l], h[r]) × (r − l).

trié  +  question sur des paires   |   ou deux facteurs majorables séparément

Le contre-signal est net et double : des indices d'origine à renvoyer sur un tableau non trié — trier les détruit, c'est le dictionnaire qu'il faut (c00) ; et une quantité qui ne se majore par aucun bord, où plus rien ne s'élimine.

« Le tableau est trié et la question porte sur une paire, donc une comparaison aux deux bords désigne un bord qui ne peut plus servir, donc deux indices qui se rapprochent suffisent. »

Application — lire LC 167

Énoncé. « Un tableau trié croissant, une cible ; renvoyer les deux positions dont la somme vaut la cible. »

Les deux marques. « trié croissant » → H1 est donnée par l'énoncé, gratuitement ; « les deux positions dont la somme vaut » → une question sur des paires.

Fil rouge. a = [1, 3, 4, 6, 8, 11], t = 10. Réponse : (2, 3), soit 4 + 6 — l'unique paire, vérifiée contre les 15 paires de la force brute.

Ce qui n'est pas le signal. LC 1 « Two Sum », non trié, indices demandés : dictionnaire. Un sous-tableau contigu : fenêtre glissante, c01. Une somme exactement égale avec des négatifs, sur un segment : préfixes, c10.

Le pattern : ils se rapprochent, la comparaison décide tronc

l part de 0, r de n − 1, et ils se rapprochent. Une seule comparaison par tour, en (l, r), et elle fait une seule chose : désigner celui des deux bords qui sort. Aucun des deux ne recule jamais.

s > t ⇒ r −= 1  ·  s < t ⇒ l += 1  ·  s = t ⇒ fini

La boucle est l < r, strict. Avec l <= r on autorise la paire (i, i) : un élément apparié à lui-même, qui n'est pas une paire. C'est le premier piège, et il ne lève aucune exception.

« Une seule comparaison par tour désigne le bord qui sort, donc un pointeur bouge exactement une fois par tour, donc la zone encore possible rétrécit à chaque pas. »

Application — le squelette de LC 167
l, r = 0, n − 1 tant que l < r : # STRICT, jamais l <= r s = a[l] + a[r] si s == t : retour (l, r) si s > t : r −= 1 # r ne sert plus à aucun l′ ≥ l sinon : l += 1 # l ne sert plus à aucun r′ ≤ r

retour aucune paire.

Les deux commentaires sont la preuve, pas de la décoration : chacun dit quelle classe de paires le pas vient d'écarter. Les effacer, c'est réduire le pattern à une recette qu'on ne sait plus justifier — et la justification est exactement ce qu'on demande à l'oral.

Trois branches, jamais deux. L'égalité a sa branche propre, avant les deux inégalités. Fondre s == t dans l'un des deux tests fait sortir la paire cherchée de la zone avant qu'on l'ait lue.

L'élimination : ce que le tri autorise tronc

Le cœur tient en une ligne. Si a[l] + a[r] > t, alors pour tout l′ ≥ l le tri donne a[l′] ≥ a[l], donc la somme ne peut que monter : aucune paire de bord droit r ne vaut t. r est fini — et avec lui toute une colonne de paires.

l′ ≥ l  ⇒  a[l′] ≥ a[l]  ⇒  a[l′] + a[r] ≥ a[l] + a[r] > t

La flèche du milieu est le tri, et c'est la seule chose qu'on lui demande. Symétriquement, s < t écarte la ligne du bord gauche l. Une comparaison, une classe entière.

« Le tri donne a[l′] ≥ a[l] pour tout l′ à droite de l, donc toutes ces paires dépassent déjà la cible, donc le bord droit r est éliminé avec toute sa colonne — et non pas un candidat à la fois. »

Application — les 15 paires du fil rouge, en 5 comparaisons

a = [1, 3, 4, 6, 8, 11], t = 10 : n = 6, donc 15 paires à couvrir. Chaque pas en écarte un bloc, la paire testée comprise :

pas(l, r) · sla classe écartéepaires
1(0, 5) · 12 > 10(l′, 5), l′ = 0…45
2(0, 4) · 9 < 10(0, r′), r′ = 1…44
3(1, 4) · 11 > 10(l′, 4), l′ = 1…33
4(1, 3) · 9 < 10(1, r′), r′ = 2…32
5(2, 3) · 10 = 10 ✓trouvée : 4 + 61

5 + 4 + 3 + 2 + 1 = 15. La partition est exacte : les cinq classes recouvrent les 15 paires sans recouvrement et sans trou. C'est ça, « couvrir sans énumérer », et c'est la phrase qui vaut le point à l'oral.

Figure 1 — les 5 comparaisons de LC 167, l'invariant à chaque image

a = [1, 3, 4, 6, 8, 11], t = 10. Le cadre vert est la zone encore possible [l, r] ; le fond ambré marque les cases éliminées, sorties de la zone avec preuve. Fais « pas › » et regarde combien de paires meurent à chaque image : 5, puis 4, puis 3, puis 2 — jamais une seule. La ligne du bas est l'invariant, réécrit à chaque image ; dis-le avant de le lire.

Invariant, variant, conclusion, complexité

L'invariant n'est pas « la paire est dans [l, r] » tout court : c'est si une paire de somme t existe, alors ses deux indices sont dans [l, r]. Le conditionnel porte la conclusion. Le variant est r − l.

I : ∃ paire de somme t ⇒ ses deux indices ∈ [l, r]  ·  V : r − l

Préservation : le pas 3 montre qu'on ne retire jamais un bord sans avoir prouvé qu'aucun partenaire restant ne lui convient. Conclusion : à l = r, la zone n'a plus de paire ; I, contraposée, dit qu'il n'en existait aucune.

« Le variant r − l est entier, positif et décroît strictement à chaque tour, donc la boucle s'arrête en au plus n − 1 pas, donc le coût est linéaire une fois le tri payé. »

Application — les quatre cases, sur le fil rouge

I. Si une paire de somme 10 existe, ses deux indices sont dans [l, r]. Initialisation : [0, 5] est tout le tableau, I tient trivialement.

V. r − l : part de 5, vaut 1 au dernier pas, décroît de 1 à chaque tour — entier, ≥ 0, strictement décroissant. Donc au plus n − 1 = 5 tours, et il y en a eu exactement 5.

Conclusion, les deux sorties. Retour anticipé : s = t a été lue, la paire est vraie. Sortie par l = r : plus aucune paire dans la zone, et I dit qu'il n'en existe nulle part — donc « aucune », et c'est une conclusion, pas un aveu.

Complexité. ≤ n − 1 tours × O(1) (une addition, deux comparaisons) ⇒ O(n) sur un tableau déjà trié, O(n log n) s'il faut trier — le tri domine, et il faut le dire dans cet ordre. Espace O(1) : deux entiers.

Vérifié à l'exécution : 0 désaccord sur 20 000 tableaux triés aléatoires (longueurs 0 à 7, valeurs −9 à 9, cibles −18 à 18) face à la force brute, et toute paire renvoyée somme bien à la cible.

3Sum : fixer un indice, deux pointeurs dessous

Trois indices, mais un seul degré de liberté en trop : on fixe i, et chercher a[i] + a[l] + a[r] = 0 redevient exactement le pas 2, avec la cible −a[i] sur [i+1, n−1].

a[i] + a[l] + a[r] = 0  ⇔  a[l] + a[r] = −a[i]  ·  n × O(n) = O(n2)

Le tri sert ici deux fois : il valide l'élimination, et il met les valeurs égales côte à côte — donc les doublons se sautent par un while, en O(1) amorti, jamais par un ensemble de triplets.

« i fixé ramène le problème à une somme cible sur un tableau trié, donc le pas 2 s'applique tel quel, donc n balayages linéaires, donc O(n²) — et les égaux étant voisins après tri, les doublons se sautent sans mémoire. »

Application — le squelette, et les doublons chiffrés
a.sort() pour i dans range(n − 2) : si i > 0 et a[i] == a[i−1] : continue # doublon sur i l, r = i + 1, n − 1 tant que l < r : s = a[i] + a[l] + a[r] si s < 0 : l += 1 sinon si s > 0 : r −= 1 sinon : enregistrer (a[i], a[l], a[r]) tant que l < r et a[l] == a[l+1] : l += 1 # doublon sur l tant que l < r et a[r] == a[r−1] : r −= 1 # doublon sur r l += 1 ; r −= 1

Les trois while ne sont pas optionnels. Sans eux, sur [−1, 0, 1, 2, −1, −4] le balayage rend (−1, −1, 2), (−1, 0, 1) et encore (−1, 0, 1) : 3 triplets au lieu de 2. Sur [−2, 0, 0, 2, 2], (−2, 0, 2) sort deux fois.

Pourquoi pas un set. Il donne la bonne réponse, et coûte O(n2) de mémoire dans le pire cas — l'espace annoncé passe de O(1) à O(n2). C'est la complexité qui est fausse, pas le résultat : la faute typique qui ne se voit pas aux tests.

Chiffré. n = 1 000 : O(n2) = 106 contre 109 pour le triple balayage naïf. Vérifié : 0 désaccord sur 5 000 tableaux aléatoires face à l'énumération des triplets.

Sans tri : majorer les deux facteurs

LC 11 n'est pas trié, et pourtant l'élimination tient. L'aire vaut min(h[l], h[r]) × (r − l). Si h[l] est le plus bas, toute paire (l, r′) avec r′ < r perd sur la largeur et ne gagne rien sur la hauteur, plafonnée par h[l].

aire(l, r′) ≤ h[l] × (r′ − l) < h[l] × (r − l) = aire(l, r)

On majore chaque facteur séparément : c'est la seconde justification de l'élimination, et la seule qui ne demande pas de tri. Elle désigne toujours le plus bas : garder le plus bas, c'est garder le plafond.

« Le bord le plus bas plafonne la hauteur et la largeur ne fera que baisser, donc toutes les paires qui le gardent sont majorées par l'aire courante, donc ce bord sort — sans tri, en majorant les deux facteurs. »

Application — LC 11 sur le fil rouge à neuf barres
l, r = 0, n − 1 ; best = 0 tant que l < r : best = max(best, min(h[l], h[r]) * (r − l)) si h[l] < h[r] : l += 1 # on bouge LE PLUS BAS sinon : r −= 1

h = [1, 8, 6, 2, 5, 4, 8, 3, 7] : réponse 49, atteinte en (l, r) = (1, 8), soit min(8, 7) × 7 = 7 × 7. 8 comparaisons contre 36 paires en force brute.

Bouger le plus haut « pour voir » coûte la correction, pas seulement du temps : la même boucle avec la comparaison inversée rend 8 au lieu de 49, en exactement autant de pas. Le pattern ne plante pas, il ment.

L'invariant change de forme. Il ne dit plus « la solution est dans [l, r] » mais « best ≥ l'aire de toute paire déjà sortie de [l, r] ». Conclusion à l = r : toutes les paires sont sorties, donc best est le maximum. 0 désaccord sur 20 000 tableaux aléatoires face à la force brute.

Figure 2 — LC 11 : le plus bas est le seul qui puisse faire mieux en bougeant

h = [1, 8, 6, 2, 5, 4, 8, 3, 7], sans tri. Le cadre vert est l'écart courant [l, r], le fond ambré les deux bords du record. Le record tombe à l'image 2 — 49 — et les six images suivantes ne font que le confirmer : la largeur ne fait que baisser tandis que la hauteur reste plafonnée par le 8 de gauche. Regarde qui bouge : toujours le plus bas, et l ne bouge qu'une fois en tout.

Où ça casse casse

Un seul cas fatal, et il ne lève aucune exception : somme cible sur un tableau non trié. L'implication du pas 3 devient fausse — a[l′] peut être plus petit que a[l] pour l′ > l — donc on élimine des paires qu'on n'a pas le droit d'éliminer.

La boucle tourne, termine, et rend « aucune paire ». C'est une réponse, elle est fausse, et rien dans la trace ne le signale.

« Sans tri, a[l′] ≥ a[l] tombe, donc l'élimination retire des paires jamais examinées, donc le résultat est faux sans erreur — il faut un dictionnaire, ou trier des couples (valeur, indice). »

Le contre-exemple minimal, à sortir de mémoire

a = [3, 1, 4], t = 5. La bonne réponse est (1, 2) : 1 + 4 = 5. Le squelette du pas 2 renvoie « aucune paire ».

Pourquoi. Premier tour : 3 + 4 = 7 > 5, donc r sort — au motif que tout a[l′] à droite serait ≥ 3. Or a[1] = 1. La paire (1, 2) meurt dans cette élimination sans avoir été lue. Second tour : 3 + 1 = 4 < 5, l sort, l = r, fini.

Le remède dépend de ce qu'on rend. Les indices d'origine (LC 1) : dictionnaire valeur → indice, O(n), c00. Les valeurs : trier, puis deux pointeurs, O(n log n). Les indices et le tri : trier des couples (valeur, indice), et ne jamais oublier de rendre la seconde composante.

Le test de trente secondes. Avant d'écrire la première ligne : « quand je retire ce bord, sur quoi repose ma preuve que rien d'utile ne part avec ? » Si la réponse n'est ni « le tri », ni « je majore les deux facteurs », ce n'est pas deux pointeurs.

Pièges Python — cinq lignes qui ont l'air justes
  • while l <= r au lieu de <. Sur [1, 3, 4, 6, 8, 11] et t = 8, la version large renvoie (2, 2) — l'élément 4 apparié à lui-même — alors qu'aucune paire ne somme à 8. La version stricte renvoie « aucune », qui est la bonne réponse.
  • Dédoublonner 3Sum par un set de triplets. Le résultat est juste, l'espace annoncé devient faux : O(n2) au lieu de O(1) hors sortie. Les valeurs égales sont voisines après tri — c'est un while, pas une table.
  • Oublier que sort() détruit les indices. LC 1 demande les positions d'origine : après un tri en place elles n'existent plus. Soit dictionnaire, soit tri de couples (valeur, indice) — jamais un tri nu suivi d'un retour de l et r.
  • LC 11 : bouger le plus haut « pour voir ». Prouvablement inutile, et la boucle inversée rend 8 au lieu de 49 sur le fil rouge. Un pattern qui ment ne se rattrape pas au débogage : c'est la preuve qu'il faut relire.
  • Sauter les doublons avant d'enregistrer le triplet. Dans 3Sum, l'ordre est : enregistrer, puis avancer sur les égaux, puis l += 1 ; r −= 1. Inversé, on saute la première occurrence et le triplet disparaît de la sortie.

Résumé

À retenir
  1. Signal : trié + question sur des paires ; ou, sans tri, deux facteurs qu'on sait majorer séparément (LC 11).
  2. Pattern : l = 0, r = n − 1, ils se rapprochent ; une comparaison par tour désigne le bord qui sort. Boucle l < r, strict.
  3. Élimination : s > t tue toute la colonne du bord droit, s < t toute la ligne du bord gauche. Sur le fil rouge, 5 + 4 + 3 + 2 + 1 = 15 paires en 5 comparaisons.
  4. Invariant conditionnel : si une paire de somme t existe, alors ses indices sont dans [l, r]. Variant r − l. O(n) après tri, O(1) espace.
  5. 3Sum : trier, fixer i, deux pointeurs pour −a[i] ⇒ O(n2). Doublons par while sur i, l et r — jamais par un set.
  6. LC 11 : bouger le plus bas, parce qu'il plafonne la hauteur et que la largeur ne fera que baisser. L'inverse rend 8 au lieu de 49.
  7. Non trié + somme cible ⇒ faux sans erreur : [3, 1, 4], t = 5 renvoie « aucune » alors que 1 + 4 = 5.
« Trié et une question sur des paires, donc deux pointeurs qui se rapprochent : chaque comparaison élimine un bord et tout un bloc de paires avec lui, c'est le tri qui rend l'élimination valide. Le variant est r moins l, donc linéaire ; sans tri, il faut pouvoir majorer les deux facteurs, comme dans le container. »

Chaîne verbalisée — une prise, à voix haute

4 maillons · clique pour révéler après avoir dit
  1. Pourquoi peut-on abandonner r quand a[l] + a[r] > t ?
    Parce que le tableau est trié : pour tout l′ ≥ l, a[l′] ≥ a[l], donc toutes les paires (l′, r) ont une somme ≥ a[l] + a[r] > t. Toute la colonne du bord droit r est écartée d'un coup.
  2. Énonce l'invariant et le variant.
    Invariant conditionnel : si une paire de somme t existe, ses deux indices sont dans [l, r] — les indices sortis l'ont été avec preuve. Variant : r − l, entier ≥ 0, strictement décroissant, donc au plus n − 1 tours.
  3. 3Sum : comment gérer les doublons ?
    Par des while sur les valeurs égales, pour i, pour l et pour r — les égaux sont voisins après tri. Jamais par un set de triplets : le résultat serait juste mais l'espace passerait à O(n²).
  4. LC 11 : lequel bouger, et pourquoi ?
    Le plus bas. Le garder plafonne la hauteur à sa valeur pendant que la largeur ne fait que baisser, donc toute paire qui le garde est majorée par l'aire courante. Bouger le plus haut rend 8 au lieu de 49 sur [1, 8, 6, 2, 5, 4, 8, 3, 7].