06 — Reconnaître le bon pattern
Ce que tu vas apprendre
- Les signaux qui révèlent chaque pattern
- Un arbre de décision pour choisir
- Trois problèmes résolus en identifiant le bon pattern
- Comment ces patterns se combinent
Prérequis
On a vu quatre patterns. Le vrai savoir-faire, ce n'est pas de connaître chaque algorithme isolément, c'est de reconnaître lequel s'applique en lisant l'énoncé d'un problème. Cet article rassemble les signaux et propose une méthode pour décider rapidement, au lieu de partir par défaut sur deux boucles imbriquées.
Les signaux de chaque pattern
Chaque pattern a une signature, des indices dans la formulation du problème.
Recherche dichotomique — les mots qui la trahissent :
- « le tableau est trié »
- « trouve la position de… », « la première valeur ≥ … »
- « la plus petite/grande valeur telle que [condition monotone] » (recherche sur la réponse)
Deux pointeurs — les indices :
- « tableau trié » + recherche de paires, triplets, ou somme cible
- symétrie (palindrome)
- fusion ou comparaison de deux séquences ordonnées
- modification en place sans tableau auxiliaire
Fenêtre glissante — les indices :
- « sous-tableau ou sous-chaîne contigus »
- « le plus long / le plus court / la somme maximale »
- « contenant au plus K éléments distincts », « sans répétition »
Sommes préfixes — les indices :
- « somme entre les index i et j »
- « plusieurs requêtes » sur un tableau fixe
- besoin de cumuls, de moyennes de plages
L'arbre de décision
Face à un problème de tableau, déroule ces questions dans l'ordre.
- Le tableau est-il trié, ou la réponse est-elle monotone ? Si oui, pense dichotomie (valeur, frontière, ou recherche sur la réponse).
- Cherche-t-on une paire / une symétrie / une fusion sur des données triées ? Si oui, deux pointeurs convergents ou parallèles.
- Cherche-t-on un sous-segment contigu optimal ? Si oui, fenêtre glissante (fixe ou variable).
- Doit-on répondre à plusieurs requêtes de somme sur un tableau fixe ? Si oui, sommes préfixes.
- Aucun des quatre ? Reviens aux structures de la série Complexité : un Set ou une Map résout-il le problème en O(n) par indexation ?
Cette grille couvre une grande partie des problèmes de tableaux qu'on rencontre.
Trois problèmes, trois patterns
Problème 1 : « Dans un tableau trié, combien de valeurs sont entre 10 et 50 ? » Le mot « trié » et la recherche de frontières pointent vers la dichotomie. On calcule la borne inférieure de 10 et la borne supérieure de 50, on soustrait. O(log n).
Problème 2 : « Plus longue sous-chaîne contenant au plus 2 caractères distincts. » « Sous-chaîne », « le plus long », « au plus K » : c'est une fenêtre glissante variable. On étend à droite, on rétrécit à gauche dès qu'on dépasse 2 caractères distincts. O(n).
Problème 3 : « Trois nombres du tableau somment-ils à zéro ? » On trie le tableau (O(n log n)), puis pour chaque élément fixé, on cherche une paire de somme donnée dans le reste avec deux pointeurs convergents. O(n²) au total, bien mieux que les O(n³) des trois boucles imbriquées naïves.
Combiner les patterns
Les patterns ne s'excluent pas, ils se composent souvent. Le problème 3 ci-dessus combine un tri (série précédente) et les deux pointeurs. Une recherche sur la réponse (article 02) utilise une dichotomie dont le test interne peut lui-même être une fenêtre glissante. Un problème de sous-tableau de somme cible peut se résoudre par sommes préfixes combinées à une table de hachage.
Le réflexe à construire : décomposer le problème. « Qu'est-ce que je cherche, et qu'est-ce que je sais des données ? » Les données triées appellent la dichotomie ou les deux pointeurs. Un sous-segment contigu appelle la fenêtre. Des requêtes répétées appellent le précalcul. Une fois ces réflexes installés, l'approche naïve en O(n²) cesse d'être ton point de départ par défaut.
Conclusion de la série
Ces quatre patterns partagent une idée avec toute la série Complexité : éviter de recalculer ce qu'on sait déjà. La dichotomie exploite l'ordre pour ne pas tout regarder. Les deux pointeurs exploitent une passe unique. La fenêtre glissante met à jour au lieu de recalculer. Les sommes préfixes préparent une fois pour servir mille requêtes. Reconnaître quand appliquer chacun, c'est ce qui sépare un code qui marche d'un code qui tient à l'échelle.
La suite du parcours algorithmie, la série Structures de données, construit les outils dont la série Complexité ne donnait que les coûts : piles, files, tas, arbres et union-find.
Sources
- Laakmann McDowell, G. (2015). Cracking the Coding Interview (6th ed.). CareerCup.
- Halim, S., & Halim, F. (2013). Competitive Programming 3, Chapitre 3 "Problem Solving Paradigms". Lulu.
- Skiena, S. S. (2008). The Algorithm Design Manual (2nd ed.), Chapitre 8. Springer.