Coding Interview Prep · Leçon

N-ième valeur la plus élevée avec DENSE_RANK

Généraliser à la n-ième valeur distincte et gérer les doublons

N-ième valeur la plus élevée avec DENSE_RANK est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 2 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.

Généraliser au N-ième salaire le plus élevé

Une fois que vous savez trouver le deuxième salaire le plus élevé, les recruteurs enchaînent immédiatement : « Maintenant, donnez-moi le N-ième salaire le plus élevé. » La réponse la plus claire et la plus facile à défendre utilise DENSE_RANK.

Le principe est toujours le même : classer les salaires distincts par ordre décroissant, puis filtrer la ligne dont le rang est égal à N. Comme la logique ne change pas avec N, cette seule approche répond à toute cette famille de questions.

Nous allons construire cette solution, gérer les égalités et les doublons, puis expliquer pourquoi DENSE_RANK est la bonne fonction de classement pour exprimer la notion de « valeur distincte ».

Le modèle fondamental

Voici le modèle réutilisable pour le N-ième salaire le plus élevé. Remplacez la constante par la valeur de N demandée par la personne qui vous recrute.

Vous calculez DENSE_RANK dans une requête interne, car la fonction de fenêtre ne peut pas être utilisée dans WHERE, puis vous filtrez à l’extérieur sur rnk = N. Pour le troisième salaire le plus élevé, définissez le filtre sur rnk = 3.

SELECT salary AS nth_highest
FROM (
  SELECT salary,
         DENSE_RANK() OVER (ORDER BY salary DESC) AS rnk
  FROM employee
) ranked
WHERE rnk = 3;

Comment DENSE_RANK numérote les valeurs distinctes

DENSE_RANK attribue le même rang aux valeurs égales et ne laisse jamais de saut ensuite. C’est exactement la définition de la « N-ième valeur distincte » attendue par les recruteurs.

Pour les salaires 800, 800, 600, 600, 400 :

800 -> rang 1
600 -> rang 2
400 -> rang 3

Le troisième salaire le plus élevé est donc 400, même s’il y a cinq lignes. Les doublons sont automatiquement regroupés dans un même rang.

Pourquoi RANK donne une mauvaise réponse

Remplacez-le par RANK et la réponse devient incorrecte. RANK laisse des sauts proportionnels au nombre de valeurs à égalité.

Pour 800, 800, 600, 600, 400 :

800, 800 -> rang 1 (les deux)
600, 600 -> rang 3 (saut, pas de rang 2)
400 -> rang 5

Le filtrage sur rnk = 3 renvoie 600, tandis que rnk = 2 ne renvoie rien. Sauf si la personne qui vous recrute demande précisément un classement de type compétition, DENSE_RANK est correct pour obtenir le « N-ième salaire distinct ».

Pourquoi ROW_NUMBER est également incorrect ici

ROW_NUMBER attribue un numéro unique à chaque ligne et ignore complètement les égalités. Pour 800, 800, 600, 600, 400, il produit 1, 2, 3, 4, 5.

Ainsi, rn = 3 renvoie 600, mais rn = 2 renvoie le doublon 800, et non une deuxième valeur distincte. ROW_NUMBER répond à la question « quelle est la N-ième ligne ? », et non « quelle est la N-ième valeur distincte ? »

Utilisez ROW_NUMBER uniquement lorsque la question porte réellement sur une ligne précise, par exemple pour dédupliquer des données ou conserver exactement une ligne dans un classement des N premiers éléments par groupe.

SELECT salary, ROW_NUMBER() OVER (ORDER BY salary DESC) AS rn
FROM employee;

Paramétrer N en toute sécurité

Dans du code réel, vous ne coderiez pas le rang en dur. Transmettez N comme paramètre et comparez-le à cette valeur. La définition de la fenêtre reste identique ; seul le filtre externe est paramétré.

C’est également à ce moment que vous pouvez renvoyer tous les salaires à égalité au rang N : comme DENSE_RANK attribue le même rang aux valeurs à égalité, WHERE rnk = N peut renvoyer plusieurs lignes si plusieurs employés partagent le N-ième salaire distinct, ce qui est souvent le comportement souhaité.

SELECT id, salary
FROM (
  SELECT id, salary,
         DENSE_RANK() OVER (ORDER BY salary DESC) AS rnk
  FROM employee
) ranked
WHERE rnk = :n;

La généralisation par comptage corrélé

L’approche antérieure aux fonctions de fenêtre se généralise également : un salaire est le N-ième salaire distinct le plus élevé lorsqu’il existe exactement N - 1 salaires distincts strictement supérieurs à celui-ci.

Pour le troisième salaire le plus élevé, exigez exactement deux salaires distincts supérieurs. Cette méthode fonctionne avec d’anciens moteurs dépourvus de fonctions de fenêtre, mais passe mal à l’échelle, car le comptage interne est réexécuté pour chaque ligne externe.

SELECT DISTINCT salary AS nth_highest
FROM employee e
WHERE (
  SELECT COUNT(DISTINCT e2.salary)
  FROM employee e2
  WHERE e2.salary > e.salary
) = 2;

La forme de fonction MySQL demandée en entretien

Le problème du « N-ième salaire le plus élevé » de style LeetCode demande souvent une fonction stockée qui renvoie une seule valeur. Son corps consiste simplement à envelopper le modèle DENSE_RANK pour renvoyer un salaire.

Vous n’avez pas besoin de mémoriser la syntaxe exacte d’une fonction pour un entretien, mais il est utile de savoir que LIMIT N-1, 1 appliqué à des salaires distincts est l’idiome MySQL concis correspondant.

SELECT DISTINCT salary
FROM employee
ORDER BY salary DESC
LIMIT 1 OFFSET 2;  -- N = 3, so OFFSET N-1

Exemple détaillé : quatrième salaire le plus élevé

Salaires : 1000, 900, 900, 700, 500, 500, 300.

Valeurs distinctes par ordre décroissant avec DENSE_RANK :

1000 -> 1
900 -> 2
700 -> 3
500 -> 4
300 -> 5

Le quatrième salaire le plus élevé est 500. Remarquez que les deux lignes correspondant à 500 partagent le rang 4 ; le filtrage sur rnk = 4 renverra donc les deux employés gagnant 500 si vous sélectionnez également leurs identifiants.

Notes sur les performances

Comment ces approches se comparent-elles à grande échelle ?

DENSE_RANK : un seul tri des données, puis un filtre. Cette méthode est efficace et le planificateur peut utiliser un index sur le salaire pour effectuer le tri.
Comptage corrélé : complexité potentiellement en O(n carré), car l’agrégat interne s’exécute pour chaque ligne. À éviter sur les grandes tables.
LIMIT/OFFSET : rapide pour les petites valeurs de N, mais nécessite tout de même un tri ; les grands décalages parcourent et écartent de nombreuses lignes.

Commencez par DENSE_RANK et vous vous tromperez rarement.

Cas limites à mentionner

Les bons candidats signalent les cas limites avant qu’on ne les interroge à leur sujet :

N supérieur au nombre de salaires distincts : le filtre ne correspond à aucune ligne et renvoie un résultat vide. La leçon 4 explique comment forcer le renvoi d’un seul NULL.
Égalités au rang N : DENSE_RANK renvoie chaque employé à égalité ; déterminez si c’est bien le comportement souhaité.
N = 1 : le modèle fonctionne toujours et renvoie le maximum.

Vérification rapide

Appliquez le modèle du N-ième salaire le plus élevé.

Récapitulatif

Pour trouver le N-ième salaire le plus élevé, une réponse de référence consiste à classer les salaires distincts avec DENSE_RANK() OVER (ORDER BY salary DESC) dans une sous-requête, puis à filtrer avec WHERE rnk = N.

DENSE_RANK signifie « N-ième valeur distincte », les valeurs à égalité partageant le même rang sans aucun saut.
RANK introduit des sauts ; ROW_NUMBER compte les lignes et non les valeurs.
L’astuce du comptage corrélé = N-1 généralise la même idée sans fonctions de fenêtre, mais passe mal à l’échelle.

Signalez toujours le cas limite où « N dépasse le nombre de valeurs disponibles » ; nous le traiterons ensuite.

Questions Fréquemment Posées

La leçon « N-ième valeur la plus élevée avec DENSE_RANK » est-elle gratuite ?

Oui — le texte complet de « N-ième valeur la plus élevée avec DENSE_RANK » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « N-ième valeur la plus élevée avec DENSE_RANK » ?

Généraliser à la n-ième valeur distincte et gérer les doublons Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.

Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?

Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 2 sur 4.

Combien de temps prend la leçon « N-ième valeur la plus élevée avec DENSE_RANK » ?

La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.

Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?

Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.

Toutes les leçons de ce cours

Deuxième salaire le plus élevé : cinq méthodes
N-ième valeur la plus élevée avec DENSE_RANK
Le plus gros salaire par service
Renvoyer NULL lorsqu’il n’existe aucune n-ième valeur

← Retour à Coding Interview Prep