Algorithmes Classiques

Two Sum, Anagrammes, Compteur de Fréquence

Utilisez les flèches, cliquez ou glissez pour naviguer

Objectifs de la leçon

1. Appliquer le pattern compteur de fréquence

Un pattern réutilisable dans de nombreux problèmes

2. Résoudre Two Sum en O(n)

Passer de O(n²) à O(n) avec un objet

3. Décomposer un problème algorithmique

D'abord simple, puis optimiser

4. Choisir la bonne structure de données

Objet, Map, Set selon le besoin

Plan du cours

1

Récap de la semaine

Complexité, recherche, tri, récursion

2

Two Sum

Trouver deux nombres qui font une somme cible

3

Anagrammes

Détecter si deux mots sont des anagrammes

4

Le compteur de fréquence

Un pattern fondamental avec .reduce() ou objet

5

Projet : Résoudre des classiques

Combiner les techniques apprises

Récap de la semaine

Complexité

O(1), O(n), O(n²), O(log n)

Recherche

Linéaire vs Binaire

Tri

Bulles, Sélection

Récursion

Cas de base, cas récursif

Pourquoi c'est important ?

Ces concepts sont les briques des algorithmes classiques

Two Sum

Utilise la recherche et la complexité

Anagrammes

Utilise le tri ou le compteur

Compteur de fréquence

Pattern réutilisable

Plus longue sous-chaîne

Combine tous les concepts

💡 Aujourd'hui, on combine tout ça pour résoudre des problèmes classiques!

Problème classique : Two Sum

Trouver deux nombres qui font une somme cible

Étant donné un tableau [2, 7, 11, 15]

Et une cible 9

Trouver les indices des deux nombres

Réponse : [0, 1] car 2 + 7 = 9

Approche 1 : Brute Force

⚠️ On commence TOUJOURS par la solution simple!

function twoSum(nums, target) {

for (let i = 0; i < nums.length; i++) {

for (let j = i + 1; j < nums.length; j++) {

if (nums[i] + nums[j] === target) {

return [i, j];

}

}

}

}

💡 Pour chaque nombre, on teste avec tous les autres

Complexité : O(n²)

Deux boucles imbriquées = n × n comparaisons

10 éléments

100

comparaisons

100 éléments

10 000

comparaisons

1000 éléments

1 000 000

comparaisons

⚠️ Ça explose rapidement! Peut-on faire mieux?

L'astuce : Le complément

Si je cherche 9

Et que j'ai 2

Il me manque 9 - 2 = 7

Le complément de 2 est 7

Si je trouve 7 quelque part → j'ai ma paire!

Approche 2 : Objet pour les compléments

Stocker les nombres déjà vus dans un objet

Pour chaque nombre, vérifier si son complément existe déjà

function twoSum(nums, target) {

const seen = {};

for (let i = 0; i < nums.length; i++) {

const complement = target - nums[i];

if (complement in seen) {

return [seen[complement], i];

}

seen[nums[i]] = i;

}

}

✅ Un seul parcours = O(n)!

Visualisation : target = 9

Tableau : [2, 7, 11, 15]

Étape 1 : i = 0, nums[0] = 2

complément = 9 - 2 = 7 → 7 n'est pas dans seen → seen = {2: 0}

Étape 2 : i = 1, nums[1] = 7

complément = 9 - 7 = 2 → 2 est dans seen!

→ Retourne [0, 1] ✓

Comparaison : Brute Force vs Optimisé

Brute Force

O(n²)

100 éléments → 10 000 ops

1000 éléments → 1 000 000 ops

Deux boucles imbriquées

Optimisé

O(n)

100 éléments → 100 ops

1000 éléments → 1000 ops

Un seul parcours + objet

Pour 1000 éléments : 1000x plus rapide!

Problème classique : Anagrammes

Deux mots avec les mêmes lettres réarrangées

listen

↕️

silent

race

↕️

care

Approche 1 : Trier les lettres

Si deux mots sont des anagrammes, leurs lettres triées sont identiques

function isAnagram(str1, str2) {

const sorted1 = str1.split('').sort().join('');

const sorted2 = str2.split('').sort().join('');

return sorted1 === sorted2;

}

listen → eilnst

silent → eilnst

Complexité : O(n log n) à cause du tri

Approche 2 : Compteur de fréquence

Compter combien de fois chaque lettre apparaît

function isAnagram(str1, str2) {

if (str1.length !== str2.length) return false;

const count = {};

for (const char of str1) {

count[char] = (count[char] || 0) + 1;

}

for (const char of str2) {

if (!count[char]) return false;

count[char]--;

}

return true;

}

Complexité : O(n) — Un seul parcours par mot!

⚠️ Piège : Normalisation

Les espaces et majuscules faussent le résultat!

"Listen" ≠ "silent"

Majuscule différente

"dormitory" ≠ "dirty room"

Espace en plus

✅ Solution : Normaliser avant de comparer

const normalize = str => str.toLowerCase().replace(/\s/g, '');

Comparaison des approches

Approche	Complexité	Avantages
Trier les lettres	O(n log n)	Code simple, une ligne
Compteur de fréquence	O(n)	Plus rapide, pattern réutilisable

💡 Le compteur de fréquence est le pattern à retenir!

Le compteur de fréquence

Un pattern fondamental et réutilisable

Compter combien de fois chaque élément apparaît

// Exemple

['a', 'b', 'a', 'c', 'b', 'a']

→ { a: 3, b: 2, c: 1 }

Implémentation avec .reduce()

function frequencyCounter(arr) {

return arr.reduce((acc, val) => {

acc[val] = (acc[val] || 0) + 1;

return acc;

}, {});

}

💡 reduce accumule les comptes dans un objet

Exemple d'utilisation :

frequencyCounter(['a', 'b', 'a', 'c']);

// → { a: 2, b: 1, c: 1 }

Implémentation avec boucle for...of

function frequencyCounter(arr) {

const count = {};

for (const val of arr) {

count[val] = (count[val] || 0) + 1;

}

return count;

}

💡 Plus lisible pour les débutants, même complexité O(n)

Quand utiliser ce pattern ?

✅ Anagrammes

Comparer les fréquences des lettres

✅ Trouver les doublons

Fréquence > 1 = doublon

✅ Caractères uniques

Fréquence = 1 pour tous

✅ Two Sum

Stocker les nombres vus

🎯 Ce pattern revient PARTOUT dans les entretiens techniques!

La démarche recommandée

1️⃣

Brute force d'abord

Solution simple, même si lente

2️⃣

Analyser la complexité

Identifier les goulots d'étranglement

3️⃣

Optimiser

Meilleure structure de données

Pièges courants à éviter

❌ Vouloir la solution optimale directement

✅ Commencer par brute force, puis optimiser

❌ Ne pas comprendre le "complément" dans Two Sum

✅ Visualiser : target - current = ce qu'on cherche

❌ Oublier de normaliser les anagrammes

✅ toLowerCase() + remove spaces

Points clés à retenir

Two Sum : O(n²) → O(n) avec un objet

Stocker les compléments déjà vus

Anagrammes : Trier O(n log n) ou Compter O(n)

Penser à normaliser (espaces, majuscules)

Compteur de fréquence = Pattern réutilisable

Doublons, anagrammes, caractères uniques...

Démarche : Brute force → Analyser → Optimiser

Ne pas chercher la solution parfaite du premier coup

À retenir!

Two Sum

Objet pour les compléments

O(n)

Anagrammes

Compter les fréquences

O(n)

Compteur de fréquence

Le pattern à maîtriser absolument!

Exercices pratiques

1. Two Sum

Implémenter les deux versions et comparer

2. Détecter les anagrammes

Avec tri ET avec compteur de fréquence

3. Trouver les doublons

Utiliser le compteur de fréquence

4. Plus longue sous-chaîne sans répétition

Combiner Set + sliding window

Questions?

Les algorithmes classiques sont la base de l'algorithmique

Maîtrisez le compteur de fréquence

Et vous résoudrez 50% des problèmes d'entretien!