Fundamentos de arrays y operaciones in-place

Internamente, una lista de Python se basa en un array dinámico: un bloque contiguo de memoria en el que los elementos se almacenan en direcciones consecutivas. Esta disposición proporciona un acceso aleatorio O(1) mediante el índice: Python calcula address = base + index × element_size al instante. Las inserciones o eliminaciones en el centro requieren desplazar todos los elementos posteriores, con un coste de O(n). Esta asimetría origina la mayoría de los debates sobre los equilibrios de los arrays en las entrevistas.

Los errores de desfase de uno son la fuente más frecuente de respuestas incorrectas en los problemas con arrays. La indexación basada en cero de Python significa que el último índice válido es len(arr) - 1. Al escribir bucles, decida si necesita < o <= comprobando la condición límite con la entrada válida más pequeña (n=1 o n=2). Antes de enviar la solución, compruebe siempre el límite con ejemplos concretos.

Invertir un array in situ utiliza dos punteros que comienzan en extremos opuestos y avanzan hacia el centro intercambiando elementos hasta encontrarse. Esto requiere un espacio adicional O(1) y un tiempo O(n). La condición left < right (estrictamente menor) garantiza la corrección tanto para longitudes pares como impares: con un número impar de elementos, el elemento central permanece automáticamente en su lugar.

Para rotar un array k posiciones hacia la derecha, puede hacerlo in situ invirtiendo tres segmentos: invierta el array completo, después los primeros k elementos y, por último, los n-k elementos restantes. Esto consigue un tiempo O(n) y un espacio O(1), mucho mejor que el enfoque de O(n) de espacio que utiliza slicing y concatenación. Reduzca siempre k módulo n para gestionar k ≥ n.

Eliminar duplicados o valores objetivo in situ utiliza un puntero de escritura que indica dónde debe escribirse el siguiente elemento válido. El puntero de lectura avanza; cuando encuentra un elemento válido, lo copia en la posición de escritura y avanza ambos punteros. Este es el patrón fundamental de problemas de LeetCode como 'remove element', 'remove duplicates from sorted array' y 'move zeroes'.

Mueva todos los ceros al final de un array y conserve el orden de los elementos distintos de cero. El enfoque del puntero de lectura y escritura coloca cada elemento distinto de cero en la posición de escritura y luego rellena con ceros el tramo final. Un enfoque alternativo intercambia los ceros hacia atrás y conserva el orden sin una segunda pasada de relleno. Ambos enfoques tienen una complejidad temporal de O(n) y espacial de O(1).

Dado un array ordenado de enteros que puede contener valores negativos, devuelva un array con sus cuadrados en orden. El enfoque ingenuo eleva los valores al cuadrado y luego los ordena: O(n log n). El enfoque óptimo de dos punteros aprovecha que los cuadrados mayores proceden de cualquiera de los extremos de la entrada ordenada: compare los valores absolutos de los elementos de los extremos izquierdo y derecho y rellene el resultado de derecha a izquierda en O(n).

El problema de la bandera nacional neerlandesa particiona un array en tres secciones (menores que el pivote, iguales al pivote y mayores que el pivote) in situ mediante tres punteros. Este es el subpaso clave de quicksort y la solución al problema de LeetCode 'sort colors'. Mantener la invariante de que los elementos anteriores al puntero low son < pivot y los posteriores al puntero high son > pivot guía el algoritmo.

Puede modificar los valores de los elementos de forma segura (por ejemplo, multiplicarlos por -1 para marcar los que ya ha visitado) mientras itera, pero no cambie nunca la longitud de una lista durante un bucle for. Un truco de codificación seguro consiste en codificar temporalmente dos valores en un solo entero (por ejemplo, mediante el bit de signo) para simular un booleano adicional por elemento sin asignar espacio extra. Esto aparece en problemas como 'encontrar todos los números que desaparecieron en un array'.

Antes de programar cualquier problema de arrays, repase esta lista mental:

• ¿Está ordenado el array? (permite usar dos punteros y búsqueda binaria)
• ¿Los elementos están dentro de un rango acotado (p. ej., 1..n)? (permite usar trucos basados en índices)
• ¿Es necesario hacerlo in situ? (puntero de lectura y escritura o intercambios)
• ¿Necesita todos los pares o solo uno? (determina si los bucles anidados son aceptables)
• Casos límite: array vacío, un solo elemento, todos los valores iguales

El algoritmo de Kadane encuentra el subarray contiguo de suma máxima en O(n) y con espacio O(1). En cada paso, decida si debe ampliar el subarray actual o comenzar uno nuevo: current = max(num, current + num). Si current + num es menor que num por sí solo, el subarray actual nos está perjudicando y empezamos de nuevo. Mantenga el máximo global durante todo el recorrido.

Ponga a prueba su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.

En esta lección ha aprendido: los arrays ofrecen acceso aleatorio en O(1), pero las inserciones y eliminaciones en el medio cuestan O(n); conocer esta asimetría orienta la elección del algoritmo, el patrón del puntero de lectura y escritura permite eliminar elementos o mover valores in situ en O(n) y con O(1) de espacio, y la codificación con el bit de signo y los trucos que usan el índice como marca permiten resolver en O(1) de espacio problemas que, de otro modo, requerirían un array auxiliar. A continuación exploraremos las sumas de prefijos y los totales acumulados.