Mon obsession pour LeetCode 41 : Plongeon en profondeur dans le casse-tête du premier entier positif manquant

Le problème "First Missing Positive" de LeetCode (numéro 41) est devenu ma dernière obsession en matière de codage. Il s'agit d'une énigme d'une simplicité trompeuse qui a accaparé mes pensées, me poussant à explorer ses subtilités et à concevoir la solution TypeScript la plus efficace possible. Cet article ne traite pas seulement de réussir les entretiens de codage (bien que ce soit un avantage appréciable). Il s'agit de la pure joie de la résolution de problèmes, du frisson de l'optimisation et de la beauté élégante d'un code efficace. Et comme je suis un peu passionné de mathématiques, nous allons même nous pencher sur les fondements mathématiques de la solution.

Le Problème : Un Loup Déguisé en Mouton

Le problème présente un tableau non trié d'entiers. Votre tâche : trouver le plus petit entier positif manquant. Cela semble simple ? Détrompez-vous. Les contraintes de complexité temporelle $O(n)$ et spatiale $O(1)$ transforment cette tâche apparemment simple en une énigme algorithmique stimulante.

Premières Difficultés : Le Piège de la Force Brute

Mes premières tentatives impliquaient le tri (violant la contrainte de temps $O(n)$) et les ensembles de hachage (dépassant la limite d'espace $O(1)$). De toute évidence, une approche plus sophistiquée était nécessaire.

L'Eurêka : Transformation sur Place

L'idée clé a été de réaliser que je pouvais utiliser le tableau d'entrée lui-même comme table de hachage. En réorganisant les éléments, je pouvais placer le nombre $x$ à l'index $x - 1$ (si $1 \le x \le n$, où $n$ est la longueur du tableau). Cette transformation sur place ouvre la voie à une solution efficace.

Évolution du Code : Une Saga TypeScript

Voici la chronique de l'évolution de mon code, avec des explications détaillées et des idées mathématiques :

Version 1 : L'Approche Naïve (avec des Échanges Redondants)

function firstMissingPositive(nums: number[]): number {
  const n = nums.length

  // Placer chaque nombre à sa position correcte s'il est dans l'intervalle [1, n]
  for (let i = 0; i < n; i++) {
    while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
      const correctIndex = nums[i] - 1
      ;[nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]] // Échange
    }
  }

  // Trouver le premier positif manquant
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  // Si tous les nombres sont à leurs positions correctes, le nombre manquant est n + 1
  return n + 1
}

Cette version, bien que fonctionnelle, souffre d'échanges redondants. Le nombre d'échanges dans le pire des cas approche $O(n^2)$, bien que le cas moyen soit plus proche de $O(n)$.

Explication :

1. Réorganiser le tableau : Chaque nombre nums[i] est placé à son index "correct" (nums[i] - 1) s'il est dans l'intervalle [1, n] et non déjà à la bonne position.

2. Identifier le positif manquant : Après le réarrangement, le premier index i où nums[i] !== i + 1 indique que i + 1 est l'entier positif manquant.

3. Retourner n + 1 si nécessaire : Si tous les nombres de 1 à n sont aux bonnes positions, le nombre manquant est n + 1.

Points Clés :

• Réarrangement sur place : Nous modifions le tableau lui-même pour éviter d'utiliser de l'espace supplémentaire.
• Efficacité : Le réarrangement et l'analyse finale prennent tous deux un temps $O(n)$, garantissant des performances optimales.

Version 2 : Amélioration des Performances (Élimination des Échanges Redondants)

function firstMissingPositive(nums: number[]): number {
  const n = nums.length
  let idx = 0

  // Réorganiser les nombres à leurs positions correctes si possible
  while (idx < n) {
    const correctIdx = nums[idx] - 1
    if (correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx]) {
      // Échange sans utiliser de variable temporaire
      ;[nums[idx], nums[correctIdx]] = [nums[correctIdx], nums[idx]]
    } else {
      idx++
    }
  }

  // Identifier le premier positif manquant
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  return n + 1
}

Explication :

1. Réarrangement efficace :

   • La boucle while échange directement les éléments à leurs positions correctes (nums[idx] - 1) uniquement lorsque le nombre est dans l'intervalle valide [1, n] et non déjà à sa position correcte.
   • La condition if garantit que les nombres invalides ou déjà corrects sont ignorés sans échanges inutiles.

2. Vérification directe de l'index :

   • Pendant la phase de réarrangement, les échanges invalides et les opérations redondantes sont évités en vérifiant la plage et la valeur de nums[idx].

3. Échange efficace en mémoire :

   • L'utilisation de la déstructuration ([nums[idx], nums[correctIdx]] = [nums[correctIdx], nums[idx]]) élimine le besoin d'une variable temporaire, minimisant l'utilisation de la mémoire.

4. Boucles minimales :

   • L'algorithme n'utilise que deux passages linéaires :
     • Un pour réorganiser le tableau sur place.
     • Un autre pour trouver le premier positif manquant.

Analyse de la Complexité :

• Complexité temporelle :
  • La boucle while et la boucle for s'exécutent toutes deux en $O(n)$, ce qui rend la complexité temporelle totale égale à $O(n)$.
• Complexité spatiale :
  • L'algorithme fonctionne sur place sans utiliser de structures de données auxiliaires, donc la complexité spatiale est $O(1)$.

Pourquoi ce code est optimal :

• Performances : La boucle while rationalisée garantit un minimum d'opérations redondantes, maximisant la vitesse.
• Efficacité mémoire : L'utilisation de l'échange sur place et l'évitement des variables supplémentaires garantissent l'empreinte mémoire la plus faible possible.

Version 3 : Optimisée pour la Mémoire (Utilisation Minimale de l'Espace)

function firstMissingPositive(nums: number[]): number {
  const n = nums.length
  let idx = 0

  while (idx < n) {
    const correctIdx = nums[idx] - 1

    if (correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx]) {
      nums[idx] = nums[correctIdx]
      nums[correctIdx] = correctIdx + 1
    } else {
      idx++
    }
  }

  for (let idx = 0; idx < n; idx++) {
    if (nums[idx] !== idx + 1) {
      return idx + 1
    }
  }

  return nums.length + 1
}

Optimisations Clés de la Mémoire :

1. Mises à jour sur place avec un minimum de variables temporaires :

   • Au lieu d'utiliser une variable temp pour l'échange, ce code modifie directement le tableau avec nums[idx] = nums[correctIdx]; nums[correctIdx] = correctIdx + 1.
   • Cela élimine le besoin d'une variable temporaire, réduisant la surcharge mémoire d'une quantité constante.

2. Moins de valeurs temporaires dans la boucle :

   • Le code calcule correctIdx directement dans la boucle, évitant le besoin de stocker des variables intermédiaires supplémentaires en dehors de la logique principale.
   • Moins d'affectations de variables signifient une utilisation légèrement inférieure de la mémoire par itération.

3. Passage unique pour le réarrangement :

   • Contrairement au premier code qui utilise des conditions imbriquées dans la boucle while, cette implémentation effectue des échanges ou fait avancer l'index de manière plus rationalisée, réduisant la profondeur de la pile d'exécution et l'utilisation de la mémoire.
   • La structure de la boucle (while avec un seul incrément ou réarrangement) est plus directe, nécessitant moins de valeurs auxiliaires.

4. Aucune vérification redondante :

   • Les vérifications pour correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx] sont concises et empêchent les opérations inutiles qui pourraient utiliser temporairement la mémoire de la pile ou du cache du processeur.
   • Cela évite le besoin d'allouer des ressources supplémentaires pour des opérations qui ne contribueront pas au résultat.

Pourquoi cela fait une différence en termes de mémoire :

• Stockage temporaire réduit : En ne s'appuyant pas sur une variable temp et en minimisant les calculs intermédiaires, l'empreinte mémoire est plus petite.
• Exécution rationalisée : Moins d'étapes et une logique plus simple se traduisent par une utilisation moindre de la mémoire par opération.
• Amélioration de l'utilisation du cache : Le modèle d'accès linéaire et prévisible de l'algorithme améliore les performances du cache du processeur, réduisant indirectement la surcharge mémoire.

L'accent mis par cette solution sur les mises à jour directes sur place, l'utilisation minimale de variables et les modèles d'accès mémoire efficaces en font la meilleure en termes d'efficacité mémoire. Bien que les économies soient constantes ($O(1)$), elles sont suffisamment importantes pour s'inscrire sur des plates-formes compétitives comme LeetCode, en particulier pour les grands ensembles de données.

Version 4 : Le Chef-d'œuvre Optimisé (Échange sur Place, Pas de Variable Temporaire)

function firstMissingPositive(nums: number[]): number {
  for (let i = 0; i < nums.length; i++) {
    while (nums[i] !== i + 1) {
      if (nums[i] <= 0 || nums[i] > nums.length || nums[i] === nums[nums[i] - 1]) {
        break
      }

      const temp = nums[i]
      nums[i] = nums[temp - 1]
      nums[temp - 1] = temp
    }
  }

  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  return nums.length + 1
}

Cette version finale atteint à la fois des performances optimales et une utilisation minimale de la mémoire grâce à un échange élégant sur place sans variable temporaire. La complexité temporelle est maintenant fermement $O(n)$, et la complexité spatiale est $O(1)$, répondant à toutes les exigences. Mathématiquement, nous effectuons une sorte de permutation cyclique dans le tableau pour placer les éléments à leurs positions "correctes".

En ajoutant une vérification (nums[i] === nums[nums[i] - 1]), nous évitons les échanges inutiles. Cela améliore considérablement les performances, rapprochant la complexité temporelle du $O(n)$ souhaité.

Différences Clés dans l'Implémentation :

1. Éviter les échanges redondants :

   • Le code fourni vérifie explicitement si nums[i] === nums[nums[i] - 1] avant d'effectuer l'échange. Cela évite les échanges inutiles lorsque le nombre est déjà à la bonne position ou que des doublons existent.
   • Dans la première implémentation, cette vérification est omise, ce qui peut entraîner des échanges redondants même lorsqu'ils sont inutiles. Chaque échange supplémentaire ajoute une surcharge, en particulier pour les grands tableaux.

2. Comparaison d'index directe :

   • Le code fourni utilise while (nums[i] !== i + 1) pour garantir qu'un nombre est échangé à plusieurs reprises à sa position correcte jusqu'à ce qu'il soit correctement placé ou qu'une condition invalide soit rencontrée. Cela élimine les itérations de boucle inutiles.
   • Le premier code ne compare pas explicitement le nombre à son index prévu dans la condition de la boucle. Il peut effectuer plus d'opérations dans les cas où les nombres nécessitent un déplacement minimal.

3. Vérifications conditionnelles optimisées :

   • En combinant les conditions dans un seul bloc if (par exemple, nums[i] <= 0 || nums[i] > nums.length || nums[i] === nums[nums[i] - 1]), le code évite les frais généraux supplémentaires provenant de vérifications ou de calculs inutiles.

Pourquoi cela est important dans LeetCode :

• Cohérence du temps d'exécution :

  • Les mesures du temps d'exécution de LeetCode peuvent être sensibles aux opérations inutiles, telles que les échanges redondants ou les comparaisons supplémentaires.
  • Le code fourni minimise ces opérations, ce qui conduit à un temps d'exécution plus rapide en moyenne.

• Efficacité du cache :

  • Moins d'échanges et une logique de boucle plus simple entraînent une meilleure utilisation du cache du processeur. Les processeurs modernes bénéficient de modèles d'accès prévisibles et rationalisés, que le code fourni présente.

Résultats

Voici le résumé présenté sous forme de tableau :

Ce tableau met en évidence les compromis et l'optimalité de la solution finale.

Le résumé indique que la tentative pour les meilleures performances et la meilleure mémoire est en effet la plus optimisée, atteignant :

• Temps d'exécution de 1 ms : Correspondant au résultat le plus rapide en termes de performances.
• Utilisation de la mémoire de 58,9 Mo : Légèrement supérieure au clone "meilleure mémoire" mais inférieure aux autres tentatives.

Analyse :

1. Temps d'exécution :

   • Le temps d'exécution de 1 ms montre que l'approche optimisée élimine les vérifications redondantes et les échanges inutiles.
   • La complexité temporelle cohérente de $O(n)$ garantit l'évolutivité pour les ensembles de données plus importants.

2. Mémoire :

   • 58,9 Mo est compétitif, montrant que l'empreinte mémoire est faible malgré l'exécution rapide. Cette légère augmentation par rapport à la "meilleure mémoire" (58,5 Mo) peut être due à des différences dans la déstructuration ou des optimisations spécifiques au moteur.

3. Compromis :

   • La solution "meilleure mémoire" sacrifie légèrement le temps d'exécution pour une utilisation de la mémoire inférieure.
   • La solution "meilleures performances" se concentre davantage sur la vitesse mais utilise un peu plus de mémoire.

Conclusion :

La solution optimisée trouve un bon équilibre :

• Temps d'exécution de 1 ms aussi rapide que le code le plus performant.
• Utilisation de la mémoire de 58,9 Mo proche du meilleur résultat en termes de mémoire, avec une surcharge négligeable.

C'est un choix complet, surtout pour les scénarios où les performances et la mémoire sont toutes deux critiques.

Fondements Mathématiques : Permutations Cycliques et Principe des Tiroirs

L'idée principale tourne autour du concept de permutations cycliques. Nous visons à créer un cycle où chaque nombre $x$ est placé à l'index $x - 1$. La boucle while parcourt efficacement ces cycles, garantissant que chaque élément trouve sa place désignée.

Le principe des tiroirs joue subtilement un rôle ici. Puisque nous avons $n$ positions possibles (index $0$ à $n-1$) et que nous recherchons un entier positif manquant dans l'intervalle $[1, n+1]$, si tous les nombres de 1 à $n$ sont présents, le nombre manquant doit être $n + 1$.

L'Obsession Continue...

Ma fascination pour LeetCode 41 demeure. Je suis constamment à la recherche d'optimisations supplémentaires et d'idées plus approfondies. Rejoignez-moi dans cette quête ! Partagez vos pensées, vos propres solutions et explorons ensemble l'intersection élégante des mathématiques et des algorithmes.