Data Structure & Algorithms
Diseño de algoritmos in-place, contratos de mutación, punteros de lectura y escritura, particiones, aliasing y uso de memoria auxiliar.
Un algoritmo in-place transforma los datos usando una cantidad pequeña de memoria auxiliar, normalmente O(1) o O(log n) según si se cuenta el call stack.
No significa que “no use memoria”. La entrada ya ocupa memoria, existen variables locales y puede haber stack. La afirmación se refiere a memoria adicional que crece con n.
La mutación puede ahorrar copias, pero también cambia el contrato de la función y aumenta el riesgo de efectos laterales.
function reverseInPlace<T>(values: T[]): void {
let left = 0;
let right = values.length - 1;
while (left < right) {
[values[left], values[right]] = [values[right], values[left]];
left += 1;
right -= 1;
}
}O(n);O(1);Versión no mutante:
function reversed<T>(values: readonly T[]): T[] {
const copy = [...values];
reverseInPlace(copy);
return copy;
}O(n);O(n) por la copia;Ambas pueden ser correctas. La API debe declarar cuál ofrece.
Si un algoritmo in-place devuelve una lista de resultados de tamaño n, la salida ocupa O(n). En análisis suele distinguirse:
Por ejemplo, compactar un array y devolver la nueva longitud puede usar O(1) auxiliar. Crear un array con los valores compactados no.
Este patrón modifica un prefijo mientras lee la entrada.
function removeValue<T>(values: T[], target: T): number {
let write = 0;
for (let read = 0; read < values.length; read += 1) {
if (!Object.is(values[read], target)) {
values[write] = values[read];
write += 1;
}
}
return write;
}Después de ejecutar, values[0..write) contiene los valores conservados. Lo que queda después de write no forma parte del resultado lógico.
Antes de cada iteración:
values[0..write) contiene exactamente los valores válidos vistos;read apunta al siguiente elemento por procesar;write <= read.Tiempo O(n), espacio O(1).
La versión anterior conserva el orden relativo porque escribe los valores en el mismo orden en que los lee.
Si el orden no importa, puedes reemplazar un valor eliminado con el último elemento y reducir el límite. Puede hacer menos escrituras, pero cambia el orden.
function removeUnordered<T>(values: T[], target: T): number {
let index = 0;
let length = values.length;
while (index < length) {
if (Object.is(values[index], target)) {
values[index] = values[length - 1];
length -= 1;
} else {
index += 1;
}
}
return length;
}La elección depende del contrato, no solo de velocidad.
Separar elementos según una condición:
function partition<T>(
values: T[],
predicate: (value: T) => boolean,
): number {
let boundary = 0;
for (let index = 0; index < values.length; index += 1) {
if (predicate(values[index])) {
[values[boundary], values[index]] = [values[index], values[boundary]];
boundary += 1;
}
}
return boundary;
}Al terminar:
[0..boundary) cumple predicate
[boundary..n) no cumpleNo es estable: los swaps pueden cambiar el orden relativo.
Clasifica tres grupos en una pasada.
function sortColors(values: number[]): void {
let low = 0;
let current = 0;
let high = values.length - 1;
while (current <= high) {
if (values[current] === 0) {
[values[low], values[current]] = [values[current], values[low]];
low += 1;
current += 1;
} else if (values[current] === 2) {
[values[current], values[high]] = [values[high], values[current]];
high -= 1;
} else {
current += 1;
}
}
}Invariante:
[0..low) ceros
[low..current) unos
[current..high] desconocidos
(high..n) dosesDespués de intercambiar con high, no avanzas current porque el valor recibido todavía no se ha clasificado.
Eliminar elementos con splice mientras avanzas puede saltar posiciones:
for (let index = 0; index < values.length; index += 1) {
if (shouldRemove(values[index])) {
values.splice(index, 1);
}
}Al eliminar, el siguiente elemento se mueve al índice actual, pero el loop incrementa index.
Alternativas:
Además, splice puede desplazar O(n) elementos por eliminación, produciendo O(n²).
Dos variables pueden referenciar el mismo objeto:
const original = [1, 2, 3];
const alias = original;
reverseInPlace(alias);
// original también cambióUna copia superficial crea un array nuevo, pero no clona objetos internos:
const copy = [...users];
copy[0].name = "New";
// users[0].name también cambiaLa mutación segura exige comprender qué nivel de identidad compartes.
function sum(values: readonly number[]): number {
// values.push(1) is rejected by TypeScript.
return values.reduce((total, value) => total + value, 0);
}readonly expresa un contrato en tiempo de compilación. No congela el array en runtime ni vuelve profundamente inmutables sus objetos internos.
Para una función in-place, recibe T[]; para una función que promete no mutar, prefiere readonly T[].
Quick sort puede ser in-place respecto al array, pero su call stack usa:
O(log n) promedio;O(n) peor caso.Por eso algunas definiciones permiten O(log n) stack dentro de “in-place”, mientras otras exigen O(1) estricto. Declara la convención.
Rotar una matriz cuadrada 90 grados puede hacerse transponiendo y revirtiendo filas.
function rotateClockwise(matrix: number[][]): void {
const size = matrix.length;
if (matrix.some((row) => row.length !== size)) {
throw new RangeError("Matrix must be square");
}
for (let row = 0; row < size; row += 1) {
for (let col = row + 1; col < size; col += 1) {
[matrix[row][col], matrix[col][row]] = [
matrix[col][row],
matrix[row][col],
];
}
}
for (const row of matrix) {
reverseInPlace(row);
}
}Tiempo O(n²) porque toca una cantidad proporcional a las celdas. Espacio auxiliar O(1).
El loop de transposición comienza en col = row + 1 para no intercambiar dos veces ni tocar la diagonal.
Algunas permutaciones in-place se descomponen en ciclos. Guardas un valor temporal y mueves cada elemento a su destino hasta regresar al inicio.
El reto es marcar qué posiciones ya fueron procesadas sin usar O(n) memoria. A veces la entrada permite codificar marcas; otras veces no. No fuerces una solución in-place si destruye claridad o exige supuestos no disponibles.
En aplicaciones comunes, una copia clara puede ser preferible a una mutación difícil de verificar.
Comprueba:
Una propiedad útil para reverse:
reverse(reverse(values)) = valuesO(n).splice y saltar elementos.¿Por qué después de intercambiar values[current] con values[high] en Dutch National Flag no se incrementa current?
Porque el valor que llegó desde high todavía pertenece a la región desconocida. Debe clasificarse antes de avanzar; hacerlo de inmediato podría dejarlo en la región incorrecta.