19 — Corrections détaillées : solutions multi-langages

Ce chapitre fournit les corrigés des exercices du chapitre 17. Chaque corrigé suit le même format : problème, approche (avec intuition et preuve courte), complexité, code multi-langages, pièges et variante. Les langages couverts : Python, TypeScript, JavaScript, Java, Go, C++.

1. Format d'un corrigé

Chaque corrigé contient :

Problème : reformulation synthétique de l'énoncé E17-NN.
Approche : l'intuition, la structure de données choisie, la justification de l'optimalité (bornes inférieures, invariants, preuve par échange pour les greedy, récurrence pour la DP).
Complexité : T (temps) et S (espace), pire cas.
Code : solutions dans plusieurs langages, identifiés par leur icône.
Pièges : erreurs classiques (dépassement d'entier, cas n=1, indexation off-by-one…).
Variante : une extension pour s'entraîner davantage.

2. Niveau facile

E17-01 — Somme et maximum (arrays, ★☆☆)

Problème : renvoyer (somme, max) d'un tableau d'entiers.

Approche : une seule boucle suffit : accumuler la somme et comparer le maximum courant. On initialise max à -inf (ou au premier élément) pour être robuste aux tableaux non vides.

Complexité : T = O(n), S = O(1).

def sum_and_max(arr):
    total, best = 0, float("-inf")
    for x in arr:
        total += x
        best = max(best, x)
    return total, best

function sumAndMax(arr: number[]): [number, number] {
  let total = 0;
  let best = Number.NEGATIVE_INFINITY;
  for (const x of arr) {
    total += x;
    best = Math.max(best, x);
  }
  return [total, best];
}

class Solution {
  int[] sumAndMax(int[] arr) {
    int total = 0, best = Integer.MIN_VALUE;
    for (int x : arr) { total += x; best = Math.max(best, x); }
    return new int[]{total, best};
  }
}

func sumAndMax(arr []int) (int, int) {
	total, best := 0, int(^uint(0)>>1) // MaxInt
	best = -best - 1                    // MinInt
	for _, x := range arr {
		total += x
		if x > best { best = x }
	}
	return total, best
}

#include <vector>
#include <limits>
using namespace std;
pair<int,int> sumAndMax(const vector<int>& arr) {
    long long total = 0;
    int best = numeric_limits<int>::min();
    for (int x : arr) { total += x; best = max(best, x); }
    return {total, best};
}

Pièges : initialiser best = 0 échoue si toutes les valeurs sont négatives. Utiliser long long pour la somme si n × valeur peut dépasser int.

Variante : renvoyer également l'indice de la première occurrence du maximum.

E17-03 — Palindrome (strings, ★☆☆)

Problème : vérifier si une chaîne est un palindrome en ignorant casse et non-alphanumériques.

Approche : deux pointeurs convergent vers le centre. On avance chaque pointeur pour sauter les caractères non alphanumériques, on compare les caractères en minuscule. Complexité linéaire, aucun espace.

Complexité : T = O(n), S = O(1).

def is_palindrome(s: str) -> bool:
    i, j = 0, len(s) - 1
    while i < j:
        while i < j and not s[i].isalnum(): i += 1
        while i < j and not s[j].isalnum(): j -= 1
        if s[i].lower() != s[j].lower():
            return False
        i += 1; j -= 1
    return True

function isPalindrome(s: string): boolean {
  const isAlnum = (c: string) => /[a-z0-9]/i.test(c);
  let i = 0, j = s.length - 1;
  while (i < j) {
    while (i < j && !isAlnum(s[i])) i++;
    while (i < j && !isAlnum(s[j])) j--;
    if (s[i].toLowerCase() !== s[j].toLowerCase()) return false;
    i++; j--;
  }
  return true;
}

class Solution {
  boolean isPalindrome(String s) {
    int i = 0, j = s.length() - 1;
    while (i < j) {
      while (i < j && !Character.isLetterOrDigit(s.charAt(i))) i++;
      while (i < j && !Character.isLetterOrDigit(s.charAt(j))) j--;
      if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))) return false;
      i++; j--;
    }
    return true;
  }
}

func isPalindrome(s string) bool {
	i, j := 0, len(s)-1
	isAlnum := func(c byte) bool {
		return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9')
	}
	for i < j {
		for i < j && !isAlnum(s[i]) { i++ }
		for i < j && !isAlnum(s[j]) { j-- }
		if s[i] >= 'A' && s[i] <= 'Z' { s = s } // converti inline ci-dessous
		lo, hi := s[i], s[j]
		if lo >= 'A' && lo <= 'Z' { lo += 32 }
		if hi >= 'A' && hi <= 'Z' { hi += 32 }
		if lo != hi { return false }
		i++; j--
	}
	return true
}

#include <string>
#include <cctype>
using namespace std;
bool isPalindrome(string s) {
    int i = 0, j = (int)s.size() - 1;
    while (i < j) {
        while (i < j && !isalnum(s[i])) i++;
        while (i < j && !isalnum(s[j])) j--;
        if (tolower(s[i]) != tolower(s[j])) return false;
        i++; j--;
    }
    return true;
}

Pièges : les chaînes vides et les chaînes composées uniquement de séparateurs sont des palindromes (le while interne protège contre i qui dépasse j).

Variante : trouver le palindrome le plus long dans une chaîne (cf. E17-50).

E17-05 — Longueur d'une liste chaînée (linked lists, ★☆☆)

Problème : compter les nœuds d'une liste chaînée.

Approche : itérer jusqu'à null. Le cas d'une liste vide retourne naturellement 0.

Complexité : T = O(n), S = O(1).

class ListNode:
    def __init__(self, val=0, next=None):
        self.val, self.next = val, next

def list_length(head):
    count = 0
    while head:
        count += 1
        head = head.next
    return count

class ListNode {
  val: number; next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val; this.next = next;
  }
}
function listLength(head: ListNode | null): number {
  let count = 0;
  while (head) { count++; head = head.next; }
  return count;
}

class ListNode {
  int val; ListNode next;
  ListNode(int val) { this.val = val; }
}
class Solution {
  int listLength(ListNode head) {
    int count = 0;
    while (head != null) { count++; head = head.next; }
    return count;
  }
}

type ListNode struct {
	Val  int
	Next *ListNode
}
func listLength(head *ListNode) int {
	count := 0
	for head != nil {
		count++
		head = head.Next
	}
	return count
}

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int v) : val(v), next(nullptr) {}
};
int listLength(ListNode* head) {
    int count = 0;
    while (head) { count++; head = head->next; }
    return count;
}

Pièges : ne pas libérer de mémoire si on travaille avec des pointeurs bruts en C++ (ou préférer unique_ptr). Ne jamais utiliser une boucle for avec head->next sans précaution.

Variante : détecter un cycle et trouver son point d'entrée (E17-93).

E17-07 — Élément le plus fréquent (hash, ★☆☆)

Problème : renvoyer l'élément apparaissant le plus souvent.

Approche : hash map valeur → compte, puis extraction du maximum. Une seule passe.

Complexité : T = O(n), S = O(n).

def most_frequent(arr):
    freq = {}
    for x in arr:
        freq[x] = freq.get(x, 0) + 1
    return max(freq, key=freq.get)

function mostFrequent(arr: number[]): number {
  const freq = new Map<number, number>();
  for (const x of arr) freq.set(x, (freq.get(x) ?? 0) + 1);
  let best = arr[0];
  for (const [k, v] of freq) if (v > freq.get(best)!) best = k;
  return best;
}

import java.util.HashMap;
class Solution {
  int mostFrequent(int[] arr) {
    HashMap<Integer, Integer> freq = new HashMap<>();
    for (int x : arr) freq.merge(x, 1, Integer::sum);
    int best = arr[0];
    for (var e : freq.entrySet())
      if (e.getValue() > freq.get(best)) best = e.getKey();
    return best;
  }
}

func mostFrequent(arr []int) int {
	freq := map[int]int{}
	for _, x := range arr { freq[x]++ }
	best, maxCount := arr[0], 0
	for k, v := range freq {
		if v > maxCount { best, maxCount = k, v }
	}
	return best
}

#include <unordered_map>
#include <vector>
using namespace std;
int mostFrequent(const vector<int>& arr) {
    unordered_map<int, int> freq;
    for (int x : arr) freq[x]++;
    int best = arr[0], bestCount = 0;
    for (auto& [k, v] : freq)
        if (v > bestCount) { best = k; bestCount = v; }
    return best;
}

Pièges : si plusieurs éléments ont le même compte, la politique de départage (premier rencontré, plus grand…) doit être décidée et documentée.

Variante : en cas d'égalité, renvoyer tous les éléments ex æquo.

E17-13 — Fibonacci (DP, ★☆☆)

Problème : calculer fib(n).

Approche : récurrence fib(n) = fib(n-1) + fib(n-2) avec cas de base 0, 1. La version récursive naïve est O(2^n) ; la version itérative glissante est O(n) et O(1) en espace.

Complexité : T = O(n), S = O(1) (version itérative).

def fib(n: int) -> int:
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

function fib(n: number): number {
  let a = 0, b = 1;
  for (let i = 0; i < n; i++) [a, b] = [b, a + b];
  return a;
}

class Solution {
  long fib(int n) {
    long a = 0, b = 1;
    for (int i = 0; i < n; i++) { long t = a; a = b; b = t + b; }
    return a;
  }
}

func fib(n int) int {
	a, b := 0, 1
	for i := 0; i < n; i++ {
		a, b = b, a+b
	}
	return a
}

long long fib(int n) {
    long long a = 0, b = 1;
    for (int i = 0; i < n; i++) { long long t = a; a = b; b = t + b; }
    return a;
}

Pièges : pour n > 90 environ, fib(n) dépasse 64 bits — utiliser Python (grands entiers) ou des big integers.

Variante : calculer fib(n) en O(log n) par exponentiation de la matrice [[1,1],[1,0]] (cf. chapitre 14).

E17-19 — PGCD par Euclide (math, ★☆☆)

Problème : calculer le PGCD de deux entiers.

Approche : gcd(a, b) = gcd(b, a % b) jusqu'à ce que le reste soit nul. Les modulos divisent au moins par 2 le plus grand argument à chaque étape.

Complexité : T = O(log min(a,b)), S = O(1).

def gcd(a: int, b: int) -> int:
    while b:
        a, b = b, a % b
    return a

function gcd(a: number, b: number): number {
  while (b !== 0) [a, b] = [b, a % b];
  return a;
}

class Solution {
  int gcd(int a, int b) {
    while (b != 0) { int t = a % b; a = b; b = t; }
    return a;
  }
}

func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

int gcd(int a, int b) {
    while (b) { int t = a % b; a = b; b = t; }
    return a;
}

Pièges : l'opérateur % sur des valeurs négatives peut produire des restes négatifs selon le langage — normaliser avec les valeurs absolues si nécessaire.

Variante : PGCD d'un tableau (itératif, associativité) et calcul du PPCM via a/gcd(a,b)*b pour éviter les dépassements.

3. Niveau moyen

E17-21 — Two Sum (arrays, ★★☆)

Problème : trouver deux indices dont les valeurs somment à une cible.

Approche : hash map valeur → indice. Pour chaque x, chercher target - x dans la map avant d'insérer x. On garantit de ne pas utiliser deux fois le même élément car on n'insère qu'après la recherche.

Complexité : T = O(n), S = O(n).

def two_sum(arr, target):
    seen = {}
    for i, x in enumerate(arr):
        if target - x in seen:
            return [seen[target - x], i]
        seen[x] = i
    return []

function twoSum(arr: number[], target: number): number[] {
  const seen = new Map<number, number>();
  for (let i = 0; i < arr.length; i++) {
    const comp = target - arr[i];
    if (seen.has(comp)) return [seen.get(comp)!, i];
    seen.set(arr[i], i);
  }
  return [];
}

import java.util.HashMap;
class Solution {
  int[] twoSum(int[] arr, int target) {
    HashMap<Integer, Integer> seen = new HashMap<>();
    for (int i = 0; i < arr.length; i++) {
      int comp = target - arr[i];
      if (seen.containsKey(comp)) return new int[]{seen.get(comp), i};
      seen.put(arr[i], i);
    }
    return new int[0];
  }
}

func twoSum(arr []int, target int) []int {
	seen := map[int]int{}
	for i, x := range arr {
		if j, ok := seen[target-x]; ok {
			return []int{j, i}
		}
		seen[x] = i
	}
	return nil
}

#include <vector>
#include <unordered_map>
using namespace std;
vector<int> twoSum(const vector<int>& arr, int target) {
    unordered_map<int, int> seen;
    for (int i = 0; i < (int)arr.size(); i++) {
        int comp = target - arr[i];
        if (seen.count(comp)) return {seen[comp], i};
        seen[arr[i]] = i;
    }
    return {};
}

Pièges : vérifier qu'on ne retourne pas [i, i] quand x == target - x (le comportement ci-dessus est correct car l'insertion a lieu après la recherche).

Variante : trier + deux pointeurs pour une version O(n) espace O(1) (mais perd l'indice original).

E17-24 — Anagrammes (strings, ★★☆)

Problème : vérifier si deux chaînes sont des anagrammes.

Approche : compter les 26 lettres de s, décrémenter avec t ; si un compte devient négatif (ou si un compte final n'est pas nul), ce n'est pas une anagramme.

Complexité : T = O(n), S = O(1) (26 compteurs).

def is_anagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    counts = [0] * 26
    for c in s: counts[ord(c) - ord('a')] += 1
    for c in t: counts[ord(c) - ord('a')] -= 1
    return all(c == 0 for c in counts)

function isAnagram(s: string, t: string): boolean {
  if (s.length !== t.length) return false;
  const counts = new Array(26).fill(0);
  for (const c of s) counts[c.charCodeAt(0) - 97]++;
  for (const c of t) counts[c.charCodeAt(0) - 97]--;
  return counts.every((v) => v === 0);
}

class Solution {
  boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;
    int[] counts = new int[26];
    for (char c : s.toCharArray()) counts[c - 'a']++;
    for (char c : t.toCharArray()) counts[c - 'a']--;
    for (int v : counts) if (v != 0) return false;
    return true;
  }
}

func isAnagram(s, t string) bool {
	if len(s) != len(t) { return false }
	counts := [26]int{}
	for i := range s { counts[s[i]-'a']++ }
	for i := range t { counts[t[i]-'a']-- }
	for _, v := range counts { if v != 0 { return false } }
	return true
}

#include <string>
using namespace std;
bool isAnagram(const string& s, const string& t) {
    if (s.size() != t.size()) return false;
    int counts[26] = {0};
    for (char c : s) counts[c - 'a']++;
    for (char c : t) counts[c - 'a']--;
    for (int v : counts) if (v != 0) return false;
    return true;
}

Pièges : supposer l'alphabet minuscule a–z. Pour Unicode ou clés arbitraires, utiliser une hash map.

Variante : retourner toutes les paires d'anagrammes d'une liste (E17-31).

E17-27 — Retirer le n-ième nœud depuis la fin (linked lists, ★★☆)

Problème : supprimer le nœud à n positions de la fin en un seul parcours.

Approche : un pointeur fast avance de n pas, puis slow et fast avancent ensemble : quand fast atteint la fin, slow pointe sur le nœud précédant celui à supprimer. Un nœud factice (dummy) gère la suppression en tête.

Complexité : T = O(n), S = O(1).

def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)
    fast = slow = dummy
    for _ in range(n):
        fast = fast.next
    while fast.next:
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next
    return dummy.next

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  const dummy = new ListNode(0, head);
  let fast: ListNode | null = dummy, slow: ListNode | null = dummy;
  for (let i = 0; i < n; i++) fast = fast!.next;
  while (fast!.next) { fast = fast!.next; slow = slow!.next; }
  slow!.next = slow!.next!.next;
  return dummy.next;
}

class Solution {
  ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode fast = dummy, slow = dummy;
    for (int i = 0; i < n; i++) fast = fast.next;
    while (fast.next != null) { fast = fast.next; slow = slow.next; }
    slow.next = slow.next.next;
    return dummy.next;
  }
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
	dummy := &ListNode{Next: head}
	fast, slow := dummy, dummy
	for i := 0; i < n; i++ { fast = fast.Next }
	for fast.Next != nil {
		fast = fast.Next
		slow = slow.Next
	}
	slow.Next = slow.Next.Next
	return dummy.Next
}

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode dummy(0, head);
    ListNode *fast = &dummy, *slow = &dummy;
    for (int i = 0; i < n; i++) fast = fast->next;
    while (fast->next) { fast = fast->next; slow = slow->next; }
    ListNode* toDel = slow->next;
    slow->next = slow->next->next;
    delete toDel;
    return dummy.next;
}

Pièges : le n est toujours valide dans l'énoncé ; si ce n'était pas garanti, il faut borner la boucle initiale.

Variante : avec n dépassant la longueur, ne rien supprimer.

E17-29 — Sous-tableaux de somme `k` (hash, ★★☆)

Problème : compter les sous-tableaux contigus dont la somme vaut k (valeurs négatives incluses).

Approche : prefix sums. sum(i..j) = pref[j+1] - pref[i] = k équivaut à pref[i] = pref[j+1] - k. On compte donc dans une hash map le nombre d'occurrences de chaque prefix sum rencontrée.

Complexité : T = O(n), S = O(n).

def subarray_sum(arr, k):
    counts = {0: 1}
    total, ans = 0, 0
    for x in arr:
        total += x
        ans += counts.get(total - k, 0)
        counts[total] = counts.get(total, 0) + 1
    return ans

function subarraySum(arr: number[], k: number): number {
  const counts = new Map<number, number>([[0, 1]]);
  let total = 0, ans = 0;
  for (const x of arr) {
    total += x;
    ans += counts.get(total - k) ?? 0;
    counts.set(total, (counts.get(total) ?? 0) + 1);
  }
  return ans;
}

import java.util.HashMap;
class Solution {
  int subarraySum(int[] arr, int k) {
    HashMap<Integer, Integer> counts = new HashMap<>();
    counts.put(0, 1);
    int total = 0, ans = 0;
    for (int x : arr) {
      total += x;
      ans += counts.getOrDefault(total - k, 0);
      counts.merge(total, 1, Integer::sum);
    }
    return ans;
  }
}

func subarraySum(arr []int, k int) int {
	counts := map[int]int{0: 1}
	total, ans := 0, 0
	for _, x := range arr {
		total += x
		ans += counts[total-k]
		counts[total]++
	}
	return ans
}

#include <vector>
#include <unordered_map>
using namespace std;
int subarraySum(const vector<int>& arr, int k) {
    unordered_map<int, int> counts{{0, 1}};
    long long total = 0;
    int ans = 0;
    for (int x : arr) {
        total += x;
        ans += counts[total - k];
        counts[total]++;
    }
    return ans;
}

Pièges : les valeurs négatives invalident la technique sliding window simple — c'est précisément pourquoi on utilise les prefix sums.

Variante : version « plus long sous-tableau de somme k » en gardant le premier indice de chaque prefix sum.

E17-34 — Nombre d'îles (graphs, ★★☆)

Problème : compter les composantes connexes de 1 dans une grille binaire.

Approche : parcours de la grille ; à chaque 1 non visité, lancer un BFS/DFS en marquant toutes les cases voisines (4 directions) et incrémenter le compteur. On peut marquer en modifiant la grille (1 → 0) pour économiser la mémoire.

Complexité : T = O(R×C), S = O(R×C) dans le pire cas (pile de DFS).

def num_islands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    ans = 0
    def dfs(r, c):
        if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] == '0':
            return
        grid[r][c] = '0'
        dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1)
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                ans += 1
                dfs(r, c)
    return ans

function numIslands(grid: string[][]): number {
  const rows = grid.length, cols = grid[0].length;
  let ans = 0;
  const dfs = (r: number, c: number) => {
    if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] === "0") return;
    grid[r][c] = "0";
    dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1);
  };
  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      if (grid[r][c] === "1") { ans++; dfs(r, c); }
  return ans;
}

class Solution {
  int rows, cols;
  int numIslands(char[][] grid) {
    rows = grid.length; cols = grid[0].length;
    int ans = 0;
    for (int r = 0; r < rows; r++)
      for (int c = 0; c < cols; c++)
        if (grid[r][c] == '1') { ans++; dfs(grid, r, c); }
    return ans;
  }
  void dfs(char[][] grid, int r, int c) {
    if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] == '0') return;
    grid[r][c] = '0';
    dfs(grid, r+1, c); dfs(grid, r-1, c); dfs(grid, r, c+1); dfs(grid, r, c-1);
  }
}

func numIslands(grid [][]byte) int {
	if len(grid) == 0 { return 0 }
	rows, cols := len(grid), len(grid[0])
	var dfs func(r, c int)
	dfs = func(r, c int) {
		if r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] == '0' { return }
		grid[r][c] = '0'
		dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1)
	}
	ans := 0
	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {
			if grid[r][c] == '1' { ans++; dfs(r, c) }
		}
	}
	return ans
}

#include <vector>
using namespace std;
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int rows = grid.size(), cols = grid[0].size(), ans = 0;
        auto dfs = [&](int r, int c, auto&& self) -> void {
            if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] == '0') return;
            grid[r][c] = '0';
            self(r+1, c, self); self(r-1, c, self);
            self(r, c+1, self); self(r, c-1, self);
        };
        for (int r = 0; r < rows; r++)
            for (int c = 0; c < cols; c++)
                if (grid[r][c] == '1') { ans++; dfs(r, c, dfs); }
        return ans;
    }
};

Pièges : sur les grandes grilles, la récursion peut déborder la pile en Java/C++ — passer à un BFS itératif ou à une pile explicite.

Variante : compter les îles avec union-find (nombre de fusions = nombre de composantes).

E17-37 — Kadane (DP, ★★☆)

Problème : sous-tableau contigu de somme maximale (valeurs négatives incluses).

Approche : invariant — best est la meilleure somme se terminant à la position courante ; on met à jour le maximum global. Si best devient négatif, on repart de zéro (cela ne peut qu'augmenter les sommes futures).

Complexité : T = O(n), S = O(1).

def max_subarray(arr):
    best, current = arr[0], arr[0]
    for x in arr[1:]:
        current = max(x, current + x)
        best = max(best, current)
    return best

function maxSubArray(arr: number[]): number {
  let best = arr[0], current = arr[0];
  for (let i = 1; i < arr.length; i++) {
    current = Math.max(arr[i], current + arr[i]);
    best = Math.max(best, current);
  }
  return best;
}

class Solution {
  int maxSubArray(int[] arr) {
    int best = arr[0], current = arr[0];
    for (int i = 1; i < arr.length; i++) {
      current = Math.max(arr[i], current + arr[i]);
      best = Math.max(best, current);
    }
    return best;
  }
}

func maxSubArray(arr []int) int {
	best, current := arr[0], arr[0]
	for _, x := range arr[1:] {
		current = max(x, current+x)
		best = max(best, current)
	}
	return best
}

#include <vector>
#include <algorithm>
using namespace std;
int maxSubArray(const vector<int>& arr) {
    int best = arr[0], current = arr[0];
    for (int i = 1; i < (int)arr.size(); i++) {
        current = max(arr[i], current + arr[i]);
        best = max(best, current);
    }
    return best;
}

Pièges : initialiser best à 0 échoue si tous les éléments sont négatifs (le maximum serait 0 au lieu d'un élément du tableau).

Variante : renvoyer les indices de début et de fin du sous-tableau optimal.

E17-39 — Assigner des cookies (greedy, ★★☆)

Problème : maximiser le nombre d'enfants satisfaits, chaque enfant acceptant un cookie s ≥ g.

Approche : trier g et s ; deux pointeurs. Pour chaque enfant (besoin croissant), donner le plus petit cookie satisfaisant. C'est optimal par preuve d'échange : donner le cookie minimal satisfaisant ne peut pas gêner les enfants suivants.

Complexité : T = O(n log n + m log m), S = O(1).

def find_content_children(g, s):
    g.sort(); s.sort()
    i = j = 0
    while i < len(g) and j < len(s):
        if s[j] >= g[i]:
            i += 1
        j += 1
    return i

function findContentChildren(g: number[], s: number[]): number {
  g.sort((a, b) => a - b); s.sort((a, b) => a - b);
  let i = 0, j = 0;
  while (i < g.length && j < s.length) {
    if (s[j] >= g[i]) i++;
    j++;
  }
  return i;
}

import java.util.Arrays;
class Solution {
  int findContentChildren(int[] g, int[] s) {
    Arrays.sort(g); Arrays.sort(s);
    int i = 0, j = 0;
    while (i < g.length && j < s.length) {
      if (s[j] >= g[i]) i++;
      j++;
    }
    return i;
  }
}

import "sort"
func findContentChildren(g, s []int) int {
	sort.Ints(g); sort.Ints(s)
	i, j := 0, 0
	for i < len(g) && j < len(s) {
		if s[j] >= g[i] { i++ }
		j++
	}
	return i
}

#include <vector>
#include <algorithm>
using namespace std;
int findContentChildren(vector<int>& g, vector<int>& s) {
    sort(g.begin(), g.end()); sort(s.begin(), s.end());
    int i = 0, j = 0;
    while (i < (int)g.size() && j < (int)s.size()) {
        if (s[j] >= g[i]) i++;
        j++;
    }
    return i;
}

Pièges : trier dans l'ordre croissant des deux côtés, sinon la correspondance « plus petit cookie satisfaisant » n'est pas obtenue.

Variante : variante pondérée (maximiser la somme des bonheurs) qui devient un problème de tri/partitionnement.

E17-44 — Exponentiation modulaire (math, ★★☆)

Problème : calculer a^b mod m en O(log b).

Approche : carré et multiplie — b est découpé en binaire ; à chaque bit, on élève la base au carré, et si le bit est 1, on multiplie le résultat.

Complexité : T = O(log b), S = O(1).

def mod_pow(a, b, m):
    result = 1
    a %= m
    while b > 0:
        if b & 1:
            result = (result * a) % m
        a = (a * a) % m
        b >>= 1
    return result

function modPow(a: bigint, b: bigint, m: bigint): bigint {
  let result = 1n;
  a %= m;
  while (b > 0n) {
    if (b & 1n) result = (result * a) % m;
    a = (a * a) % m;
    b >>= 1n;
  }
  return result;
}

class Solution {
  long modPow(long a, long b, long m) {
    long result = 1;
    a %= m;
    while (b > 0) {
      if ((b & 1) == 1) result = (result * a) % m;
      a = (a * a) % m;
      b >>= 1;
    }
    return result;
  }
}

func modPow(a, b, m int64) int64 {
	result := int64(1)
	a %= m
	for b > 0 {
		if b&1 == 1 {
			result = result * a % m
		}
		a = a * a % m
		b >>= 1
	}
	return result
}

long long modPow(long long a, long long b, long long m) {
    long long result = 1;
    a %= m;
    while (b > 0) {
        if (b & 1) result = result * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return result;
}

Pièges : en C++/Java, a * a peut dépasser 64 bits pour a ≥ 10^9 — utiliser __int128 (C++) ou BigInteger/Math.multiplyHigh (Java).

Variante : inversion modulaire via a^(m-2) mod m quand m est premier (Fermat).

4. Niveau difficile

E17-46 — Médiane de deux tableaux triés (arrays, ★★★)

Problème : médiane de deux tableaux triés en O(log(min(n, m))).

Approche : sur le plus petit tableau, recherche binaire de la partition i ; j = (n+m+1)/2 - i. On vérifie les inégalités maxLeftA ≤ minRightB et maxLeftB ≤ minRightA puis on ajuste la partition. La médiane se lit aux frontières.

Complexité : T = O(log min(n, m)), S = O(1).

def find_median_sorted_arrays(a, b):
    if len(a) > len(b):
        a, b = b, a
    n, m = len(a), len(b)
    lo, hi = 0, n
    while lo <= hi:
        i = (lo + hi) // 2
        j = (n + m + 1) // 2 - i
        a_left = a[i-1] if i > 0 else float("-inf")
        a_right = a[i] if i < n else float("inf")
        b_left = b[j-1] if j > 0 else float("-inf")
        b_right = b[j] if j < m else float("inf")
        if a_left <= b_right and b_left <= a_right:
            if (n + m) % 2 == 1:
                return max(a_left, b_left)
            return (max(a_left, b_left) + min(a_right, b_right)) / 2
        elif a_left > b_right:
            hi = i - 1
        else:
            lo = i + 1

Pièges : la gestion des frontières (-inf / +inf) est critique — elle évite les accès hors bornes pour i=0, i=n, j=0, j=m.

Variante : k-ième plus petit élément de deux tableaux triés (même logique, en O(log(n+m))).

E17-47 — Trapping Rain Water (arrays, ★★★)

Problème : eau totale piégée entre les barres.

Approche : deux pointeurs l et r avec maxL et maxR : à chaque pas, on traite le côté le plus bas car la quantité d'eau ne dépend que du plus petit des deux maxima.

Complexité : T = O(n), S = O(1).

def trap(height):
    l, r = 0, len(height) - 1
    max_l = max_r = water = 0
    while l <= r:
        if max_l <= max_r:
            max_l = max(max_l, height[l])
            water += max_l - height[l]
            l += 1
        else:
            max_r = max(max_r, height[r])
            water += max_r - height[r]
            r -= 1
    return water

function trap(height: number[]): number {
  let l = 0, r = height.length - 1, maxL = 0, maxR = 0, water = 0;
  while (l <= r) {
    if (maxL <= maxR) {
      maxL = Math.max(maxL, height[l]);
      water += maxL - height[l];
      l++;
    } else {
      maxR = Math.max(maxR, height[r]);
      water += maxR - height[r];
      r--;
    }
  }
  return water;
}

class Solution {
  int trap(int[] height) {
    int l = 0, r = height.length - 1, maxL = 0, maxR = 0, water = 0;
    while (l <= r) {
      if (maxL <= maxR) {
        maxL = Math.max(maxL, height[l]);
        water += maxL - height[l]; l++;
      } else {
        maxR = Math.max(maxR, height[r]);
        water += maxR - height[r]; r--;
      }
    }
    return water;
  }
}

func trap(height []int) int {
	l, r := 0, len(height)-1
	maxL, maxR, water := 0, 0, 0
	for l <= r {
		if maxL <= maxR {
			if height[l] > maxL { maxL = height[l] }
			water += maxL - height[l]
			l++
		} else {
			if height[r] > maxR { maxR = height[r] }
			water += maxR - height[r]
			r--
		}
	}
	return water
}

#include <vector>
using namespace std;
int trap(const vector<int>& height) {
    int l = 0, r = (int)height.size() - 1, maxL = 0, maxR = 0, water = 0;
    while (l <= r) {
        if (maxL <= maxR) {
            maxL = max(maxL, height[l]);
            water += maxL - height[l]; l++;
        } else {
            maxR = max(maxR, height[r]);
            water += maxR - height[r]; r--;
        }
    }
    return water;
}

Pièges : confondre avec « plus grande surface de conteneur » (Two-pointer classique). Ici on cumule l'eau à chaque barre.

Variante : afficher la configuration de l'eau (matrice remplie).

E17-57 — Maximum path sum (trees, ★★★)

Problème : chemin de somme maximale entre deux nœuds quelconques d'un arbre binaire.

Approche : DFS postfixe. Chaque nœud renvoie le gain maximal d'une seule branche (max(0, gauche, droite) + val) ; on met à jour un maximum global avec val + gainGauche + gainDroite. Prendre max(0, …) permet d'ignorer les branches négatives.

Complexité : T = O(n), S = O(h) (h = hauteur).

def max_path_sum(root):
    best = float("-inf")
    def dfs(node):
        nonlocal best
        if not node:
            return 0
        left = max(dfs(node.left), 0)
        right = max(dfs(node.right), 0)
        best = max(best, left + node.val + right)
        return node.val + max(left, right)
    dfs(root)
    return best

#include <algorithm>
struct TreeNode { int val; TreeNode *left, *right; };
int maxPathSum(TreeNode* root) {
    int best = INT_MIN;
    std::function<int(TreeNode*)> dfs = [&](TreeNode* node) -> int {
        if (!node) return 0;
        int left = std::max(dfs(node->left), 0);
        int right = std::max(dfs(node->right), 0);
        best = std::max(best, left + node->val + right);
        return node->val + std::max(left, right);
    };
    dfs(root);
    return best;
}

Pièges : ne pas remettre les branches négatives à zéro est une erreur fréquente ; sans max(0, …) les chemins doivent traverser des sous-arbres négatifs inutilement.

Variante : chemin avec contrainte de longueur maximale k (nécessite de suivre plusieurs longueurs par nœud).

E17-59 — Plus court chemin dans un labyrinthe (graphs, ★★★)

Problème : distance minimale de S à E dans une grille avec murs.

Approche : BFS en 4 directions avec une file. On visite chaque case une fois ; la première atteinte de E est la plus courte car toutes les arêtes ont un poids 1.

Complexité : T = O(R×C), S = O(R×C).

from collections import deque

def shortest_path(grid, start, end):
    rows, cols = len(grid), len(grid[0])
    q = deque([(start[0], start[1], 0)])
    seen = {start}
    while q:
        r, c, d = q.popleft()
        if (r, c) == end:
            return d
        for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != '#' and (nr, nc) not in seen:
                seen.add((nr, nc))
                q.append((nr, nc, d + 1))
    return -1

function shortestPath(grid: string[][], start: [number, number], end: [number, number]): number {
  const rows = grid.length, cols = grid[0].length;
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  const seen = new Set<string>([`${start[0]},${start[1]}`]);
  const q: Array<[number, number, number]> = [[start[0], start[1], 0]];
  while (q.length) {
    const [r, c, d] = q.shift()!;
    if (r === end[0] && c === end[1]) return d;
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      const key = `${nr},${nc}`;
      if (nr >= 0 && nc >= 0 && nr < rows && nc < cols && grid[nr][nc] !== "#" && !seen.has(key)) {
        seen.add(key);
        q.push([nr, nc, d + 1]);
      }
    }
  }
  return -1;
}

Pièges : marquer la case au moment de l'empilement (pas à la sortie de file) pour éviter les doublons dans la file.

Variante : grille avec coûts par case → Dijkstra.

E17-62 — Edit distance (DP, ★★★)

Problème : distance de Levenshtein entre deux chaînes.

Approche : dp[i][j] = distance entre s[:i] et t[:j]. Trois transitions : insertion, suppression, substitution. Récurrence standard ; on peut ne garder que deux lignes pour O(m) en mémoire.

Complexité : T = O(n×m), S = O(m) (optimisée).

def edit_distance(s, t):
    prev = list(range(len(t) + 1))
    for i in range(1, len(s) + 1):
        cur = [i] + [0] * len(t)
        for j in range(1, len(t) + 1):
            if s[i-1] == t[j-1]:
                cur[j] = prev[j-1]
            else:
                cur[j] = 1 + min(prev[j], cur[j-1], prev[j-1])
        prev = cur
    return prev[-1]

func editDistance(s, t string) int {
	prev := make([]int, len(t)+1)
	for j := range prev { prev[j] = j }
	for i := 1; i <= len(s); i++ {
		cur := make([]int, len(t)+1)
		cur[0] = i
		for j := 1; j <= len(t); j++ {
			if s[i-1] == t[j-1] {
				cur[j] = prev[j-1]
			} else {
				cur[j] = 1 + min(prev[j], cur[j-1], prev[j-1])
			}
		}
		prev = cur
	}
	return prev[len(t)]
}

Pièges : l'initialisation de la première ligne/colonne (i et j) est source d'erreurs — vérifier sur de petits exemples ("a" vs "b" → 1).

Variante : reconstruction de la séquence d'opérations (backtracking dans la table).

E17-63 — Coin Change (DP, ★★★)

Problème : nombre minimal de pièces pour une somme, système non canonique.

Approche : dp[s] = min(dp[s], dp[s - coin] + 1) pour chaque pièce et chaque somme. DP bottom-up par somme croissante.

Complexité : T = O(amount × n_coins), S = O(amount).

def coin_change(coins, amount):
    dp = [float("inf")] * (amount + 1)
    dp[0] = 0
    for s in range(1, amount + 1):
        for c in coins:
            if c <= s:
                dp[s] = min(dp[s], dp[s - c] + 1)
    return dp[amount] if dp[amount] != float("inf") else -1

Pièges : l'ordre des boucles (somme externe, pièces internes) donne le nombre minimal de pièces pour des pièces réutilisables ; inverser donne le nombre de façons sans réutilisation. La valeur inf doit être distincte de tout résultat valide.

Variante : nombre total de combinaisons de pièces (dénombrement).

E17-67 — N-Queens (backtracking, ★★★)

Problème : placer n reines sans qu'elles s'attaquent.

Approche : backtracking ligne par ligne, en suivant colonnes et diagonales via des hash sets (col, diag1 = r - c, diag2 = r + c). La complexité est le nombre de solutions × coût de construction.

Complexité : T = O(n!) dans le pire cas (en pratique bien moindre), S = O(n).

def solve_n_queens(n):
    cols, diag1, diag2 = set(), set(), set()
    board = [["."] * n for _ in range(n)]
    result = []

    def backtrack(r):
        if r == n:
            result.append(["".join(row) for row in board])
            return
        for c in range(n):
            d1, d2 = r - c, r + c
            if c in cols or d1 in diag1 or d2 in diag2:
                continue
            cols.add(c); diag1.add(d1); diag2.add(d2)
            board[r][c] = "Q"
            backtrack(r + 1)
            board[r][c] = "."
            cols.remove(c); diag1.remove(d1); diag2.remove(d2)

    backtrack(0)
    return result

import java.util.*;
class Solution {
  List<List<String>> result = new ArrayList<>();
  Set<Integer> cols = new HashSet<>(), diag1 = new HashSet<>(), diag2 = new HashSet<>();
  int n;
  List<List<String>> solveNQueens(int n) {
    this.n = n;
    char[][] board = new char[n][n];
    for (char[] row : board) Arrays.fill(row, '.');
    backtrack(0, board);
    return result;
  }
  void backtrack(int r, char[][] board) {
    if (r == n) {
      List<String> list = new ArrayList<>();
      for (char[] row : board) list.add(new String(row));
      result.add(list);
      return;
    }
    for (int c = 0; c < n; c++) {
      int d1 = r - c, d2 = r + c;
      if (cols.contains(c) || diag1.contains(d1) || diag2.contains(d2)) continue;
      cols.add(c); diag1.add(d1); diag2.add(d2);
      board[r][c] = 'Q';
      backtrack(r + 1, board);
      board[r][c] = '.';
      cols.remove(c); diag1.remove(d1); diag2.remove(d2);
    }
  }
}

Pièges : oublier de retirer la reine après le retour de récursion (backtracking incomplet) ou de la retirer des sets de diagonales.

Variante : version bitmask pour n = 16 (E17-99).

5. Niveau expert

E17-71 — Inversion count (arrays, ★★★★)

Problème : compter les paires (i < j) avec arr[i] > arr[j].

Approche : pendant le tri fusion, chaque fois qu'un élément de la moitié droite est placé, les éléments restants de la moitié gauche sont tous plus grands que lui → on ajoute leur nombre au compteur. Invariant du tri fusion préservé.

Complexité : T = O(n log n), S = O(n).

def count_inversions(arr):
    def merge_sort(lo, hi):
        if hi - lo <= 1:
            return 0
        mid = (lo + hi) // 2
        inv = merge_sort(lo, mid) + merge_sort(mid, hi)
        merged, i, j = [], lo, mid
        while i < mid and j < hi:
            if arr[i] <= arr[j]:
                merged.append(arr[i]); i += 1
            else:
                merged.append(arr[j]); j += 1
                inv += mid - i
        merged.extend(arr[i:mid]); merged.extend(arr[j:hi])
        arr[lo:hi] = merged
        return inv
    return merge_sort(0, len(arr))

Pièges : la condition de comparaison doit être ≤ (pas <) pour ne pas compter les paires d'éléments égaux.

Variante : compter les paires arr[i] > 2 * arr[j] (adjustment de la comparaison seulement).

E17-72 — Sliding window maximum (arrays, ★★★★)

Problème : maximum de chaque fenêtre de taille k.

Approche : deque monotone décroissante stockant les indices. Avant d'ajouter i, retirer de la queue tous les indices dont la valeur est ≤ arr[i] ; retirer de la tête tout indice hors de la fenêtre. La tête est le maximum.

Complexité : T = O(n), S = O(k) (chaque élément entre/sort au plus une fois).

from collections import deque

def max_sliding_window(arr, k):
    dq = deque()
    result = []
    for i, x in enumerate(arr):
        while dq and arr[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            result.append(arr[dq[0]])
    return result

#include <deque>
#include <vector>
using namespace std;
vector<int> maxSlidingWindow(const vector<int>& arr, int k) {
    deque<int> dq;
    vector<int> result;
    for (int i = 0; i < (int)arr.size(); i++) {
        while (!dq.empty() && arr[dq.back()] <= arr[i]) dq.pop_back();
        dq.push_back(i);
        if (dq.front() <= i - k) dq.pop_front();
        if (i >= k - 1) result.push_back(arr[dq.front()]);
    }
    return result;
}

Pièges : stocker les valeurs au lieu des indices empêche d'expirer correctement la fenêtre.

Variante : minimum de chaque fenêtre (inverser la monotonie du deque).

E17-81 — Dijkstra (graphs, ★★★★)

Problème : plus courts chemins depuis une source (poids non négatifs).

Approche : priority queue de (distance, sommet). On ne réinsère un sommet que si on trouve une meilleure distance. Grâce aux poids non négatifs, la première extraction d'un sommet donne sa distance finale.

Complexité : T = O((V + E) log V), S = O(V + E).

import heapq

def dijkstra(n, adj, src):
    dist = [float("inf")] * n
    dist[src] = 0
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

import "container/heap"

type item struct{ dist, node int }
type pq []item

func (p pq) Len() int            { return len(p) }
func (p pq) Less(i, j int) bool  { return p[i].dist < p[j].dist }
func (p pq) Swap(i, j int)       { p[i], p[j] = p[j], p[i] }
func (p *pq) Push(x any)         { *p = append(*p, x.(item)) }
func (p *pq) Pop() any {
	old := *p
	n := len(old)
	x := old[n-1]
	*p = old[:n-1]
	return x
}

func dijkstra(n int, adj [][][]int, src int) []int {
	dist := make([]int, n)
	for i := range dist { dist[i] = 1 << 60 }
	dist[src] = 0
	h := &pq{{0, src}}
	heap.Init(h)
	for h.Len() > 0 {
		it := heap.Pop(h).(item)
		if it.dist > dist[it.node] { continue }
		for _, e := range adj[it.node] {
			v, w := e[0], e[1]
			if nd := it.dist + w; nd < dist[v] {
				dist[v] = nd
				heap.Push(h, item{nd, v})
			}
		}
	}
	return dist
}

Pièges : oublier le test d > dist[u] (stale entries) peut dupliquer énormément la file.

Variante : retrouver le chemin complet en gardant un tableau prev.

E17-84 — Sac à dos 0/1 (DP, ★★★★)

Problème : valeur maximale sous contrainte de poids, chaque objet pris au plus une fois.

Approche : DP 1D sur le poids, parcourue en décroissant pour ne pas réutiliser un objet.

Complexité : T = O(n × W), S = O(W).

def knapsack(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        for c in range(capacity, w - 1, -1):
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[capacity]

function knapsack(weights: number[], values: number[], capacity: number): number {
  const dp = new Array(capacity + 1).fill(0);
  for (let i = 0; i < weights.length; i++)
    for (let c = capacity; c >= weights[i]; c--)
      dp[c] = Math.max(dp[c], dp[c - weights[i]] + values[i]);
  return dp[capacity];
}

Pièges : si le parcours se fait en croissant, on autorise la prise multiple d'un même objet (knapsack illimité). La direction de la boucle interne encode la contrainte 0/1.

Variante : reconstruction de la liste des objets pris.

6. Niveau compétition

E17-95 — Diamètre d'un arbre (trees, ★★★★★)

Problème : paire de sommets la plus éloignée.

Approche : deux DFS/BFS — depuis un sommet arbitraire, le plus éloigné est une extrémité du diamètre (théorème classique), puis la distance depuis cette extrémité donne le diamètre.

Complexité : T = O(n), S = O(n).

from collections import deque

def diameter(n, adj):
    def bfs(src):
        dist = [-1] * n
        dist[src] = 0
        q = deque([src])
        farthest, maxd = src, 0
        while q:
            u = q.popleft()
            for v in adj[u]:
                if dist[v] == -1:
                    dist[v] = dist[u] + 1
                    q.append(v)
                    if dist[v] > maxd:
                        maxd, farthest = dist[v], v
        return farthest, maxd
    a, _ = bfs(0)
    _, d = bfs(a)
    return d

Pièges : pour un graphe avec cycles, la propriété « deux BFS » n'est vraie que pour les arbres.

Variante : retourner le chemin du diamètre (garder prev dans le BFS).

E17-97 — TSP par DP bitmask (DP, ★★★★★)

Problème : cycle hamiltonien de coût minimal sur n ≤ 16 villes.

Approche : dp[mask][i] = coût minimal pour visiter l'ensemble mask et terminer en i. Transition : dp[mask | (1<<j)][j] = min(dp[mask][i] + cost[i][j]). Les états sont les 2^n masques × n fins.

Complexité : T = O(n² · 2^n), S = O(n · 2^n).

def tsp(n, cost):
    dp = [[float("inf")] * n for _ in range(1 << n)]
    dp[1][0] = 0
    for mask in range(1 << n):
        for i in range(n):
            if dp[mask][i] == float("inf"):
                continue
            for j in range(n):
                if mask & (1 << j):
                    continue
                dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j], dp[mask][i] + cost[i][j])
    full = (1 << n) - 1
    return min(dp[full][i] + cost[i][0] for i in range(1, n))

Pièges : n ≤ 20 est déjà 20·2²⁰ ≈ 20 millions d'états — au-delà, passer aux heuristiques (2-opt, simulated annealing).

Variante : reconstruction du tour via tableau parent.

7. Grille d'auto-évaluation

Après avoir comparé votre solution à un corrigé :

Vous aviez le bon algorithme et une complexité optimale → passez à l'exercice suivant.
Algorithme correct mais sous-optimal → re-codez la version optimale de mémoire.
Approche fausse ou bug → reprenez le chapitre de la technique concernée (DP, graphes, hash…) puis refaites l'exercice dans 48 h.

Niveau	Objectif de réussite	Temps cible
Facile	20/20 sans aide	< 15 min
Moyen	20/25 sans aide	15–30 min
Difficile	15/25 (indices autorisés)	30–45 min
Expert	10/20 (indices autorisés)	45–60 min
Compétition	4/10 avec editorials	45 min chacun

Une fois les corrigés assimilés, passez aux ressources du chapitre 20 pour continuer l'entraînement en conditions réelles.

19 — Corrections

19 — Corrections détaillées : solutions multi-langages

Sommaire

1. Format d'un corrigé

2. Niveau facile

E17-01 — Somme et maximum (arrays, ★☆☆)

E17-03 — Palindrome (strings, ★☆☆)

E17-05 — Longueur d'une liste chaînée (linked lists, ★☆☆)

E17-07 — Élément le plus fréquent (hash, ★☆☆)

E17-13 — Fibonacci (DP, ★☆☆)

E17-19 — PGCD par Euclide (math, ★☆☆)

3. Niveau moyen

E17-21 — Two Sum (arrays, ★★☆)

E17-24 — Anagrammes (strings, ★★☆)

E17-27 — Retirer le n-ième nœud depuis la fin (linked lists, ★★☆)

E17-29 — Sous-tableaux de somme k (hash, ★★☆)

E17-34 — Nombre d'îles (graphs, ★★☆)

E17-37 — Kadane (DP, ★★☆)

E17-39 — Assigner des cookies (greedy, ★★☆)

E17-44 — Exponentiation modulaire (math, ★★☆)

4. Niveau difficile

E17-46 — Médiane de deux tableaux triés (arrays, ★★★)

E17-47 — Trapping Rain Water (arrays, ★★★)

E17-57 — Maximum path sum (trees, ★★★)

E17-59 — Plus court chemin dans un labyrinthe (graphs, ★★★)

E17-62 — Edit distance (DP, ★★★)

E17-63 — Coin Change (DP, ★★★)

E17-67 — N-Queens (backtracking, ★★★)

5. Niveau expert

E17-71 — Inversion count (arrays, ★★★★)

E17-72 — Sliding window maximum (arrays, ★★★★)

E17-81 — Dijkstra (graphs, ★★★★)

E17-84 — Sac à dos 0/1 (DP, ★★★★)

6. Niveau compétition

E17-95 — Diamètre d'un arbre (trees, ★★★★★)

E17-97 — TSP par DP bitmask (DP, ★★★★★)

7. Grille d'auto-évaluation

E17-29 — Sous-tableaux de somme `k` (hash, ★★☆)