Fil rouge : LC 209 (plus court sous-tableau de somme ≥ target), LC 424 (plus longue tranche avec au plus k remplacements), Number of Islands, 3Sum et le conteneur d'eau. Chaque problème raté devient une paire signal → pattern.
Fenêtre glissante
QSignal : « sous-tableau contigu de longueur exactement k ». Pattern et gain exact ?›
Fenêtre fixe : on maintient l'agrégat de la tranche courante et on le met à jour en O(1) : + nums[i] − nums[i − k]. O(n) au lieu de O(nk). Ce qui rend la mise à jour possible : l'entrant et le sortant sont déterminés par le décalage.
« Deux tranches consécutives ne diffèrent que d'un élément entrant et d'un sortant, donc l'agrégat se corrige en O(1), donc le balayage est linéaire. »
QFenêtre fixe, moyenne à renvoyer : accumuler la somme en int ou la moyenne en float ?›
En int, deux raisons indépendantes : (1) les int Python sont exacts, l'erreur est nulle, pas seulement petite ; (2) la moyenne est somme/k avec k fixe > 0, fonction strictement croissante, donc maximiser la somme = maximiser la moyenne. On divise une seule fois à la fin.
« k est fixe et positif, donc l'ordre des sommes est l'ordre des moyennes, donc on compare des entiers exacts et on ne divise qu'à la fin. »
QSignal : longueur du plus court (ou plus long) sous-tableau contigu vérifiant une contrainte monotone. Pattern ?›
Fenêtre glissante à deux pointeurs : d explore inconditionnellement (une fois par tour externe), g avance tant que la contrainte le permet (while interne). Chaque pointeur ne fait que croître → O(n). Condition : la contrainte est monotone en l'extension de la fenêtre.
LC 209 : plus court sous-tableau de somme ≥ target, valeurs positives — étendre ne peut qu'augmenter la somme, donc rétrécir tant que ça reste ≥ target.
« La contrainte est monotone en la longueur, donc quand elle est satisfaite on rétrécit et quand elle ne l'est plus on étend, donc chaque pointeur avance au plus n fois. »
QFenêtre sur une chaîne à alphabet fixé Σ, coût demandé en O(n) : qu'est-ce qui change ?›
Il faut une structure de comptage (tableau de |Σ| cases), donc un invariant supplémentaire qui la verrouille sur la tranche courante : « count[c] = nombre de c dans s[g:d] ». Espace O(|Σ|) = O(1). La condition d'admissibilité se lit sur le compteur (LC 424 : longueur − max(count) ≤ k).
« La contrainte porte sur des effectifs, donc on les maintient incrémentalement, donc l'invariant doit inclure l'état du compteur, sinon la preuve ne tient pas. »
QPlus longue tranche admissible : deux invariants sur res et sur la fenêtre. Pourquoi celui sur res ne suffit-il pas ?›
L'invariant sur res énonce ce qu'on veut prouver (« res = longueur max parmi les tranches vues ») ; il ne garantit pas que res a été mis à jour au bon moment. Il faut l'invariant sur la fenêtre elle-même : s[g:d] est admissible (ou l'est après rétrécissement), et il n'existe pas de tranche admissible plus longue finissant en d.
g = 5, d = 9 avec s[3:9] admissible non vue : sans la clause sur la fenêtre, res rate cette tranche.
« Un invariant qui ne parle que du résultat n'est pas inductif, donc il faut un invariant sur la fenêtre courante, donc la clause d'optimalité locale. »
QQuelle clause de l'invariant autorise à ne balayer qu'une fenêtre par position finale ?›
L'optimalité locale ancrée à droite : « la fenêtre courante est la plus longue fenêtre valide terminant en d ». Sans elle, un programme qui vide la fenêtre à chaque violation reste correct mais O(n²). Même clause dans Kadane, LC 209, LC 424, LC 76.
« Si la fenêtre est optimale parmi celles qui finissent en d, donc en avançant d on ne perd aucun candidat, donc on n'a jamais à revenir en arrière. »
Deux pointeurs
QTableau trié, l et r aux extrémités, somme < target. Pourquoi l += 1 est-il sûr ?›
l += 1 élimine définitivement toutes les paires contenant l : nums[l] + nums[j] ≤ nums[l] + nums[r] < target pour tout j ≤ r. Aucune de ces paires ne peut être solution. Le tri est ce qui rend l'élimination valide.
« r est le plus grand disponible, donc si nums[l] + nums[r] est trop petit, aucun partenaire de l ne suffit, donc l peut avancer sans perdre de solution. »
QTriplets de somme nulle sans doublons (3Sum) : quel pattern ?›
Trier, puis boucle externe qui fixe le premier élément et applique 2Sum II (two pointers) sur le suffixe. O(n²). Sauter les valeurs égales à la précédente en externe et en interne pour éviter les doublons.
« Fixer un élément ramène à 2Sum sur un tableau trié, donc deux pointeurs en O(n), donc n fois O(n) = O(n²). »
QDeux pointeurs sur un tableau trié avec doublons : comment sauter, et if ou while ?›
Avancer puis regarder derrière : l += 1, puis while l < r and nums[l] == nums[l−1]: l += 1. while, pas if : un if ne franchit qu'une copie, or le bloc de doublons peut être de longueur quelconque. Garder la borne l < r dans le while.
« Un bloc de doublons a une longueur arbitraire, donc un if ne suffit pas, donc on boucle tant que la valeur est égale à la précédente. »
QDeux pointeurs sans tri, quantité gouvernée par min(hg, hd) × largeur (conteneur d'eau) : sur quoi repose l'élimination ?›
Pas sur une monotonie — il n'y en a pas. On majore les deux facteurs séparément : si hg ≤ hd, pour tout k entre g et d, min(hg, hk) ≤ hg et (k − g) < (d − g), donc aire(g, k) ≤ aire(g, d). Toute fenêtre gardant g est dominée → g += 1.
« Le côté le plus bas plafonne la hauteur et rétrécir réduit la largeur, donc toute fenêtre gardant ce côté est dominée, donc on peut l'abandonner. »
Graphes sur grille — DFS, BFS
QSignal : grille 2D, compter ou mesurer des régions connexes. Pattern ?›
Flood fill : double boucle sur toutes les cases ; sur chaque case-source non visitée, lancer un DFS/BFS qui marque toute la région ; compter les lancements. O(m·n) : chaque case est visitée une fois.
« Chaque lancement épuise une composante entière, donc le nombre de lancements est le nombre de composantes, donc une double boucle plus un parcours suffit. »
QDFS et BFS sont tous deux corrects pour une région connexe. Quand l'un s'impose-t-il ?›
(1) Plus court chemin / distance minimale → BFS obligatoire : il explore par couches de distance croissante. (2) Grille très grande → BFS itératif évite la RecursionError du DFS récursif. (3) Chemin ou backtracking → DFS naturel.
« BFS traite les cases par distance croissante, donc la première visite est la plus courte, donc dès qu'on demande une distance on prend BFS. »
QDans un DFS, pourquoi marquer une case visitée AVANT l'appel récursif ?›
Sinon deux appels peuvent partir sur la même case avant qu'elle soit marquée → boucle infinie (A → B → A → …). Marquer d'abord, explorer ensuite.
« L'appel récursif peut revenir sur la case courante, donc si elle n'est pas encore marquée il repart, donc on marque avant de descendre. »
QEn BFS, la file gonfle de doublons et des cases sont traitées plusieurs fois. Quel est le bug ?›
Les cases sont marquées visitées au défilement (popleft) au lieu de l'enfilement (append). Entre les deux, plusieurs voisins l'enfilent. Règle : marquer quand on enfile.
« Entre l'enfilement et le défilement, d'autres voisins voient la case non marquée, donc ils l'enfilent aussi, donc on marque à l'enfilement. »
QDistances en BFS : quand traiter niveau par niveau (figer len(queue)) plutôt qu'avec un dist par case ?›
Quand la question porte sur le niveau comme un tout : combien de cases à distance d, nombre de « minutes » (Rotting Oranges), largeur d'un niveau. Un dist par case suffit si on veut la distance de chaque case.
« Figer la taille de la file isole un niveau complet, donc on sait quand il est fini, donc on peut compter les niveaux ou agir par niveau. »
QMarquer visited in-place (muter la grille) ou set séparé ?›
In-place évite O(m·n) d'espace supplémentaire. Trade-off : ça mute l'input, à éviter si le problème l'interdit ou si la grille est réutilisée. Number of Islands : écrire '0' « noie » l'île, le '0' joue le rôle de visited.
« La grille a déjà une case par position, donc y écrire un marqueur coûte zéro mémoire, donc on le fait sauf si l'input doit rester intact. »
QPourquoi deque et non list pour une file BFS ? Et jusqu'où va un DFS récursif ?›
list.pop(0) décale tous les éléments : O(n) ; deque.popleft() est O(1). Un DFS récursif lève RecursionError vers 1 000 de profondeur : la profondeur est la longueur du chemin DFS le plus long, pas le nombre de cases — une grille 100×100 en serpentin la dépasse.
« Une file demande des retraits en tête en O(1), donc deque ; la pile d'appels est bornée, donc un DFS profond doit être itératif. »
Preuves de boucle — invariant, variant
QInvariant et variant : que prouve chacun ?›
Invariant = propriété vraie avant et après chaque itération → prouve la correction (à la sortie, invariant + condition de sortie = résultat). Variant = quantité entière minorée par 0 et strictement décroissante → prouve la terminaison.
« L'invariant survit à chaque tour, donc il est vrai à la sortie, donc combiné à la condition d'arrêt il donne le résultat ; le variant décroît strictement dans les entiers positifs, donc la boucle s'arrête. »
QUn variant doit vérifier deux propriétés. Lesquelles, et pourquoi les deux ?›
Entier, minoré par 0 et strictement décroissant à chaque tour. Minoré seul : peut décroître à l'infini dans les réels. Décroissant seul : peut décroître de moins en moins sans jamais s'arrêter. Deux pointeurs : variant d − g.
« Une suite d'entiers strictement décroissante et positive est finie, donc les deux conditions ensemble bornent le nombre de tours, donc l'une sans l'autre ne prouve rien. »
QQu'est-ce qui distingue un invariant d'un simple corollaire ?›
Un invariant doit être inductif : il doit suffire à démontrer son propre pas. Il mentionne donc tout l'état qui intervient dans la mise à jour (compteurs, pointeurs, résultat). Test : « puis-je prouver le pas à partir de mon seul énoncé ? » Si non, il manque une clause.
« Un corollaire découle de l'état mais ne le décrit pas, donc on ne peut pas le repropager au tour suivant, donc il ne prouve rien seul. »
Complexité et heuristiques
QTri en O(n log n) puis double boucle en O(n²) : complexité totale ?›
O(n²). Un coût hors boucle s'additionne, il ne se multiplie pas : O(n log n) + n·O(n) = O(n²). Règle de composition : hors boucle → « + », dans la boucle → « × ».
« Le tri se fait une fois avant la boucle, donc son coût s'ajoute, donc le terme dominant est n². »
QUn for sur n éléments contient un while qui peut tourner longtemps. Quelle analyse, et que compte-t-on ?›
Analyse amortie (agrégée) : on ne borne pas le while par tour, on compte le nombre total d'exécutions de son corps sur toute la boucle. Si chaque exécution consomme une ressource bornée (un pointeur qui n'avance que n fois), le total est O(n).
« Chaque tour du while fait avancer un pointeur qui ne recule jamais, donc le corps s'exécute au plus n fois au total, donc la boucle est linéaire malgré le while imbriqué. »
QSet ou dict indexant des caractères d'un alphabet fixé : espace ?›
O(|Σ|) = O(1), borne exacte min(n, |Σ|). Piège : répondre avec une valeur d'exécution (« 5 clés ») au lieu d'une borne.
« Il n'y a que |Σ| clés possibles, donc la structure ne dépasse jamais |Σ|, donc l'espace est constant quel que soit n. »
QTa solution s'appuie sur une propriété globale (min, max, ordre trié). Comment l'optimiser ?›
Chercher la reformulation locale : un test en O(1) sur un élément isolé qui ne demande ni tri ni parcours préalable. Exemple : « x est le début d'une suite » ⟺ « x − 1 n'est pas dans le set ».
« Une propriété globale coûte un parcours, donc on cherche une condition locale équivalente, donc on la teste en O(1) par élément. »
QTableau non trié, question sur des valeurs consécutives, O(n) imposé : pattern ?›
Charger dans un hash set, puis ne lancer le comptage d'une suite que depuis les x tels que x − 1 ∉ set, et itérer sur le set, pas sur le tableau : sans dédoublonnage, un tableau de n copies relance n fois le même comptage et la borne O(n) tombe.
« Chaque suite n'est comptée qu'une fois depuis son début, donc chaque élément est parcouru une fois, donc O(n) — à condition d'itérer sur des valeurs uniques. »
QTop-k par min-heap de taille k : que représente le min du heap ?›
Le seuil d'entrée, le plus faible des k admis. Contre-intuitif : un min-heap sert à garder les plus grands, parce que le seul élément qu'on doit pouvoir éjecter est le plus petit. O(n log k).
« Pour garder les k plus grands il faut éjecter le plus petit des gardés, donc c'est lui qu'on veut en O(1) au sommet, donc un min-heap. »
QSignal : top-k ou k plus fréquents, valeurs de tri entières bornées (fréquences ≤ n) : pattern ?›
Bucket sort : l'indice est la fréquence, aucun tri. On range chaque valeur dans bucket[fréquence] puis on lit les buckets de n vers 0. O(n).
« Les clés de tri sont des entiers entre 0 et n, donc on les utilise comme adresses, donc on lit dans l'ordre des adresses sans comparer. »
QSérialiser une liste de strings arbitraires en une seule string, sans délimiteur sûr ?›
Préfixe de longueur : encoder chaque string en len(s)#s. Au décodage, lire les chiffres jusqu'au #, puis exactement len caractères. Aucun caractère n'est interdit dans s.
« Un délimiteur peut apparaître dans les données, donc on annonce la longueur avant, donc le décodeur sait où s'arrêter sans jamais interpréter le contenu. »
Pièges Python qui cassent un code juste
QDifférence entre [0] * n et [[]] * n ?›
[0] * n est sûr : 0 est immuable, réaffecter une case rebind cette case. [[]] * n crée n références à la même liste : append sur l'une remplit toutes. Correct : [[] for _ in range(n)].
« La multiplication copie des références, donc n objets mutables identiques, donc toute mutation est partagée. »
Qnums[-1] sur une liste non vide : que se passe-t-il, et pourquoi c'est un bug muet ?›
Aucune erreur : il lit le dernier élément. Un indice i − 1 qui vaut −1 (i = 0) compare contre la mauvaise case sans crash — le bug est silencieux.
« Python interprète l'indice négatif comme un accès par la fin, donc un off-by-one ne plante pas, donc on garde i ≥ 1 comme condition explicite. »
QSommer ou agréger sans matérialiser de liste intermédiaire ?›
Passer un générateur : sum(f(x) for x in xs), sans crochets. Les crochets construisent toute la liste en mémoire avant de sommer ; le générateur produit les valeurs à la volée. O(1) espace au lieu de O(n).
« sum consomme un itérable élément par élément, donc il n'a pas besoin de la liste entière, donc un générateur suffit et n'alloue rien. »