- Lire une boucle Python.
for i, v in enumerate(nums)donne l'indice et la valeur ;whileavec un ou deux indices ;d[k] = vécrit,k in dteste. - Tranche demi-ouverte.
nums[a:b]contient les indices a, a+1, …, b−1 : la borne droite est exclue. On la note [a:b) et on dit « exclue » à voix haute. - O(·) comme ordre de grandeur. O(f(n)) = « borné par c·f(n) pour n assez grand ». On compare des ordres, on ne compte pas les constantes.
- Dictionnaire et ensemble. Test d'appartenance et insertion en O(1) amorti (table de hachage) ; le même test sur une liste est en O(n). La différence porte toute la complexité du fil rouge.
La chaîne
Le rituel : cinq cases, dans l'ordre tronc
Devant un énoncé, on ne code pas d'abord. On remplit cinq cases : signal (ce que la phrase impose), pattern (la structure qui répond au signal), squelette (les lignes de contrôle, pas le corps), TAP, trace (l'exemple déroulé, invariant affiché).
Les quatre lettres du TAP ne sont pas un ordre d'écriture, c'est un ordre de preuve : l'invariant dit ce qui est vrai, le variant dit qu'on s'arrête, la conclusion branche l'un sur l'autre, la complexité chiffre le prix.
« L'énoncé donne un signal, donc le signal donne un pattern, donc le pattern donne un squelette, donc le squelette se défend par quatre phrases et se vérifie sur une trace. »
Signal. « Deux éléments », « somme égale à une cible », « renvoyer les indices », tableau non trié. Le mot « indices » interdit de trier ; « deux éléments » appelle un complément.
Pattern. Un seul passage + un dictionnaire valeur → indice des déjà vus. On échange de la mémoire contre du temps.
Squelette — les lignes de contrôle seulement :
seen est le conteneur de l'invariant, n − i est le variant, et seen[v] = i est la ligne qui préserve l'invariant. Deux sorties — par renvoyer ou par épuisement — donc deux conclusions (pas 4).
L'invariant : conteneur, tranche, « exactement » tronc
Un invariant est une propriété inductive : vraie avant le premier tour, préservée par un tour quelconque. Trois exigences de formulation, sans quoi il n'est pas démontrable :
Sans « exactement », « seen contient les valeurs de nums[0:i) » est encore vrai si seen contient tout le tableau — l'invariant ne sert plus à rien. Et « seen contient ce qu'on a vu » n'est pas un invariant du tout : aucun énoncé, donc aucune conclusion.
« L'invariant est vrai avant le premier tour et préservé par un tour, donc il est vrai à l'entrée de chaque tour, donc il l'est encore à la sortie — et c'est cette dernière instance qui sert de preuve. »
À l'entrée du tour i (indice courant exclu) :
I1. seen contient exactement les valeurs de nums[0:i), chacune associée à son dernier indice.
I2. Aucune paire (j, k) avec k < i ne somme à target.
Initialisation : i = 0, nums[0:0) est vide et seen = {} — I1 et I2 tiennent. Préservation : le tour i teste toutes les paires (·, i) d'un coup, puis écrit seen[v] = i ; la tranche passe de [0:i) à [0:i+1).
Vérifié à l'exécution sur 20 000 entrées aléatoires (longueurs 0 à 7, doublons compris) : I1 et I2 tiennent à l'entrée de chaque tour, sans exception.
Le « dernier indice » n'est pas un détail. Avec un doublon, seen[v] = i écrase l'entrée précédente. La paire renvoyée reste valide et son k reste le premier qui ferme une paire, mais son j n'est pas forcément le plus petit — sur les mêmes 20 000 tirages, 358 cas où j diffère de la force brute. Un énoncé qui exige la première paire exige un autre invariant, donc un autre code.
Two Sum sur nums = [2, 7, 11, 15], target = 9, quatre images. Le pointeur est i ; les cases ambrées sont celles dont la valeur est dans seen ; la dernière image encadre en vert la paire renvoyée. La ligne du bas est l'invariant, réécrit à chaque image : il se lit à chaque tour, pas seulement à la fin. Fais « pas › » et dis l'invariant avant de le lire.
Le variant : l'entier qui décroît
Le variant est un entier, ≥ 0, qui décroît strictement à chaque tour. Les trois conditions ensemble interdisent une suite infinie de tours : un entier positif ne peut décroître qu'un nombre fini de fois.
S'il n'existe pas, la boucle peut ne pas terminer — et c'est le seul endroit où une boucle infinie se cache. L'écrire force à vérifier que chaque branche du corps le fait décroître.
« Le variant est un entier positif qui décroît strictement à chaque tour, donc la suite des tours est finie, donc la boucle termine — et sans variant, on n'a rien dit sur la terminaison. »
| boucle | variant | décroît : à chaque tour… |
|---|---|---|
for i in range(n) | n − i | i augmente de 1 |
| fenêtre glissante (l, r avancent) | (n−r) + (n−l) | on avance l ou r |
| deux pointeurs qui se croisent | r − l | l monte ou r descend |
| dichotomie | hi − lo | l'intervalle est coupé au moins en deux |
| BFS / DFS | sommets non visités | un dépilement marque un sommet neuf |
Two Sum : n − i vaut 4, 3, 2, 1 aux tours 0 à 3 — entier, positif, −1 par tour. Le fil rouge renvoie au tour 1 ; le variant garantit juste qu'on ne peut pas dépasser 4 tours.
Le piège du while. Si une branche du corps ne bouge ni l ni r, le variant ne décroît pas et la boucle tourne pour toujours. C'est là, et nulle part ailleurs, que se cachent les boucles infinies de deux pointeurs et de dichotomie.
La conclusion : « donc », sur le résultat
La conclusion commence par donc et porte sur le résultat, pas sur le déroulement. « donc on a parcouru tout le tableau » est vrai et inutile : personne n'en doutait, et ça ne dit pas pourquoi la réponse est juste.
Le variant dit où la boucle s'arrête, l'invariant dit ce qui est vrai à cet endroit : leur conjonction est l'énoncé du problème. Deux sorties ⇒ deux conclusions : la sortie par renvoyer et la sortie par épuisement.
« Le variant donne la valeur finale de l'indice, donc l'invariant instancié à cette valeur est vrai, donc il dit exactement ce que le problème demandait — la conclusion porte sur le résultat, pas sur le parcours. »
Sortie par renvoyer, au tour i = k. I1 dit que seen contient exactement les valeurs de nums[0:k) avec leur indice ; le test qui vient de réussir dit que target − nums[k] y est, à un indice j < k. Donc nums[j] + nums[k] = target avec j < k : la paire renvoyée est valide.
Sortie par épuisement, i = n (variant nul). I2 sur [0:n) dit qu'aucune paire ne somme à target. Donc None est la bonne réponse.
Complétude. Si une paire (j, k) existe, au tour i = k son complément est dans seen par I1, donc la boucle ne peut pas atteindre i = n sans avoir renvoyé. Confronté à une force brute sur les 20 000 tirages : même existence, même k, paire toujours valide.
À ne pas dire : « donc on a parcouru tout le tableau ». C'est le déroulement.
La complexité : composée, pas devinée tronc
On ne devine pas une complexité, on la compose. Hors boucle, les coûts s'ajoutent ; dans une boucle, le coût du corps se multiplie par le nombre de tours — que le variant a déjà donné.
Un coût amorti se justifie (« chaque élément entre et sort au plus une fois »), il ne se décrète pas. L'espace se donne en fonction de la taille de l'entrée, jamais en valeur d'exécution : « 4 entrées » n'est pas une complexité, min(n, |Σ|) en est une.
« Le nombre de tours vient du variant et le coût du corps se lit ligne à ligne, donc le total est leur produit augmenté des coûts hors boucle, donc la complexité se compose au lieu de se deviner. »
Temps. n tours (variant n − i) ; corps = un test d'appartenance + une insertion dans un dict, O(1) amorti chacun. Donc n × O(1) = O(n).
Le même squelette avec une liste de vus : le test parcourt les vus, coût i au tour i, donc Σi = n(n−1)/2 = O(n²). Une boucle, deux complexités : c'est le corps qui décide, jamais le nombre de boucles.
Opérations comptées exactement sur le code instrumenté, pire cas (aucune paire, la boucle va au bout) :
| n | dict — 2n | liste — n(n−1)/2 + 2n |
|---|---|---|
| 10 | 20 | 65 |
| 100 | 200 | 5 150 |
| 1 000 | 2 000 | 501 500 |
Espace. seen a au plus une entrée par valeur distincte rencontrée, donc O(min(n, |valeurs distinctes|)). Sur le fil rouge il finit à 1 entrée : c'est une valeur d'exécution, pas une complexité. Les autres formes utiles : O(h) pour la pile de récursion sur un arbre de hauteur h, O(n) pour un set de vus, O(1) pour deux pointeurs.
Opérations élémentaires comptées sur les deux versions du même squelette, pire cas : dict (2n) et liste (n(n−1)/2 + 2n). Déplace n : la courbe du dict reste collée à l'axe. Le nombre de boucles est le même dans les deux cas — seul le coût du corps change, et c'est lui qui fait passer de O(n) à O(n²).
Où le TAP se rate casse
Chacune de ces erreurs produit une réponse qui sonne juste et ne prouve rien. C'est exactement ce que l'interlocuteur écoute : pas si tu sais coder Two Sum, mais si ce que tu dis démontre quelque chose.
« Un invariant sans conteneur ni tranche n'est pas démontrable, une conclusion sur le déroulement ne porte pas sur le résultat, une complexité devinée ignore le coût du corps, donc la réponse sonne juste et ne prouve rien. »
- Invariant sans conteneur ni tranche. « On a vu les éléments » : rien à initialiser, rien à préserver, rien à instancier à la sortie. Indémontrable, donc faux.
- Conclusion sur le déroulement. « On a tout parcouru » : vrai, et sans rapport avec la justesse du résultat.
- Espace en valeur d'exécution. « 4 entrées » au lieu de min(n, |valeurs distinctes|) : un nombre au lieu d'une fonction de n.
- Complexité devinée. « O(n) parce qu'il y a une boucle » — sans lire le corps. Un
insur une liste dans la boucle donne O(n²) avec exactement la même boucle. - Variant oublié sur un
while. Deux pointeurs, dichotomie : sans variant, rien ne dit que la boucle s'arrête, et c'est là que la boucle infinie attend.
inne dit pas sa structure.x in vuscoûte O(1) amorti sivusest unsetou undict, O(n) si c'est unelist. La ligne est la même, la complexité de la boucle ne l'est pas.- Muter ce qu'on itère.
for x in a: a.remove(x)casse l'invariant : la tranche parcourue n'est plus celle qu'on croit. Itérer sur une copie, ou construire une nouvelle liste. d[k],d.get(k),k in d: trois lignes, trois invariants. La première lèveKeyError, la deuxième renvoieNone— etNonepeut être une valeur légitime, auquel casd.get(k) is Nonene veut pas dire « absent ».defaultdictinsère à la lecture. Lired[k]crée l'entrée : l'invariant «dcontient exactement les clés vues » devient faux sans qu'aucune ligne d'écriture n'apparaisse.//et le milieu.mid = (lo + hi) // 2ne déborde pas en Python (entiers non bornés), mais garderlo + (hi − lo) // 2transporte l'habitude aux langages où il déborde — et c'est la même ligne qu'on écrit en entretien Java ou C++.enumerateplutôt querange(len(...)). Le TAP est identique ; les occasions de se tromper d'indice sont doublées dans la seconde forme, et un invariant faux sur un indice ne se voit pas à la relecture.
Le même rituel, neuf familles
Ce qui change d'une famille à l'autre est le conteneur de l'invariant et la forme du variant. Le rituel, lui, ne change pas : c'est cette sheet, neuf fois.
Apprendre le coding, c'est donc apprendre à lire le signal dans l'énoncé — les trois ou quatre mots qui nomment le pattern — pas à mémoriser du code.
« Le signal de l'énoncé nomme le pattern, donc le pattern fixe le conteneur de l'invariant et la forme du variant, donc les quatre phrases s'écrivent avant la première ligne de code. »
| signal dans l'énoncé | pattern | conteneur de l'invariant | variant |
|---|---|---|---|
| « sous-tableau contigu », « au plus k … » | c01 · fenêtre glissante | la fenêtre [l:r) et son agrégat | (n−r) + (n−l) |
| « trié », « une paire », « sans mémoire auxiliaire » | c02 · deux pointeurs | le segment [l:r] encore possible | r − l |
| « trié », « le premier indice tel que » | c03 · dichotomie | [lo:hi) contient la réponse | hi − lo |
| « en place », « inverser », « cycle » | c04 · listes chaînées | le préfixe déjà retourné | nœuds non visités |
| « sous-arbre », « profondeur », « BST » | c05 · arbres | le chemin racine → nœud, la pile d'appels | nœuds non visités |
| « composantes », « plus court en nombre d'arêtes » | c06 · graphes | l'ensemble des visités | sommets non visités |
| « les k plus grands », « un flux » | c07 · tas | le tas des k meilleurs de [0:i) | n − i |
| « fusionner », « chevauchement » | c08 · intervalles | les fusionnés de [0:i), triés | n − i |
| « nombre de façons », « maximum sur des choix » | c09 · DP 1D | dp[0:i) = réponse sur chaque préfixe | n − i |
Trois variants sur neuf sont n − i : la boucle simple est la forme par défaut, et les six autres lignes sont exactement les cas où elle ne suffit pas.
Résumé
- Un problème n'est fini que quand quatre phrases sont dites : invariant, variant, conclusion, complexité.
- Invariant : inductif (vrai avant, préservé par un tour), conteneur nommé, tranche en indices demi-ouverts, le mot « exactement ».
- Variant : un entier ≥ 0 qui décroît strictement. Sans lui, rien n'a été dit sur la terminaison.
- Conclusion : commence par « donc », porte sur le résultat, = l'invariant instancié à la valeur finale du variant. Une conclusion par sortie.
- Complexité : + hors boucle, × dans la boucle, amortissement justifié. C'est le coût du corps qui décide, pas le nombre de boucles.
- Espace en fonction de la taille de l'entrée — min(n, |Σ|), O(h), O(n) — jamais en valeur d'exécution.
- D'une famille à l'autre, seuls changent le conteneur de l'invariant et la forme du variant. Le rituel est le même neuf fois.
Chaîne verbalisée — une prise, à voix haute
- Énonce l'invariant de Two Sum.À l'entrée du tour i : seen contient exactement les valeurs de nums[0:i), chacune avec son dernier indice ; et aucune paire (j, k) avec k < i ne somme à target.
- Le variant ?n − i : entier, ≥ 0, décroît de 1 à chaque tour, donc la boucle termine en au plus n tours.
- La conclusion, en commençant par donc.Donc au tour k le complément de la paire est dans seen, donc elle est renvoyée ; et si la boucle finit, l'invariant sur [0:n) dit qu'aucune paire n'existe, donc None.
- La complexité, composée.n tours × O(1) par tour (test + insertion dans un dict) = O(n) en temps ; espace O(min(n, |valeurs distinctes|)). Avec une liste au lieu du dict : Σi = n(n−1)/2, donc O(n²).
- Ton invariant tient-il avec des doublons ?Oui — c'est pour ça que I1 dit « son dernier indice » : seen[v] = i écrase. La paire renvoyée reste valide et son k est le premier qui ferme, mais son j n'est pas forcément le plus petit.
Ponts et cartes
coding::tap (les quatre phrases et leur ordre) · coding::invariant (conteneur, tranche demi-ouverte, « exactement », initialisation / préservation) · coding::complexite (composition + hors boucle, × dans la boucle, amortissement, espace en fonction de n).
Une carte qui résiste après cette chaîne est une carte à refondre, pas une section à relire.