Find then compare

Question 1

Dans quel type de problème utilise-t-on le pattern “Find then Compare” ?

Answer 1

Quand on doit déterminer, pour chaque élément d’une séquence, si lui-même augmenté d’une même constante peut atteindre ou dépasser la valeur maximale de cette séquence au départ

Question 2

Quelle est la première étape de ce pattern ?

Answer 2

Faire une première passe pour trouver la valeur de référence (ici maxCandies = max(candies)) en O(n)

Question 3

Comment procède-t-on ensuite pour chaque élément ?

Answer 3

Pour chaque indice i, on calcule candies[i] + extraCandies et on vérifie si ce total est ≥ la référence maxCandies

Question 4

Comment nomme-t-on ce pattern en deux passes ?

Answer 4

On l’appelle souvent “Find then Compare” ou “Threshold Check” : on trouve d’abord un seuil global, puis on compare chaque entrée à ce seuil

Question 5

Quelle est la complexité en temps et en espace de ce pattern ?

Answer 5

Temps : O(n) (deux parcours linéaires de la liste)

Espace : O(n) pour la liste de résultats (ou O(1) espace auxiliaire si on modifie une liste existante)

Question 6

Peut-on écrire cette solution en une seule expression Python ?

Answer 6

Oui, en combinant max() et une compréhension de liste :

max_c = max(candies)
result = [(c + extraCandies) >= max_c for c in candies]

Cela reste O(n) temps et O(n) espace

Question 7

Quels cas particuliers faut-il toujours couvrir ?

Answer 7

Liste vide → retourner []

extraCandies négatif ou très grand → la comparaison reste valide

Tous les éléments identiques → tous True si extraCandies ≥ 0