Bases des tableaux et opérations en place

En interne, une liste Python repose sur un tableau dynamique — un bloc de mémoire contigu où les éléments sont stockés à des adresses consécutives. Cette disposition permet un accès aléatoire en O(1) par indice : Python calcule instantanément address = base + index × element_size. Les insertions ou suppressions au milieu nécessitent de décaler tous les éléments suivants, ce qui coûte O(n). Cette asymétrie est à l’origine de la plupart des discussions sur les compromis liés aux tableaux en entretien.

Les erreurs de décalage d’une unité sont la source la plus fréquente de mauvaises réponses dans les problèmes de tableaux. L’indexation à partir de 0 de Python signifie que le dernier indice valide est len(arr) - 1. Lorsque vous écrivez des boucles, déterminez si vous avez besoin de < ou de <= en vérifiant la condition aux limites avec la plus petite entrée valide (n=1 ou n=2). Vérifiez toujours vos limites avec des exemples concrets avant de valider votre réponse.

Inverser un tableau en place consiste à utiliser deux pointeurs partant des extrémités opposées et à les échanger en progressant vers le centre jusqu’à leur rencontre. Cela nécessite un espace supplémentaire en O(1) et un temps en O(n). La condition left < right (strictement inférieur) garantit la correction pour les longueurs paires comme impaires : avec un nombre impair d’éléments, l’élément central reste automatiquement à sa place.

Faire pivoter un tableau vers la droite de k positions peut se faire en place en inversant trois segments : inversez tout le tableau, puis les k premiers éléments, puis les n-k éléments restants. Cette méthode atteint un temps en O(n) et un espace en O(1), ce qui est bien meilleur que l’approche en O(n) spatial qui consiste à découper puis concaténer. Réduisez toujours k modulo n pour gérer le cas k ≥ n.

Supprimer les doublons ou les valeurs cibles en place utilise un pointeur d’écriture qui indique où doit être écrit le prochain élément valide. Le pointeur de lecture parcourt le tableau vers l’avant ; lorsqu’il trouve un élément valide, il le copie à la position d’écriture, puis avance les deux pointeurs. C’est le motif central de problèmes LeetCode comme « supprimer un élément », « supprimer les doublons d’un tableau trié » et « déplacer les zéros ».

Déplacez tous les zéros à la fin d’un tableau tout en préservant l’ordre des éléments non nuls. L’approche du pointeur de lecture-écriture place chaque élément non nul à la position d’écriture, puis remplit la fin avec des zéros. Une autre approche échange les zéros vers l’arrière, en préservant l’ordre sans seconde passe de remplissage. Les deux approches s’exécutent en O(n) et utilisent O(1) espace supplémentaire.

Étant donné un tableau trié d’entiers, éventuellement négatifs, renvoyez un tableau contenant leurs carrés dans l’ordre croissant. L’approche naïve consiste à calculer les carrés, puis à trier le résultat : O(n log n). L’approche optimale à deux pointeurs exploite le fait que les plus grands carrés proviennent de l’une ou l’autre extrémité du tableau d’entrée trié : comparez les valeurs absolues des éléments les plus à gauche et les plus à droite, puis remplissez le résultat de droite à gauche en O(n).

Le problème du drapeau national néerlandais partitionne un tableau en trois sections (inférieure au pivot, égale au pivot, supérieure au pivot) en place à l’aide de trois pointeurs. Il s’agit de l’étape clé du tri rapide et de la solution LeetCode « sort couleurs ». Le maintien de l’invariant selon lequel les éléments situés avant le pointeur bas sont < pivot et ceux situés après le pointeur haut sont > pivot guide l’algorithme.

Vous pouvez sans risque modifier les valeurs des éléments (par exemple, les multiplier par -1 pour marquer les éléments déjà visités) pendant une itération, mais ne modifiez jamais la longueur d’une liste pendant une boucle for. Une astuce d’encodage sûre consiste à coder temporairement deux valeurs dans un seul entier (par exemple, à l’aide du bit de signe) afin de simuler un booléen supplémentaire par élément sans allouer d’espace supplémentaire. Cette technique apparaît dans des problèmes comme « trouver tous les nombres absents d’un tableau ».

Avant de programmer une solution à un problème de tableau, parcourez cette liste de contrôle mentale :

• Le tableau est-il trié ? (cela permet d’utiliser deux pointeurs ou une recherche binaire)
• Les éléments sont-ils bornés (par exemple, de 1 à n) ? (cela permet des astuces fondées sur les indices)
• Le traitement en place est-il requis ? (pointeur de lecture-écriture ou échanges)
• Ai-je besoin de toutes les paires ou d’une seule ? (cela détermine si des boucles imbriquées sont acceptables)
• Cas limites : tableau vide, élément unique, valeurs toutes identiques

L’algorithme de Kadane trouve le sous-tableau contigu de somme maximale en O(n) et avec un espace O(1). À chaque étape, déterminez s’il faut prolonger le sous-tableau actuel ou en commencer un nouveau : current = max(num, current + num). Si current + num est inférieur à num seul, le sous-tableau actuel nous pénalise et nous repartons de zéro. Suivez le maximum global tout au long du parcours.

Vérifiez votre compréhension des concepts de structures de données et d’algorithmes — préparation aux entretiens de programmation — présentés dans cette leçon.

Dans cette leçon, vous avez appris que les tableaux offrent un accès aléatoire en O(1), mais que les insertions et suppressions au milieu coûtent O(n) — connaître cette asymétrie guide le choix de l’algorithme, que le schéma du pointeur de lecture-écriture supprime des éléments ou déplace des valeurs en place en O(n) avec un espace O(1), et que le codage à l’aide du bit de signe et les astuces utilisant l’indice comme marqueur permettent des solutions en espace O(1) à des problèmes qui nécessiteraient autrement un tableau auxiliaire. Nous allons maintenant étudier les sommes préfixes et les totaux cumulés.