Data Structure & Algorithms
Arrays, strings y matrices
Costos y modelos de arrays dinámicos, strings UTF-16 y matrices, incluyendo copias, recorridos, typed arrays, grids y casos límite.
- Última actualización
- Actualizada
- Nivel
- Fundamentos
Data Structure & Algorithms
Costos y modelos de arrays dinámicos, strings UTF-16 y matrices, incluyendo copias, recorridos, typed arrays, grids y casos límite.
Arrays, strings y matrices son representaciones secuenciales. Gran parte de DSA comienza aquí porque sus índices permiten acceso directo y sus recorridos hacen visibles patrones de acumulación, ventanas, partición y búsqueda.
Un array dinámico ofrece acceso por índice O(1), pero insertar o eliminar en una posición puede requerir desplazar elementos. Esa diferencia entre acceso y modificación estructural es fundamental.
Conceptualmente, un array almacena elementos en posiciones consecutivas:
índice: 0 1 2 3
valor: [A] [B] [C] [D]Si cada elemento ocupa un tamaño conocido, la dirección de index puede calcularse:
base + index × elementSizePor eso el acceso es O(1): no recorre los elementos anteriores.
Los arrays de JavaScript son objetos optimizados por el engine y pueden cambiar de representación interna. El modelo de array dinámico sigue siendo útil para analizar sus operaciones habituales, pero no debes asumir una distribución física específica del runtime.
| Operación | Costo típico | Razón |
|---|---|---|
| Acceso por índice | O(1) | Cálculo directo |
| Actualizar índice | O(1) | Posición conocida |
| Buscar sin orden | O(n) | Puede estar en cualquier posición |
| Push | O(1) amortizado | Escribe al final; ocasionalmente crece |
| Pop | O(1) | Retira el final |
| Insertar/eliminar al inicio | O(n) | Desplaza elementos |
| Insertar/eliminar en medio | O(n) | Desplaza sufijo |
shift y unshift pueden ser lineales. No los uses para implementar una queue y después declarar operaciones O(1).
Un array dinámico mantiene:
Al llenarse, crea almacenamiento mayor y copia elementos.
length 4, capacity 4
[A B C D]
push E → reservar capacity 8 y copiar
[A B C D E _ _ _]Una expansión cuesta O(n), pero si la capacidad se multiplica geométricamente, push cuesta O(1) amortizado.
const values = Array(3);Crea tres holes, no tres valores undefined explícitos. Algunos métodos omiten holes y otros los observan de manera diferente.
0 in values; // falsePara inicializar valores:
const zeros = Array(3).fill(0);Con objetos, fill reutiliza la misma referencia:
const rows = Array(3).fill([]); // Wrong for independent rows.
rows[0].push(1); // Appears in every row.Usa:
const rows = Array.from({ length: 3 }, () => [] as number[]);function sum(values: readonly number[]): number {
let total = 0;
for (let index = 0; index < values.length; index += 1) {
total += values[index];
}
return total;
}Tiempo O(n), espacio O(1).
El loop establece un invariante sencillo: antes de cada iteración, total es la suma del prefijo values[0..index).
for...of: valores iterables.for...in: nombres de propiedades enumerables; no es la opción normal para arrays.forEach: no permite break o continue convencional.map, filter, reduce: expresan transformaciones, pero crean salidas o callbacks y esos costos deben contarse.Elegir sintaxis no cambia automáticamente Big O, pero sí mutación, memoria y control de flujo.
const copy = [...values];
const segment = values.slice(left, right);Ambas copian referencias:
copy: O(n) tiempo y memoria;slice: O(right - left).Una solución que llama slice dentro de un loop puede ocultar complejidad cuadrática.
La copia es superficial. Los objetos internos siguen compartidos.
Los strings son inmutables. Operaciones que parecen modificarlos crean un nuevo string.
let text = "cat";
text += "s";Construir repetidamente con concatenaciones puede tener costos dependientes del engine. Para muchas piezas, un array y join expresa claramente la intención:
const pieces: string[] = [];
pieces.push("a", "b", "c");
const result = pieces.join("");JavaScript indexa strings por code units UTF-16, no por caracteres visibles.
"😀".length; // 2
"😀"[0]; // half of a surrogate pairfor...of y spread recorren code points:
[..."😀"].length; // 1Pero un grapheme cluster visible puede contener varios code points:
familia, bandera, letra + acento combinadoPara segmentación de usuario, Intl.Segmenter puede ser necesario.
Estas cadenas pueden verse iguales y tener secuencias distintas:
const composed = "é";
const decomposed = "e\u0301";
composed === decomposed; // false
composed.normalize("NFC") === decomposed.normalize("NFC"); // trueAntes de frequency counting, hashing o comparación, define si deben normalizarse y qué reglas de mayúsculas o locale aplican.
Como son inmutables, una operación in-place real sobre caracteres requiere convertir a una representación mutable:
const characters = [...text];
reverseInPlace(characters);
const reversed = characters.join("");Esto usa O(n) memoria. Decir O(1) porque el swap interno es constante ignoraría la conversión.
Una matriz suele representarse como array de filas:
const matrix: number[][] = [
[1, 2, 3],
[4, 5, 6],
];No es necesariamente un bloque contiguo. Cada fila es un array independiente.
function assertRectangular<T>(matrix: readonly (readonly T[])[]): void {
const columns = matrix[0]?.length ?? 0;
if (matrix.some((row) => row.length !== columns)) {
throw new RangeError("Matrix must be rectangular");
}
}Una matriz irregular puede ser válida como estructura jagged, pero algoritmos que suponen rows × cols deben comprobarlo.
function matrixSum(matrix: readonly (readonly number[])[]): number {
let total = 0;
for (let row = 0; row < matrix.length; row += 1) {
for (let col = 0; col < matrix[row].length; col += 1) {
total += matrix[row][col];
}
}
return total;
}Sea N la cantidad total de celdas. Tiempo O(N). Para matriz rectangular rows × cols, también se escribe O(rows · cols).
Dos loops anidados no implican O(n²) si las dimensiones son variables distintas o si el total de elementos es N.
const directions = [
[-1, 0],
[1, 0],
[0, -1],
[0, 1],
] as const;
function neighbors(
row: number,
col: number,
rows: number,
cols: number,
): Array<[number, number]> {
const result: Array<[number, number]> = [];
for (const [rowDelta, colDelta] of directions) {
const nextRow = row + rowDelta;
const nextCol = col + colDelta;
if (
nextRow >= 0 &&
nextRow < rows &&
nextCol >= 0 &&
nextCol < cols
) {
result.push([nextRow, nextCol]);
}
}
return result;
}Grids suelen modelarse como grafos implícitos: cada celda es un vértice y las direcciones definen aristas. No necesitas construir adjacency lists si puedes generar vecinos al vuelo.
Una matriz rectangular puede mapearse a un array:
index = row × cols + col
row = floor(index / cols)
col = index mod colsÚtil para:
Uint8Array, Int32Array, Float64Array y similares usan elementos numéricos de tamaño fijo.
Ventajas:
Limitaciones:
const bytes = new Uint8Array([255]);
bytes[0] += 1; // wraps to 0El tipo forma parte de la correctitud.
Arrays ofrecen:
O(1);Linked lists ofrecen:
O(1) en posición ya conocida;La operación dominante decide. No elijas linked list solo porque “insertar es rápido” si primero debes buscar la posición.
undefined como valor real;fill;O(1).shift.slice, spread y filter asignan memoria.for...in para valores de array.string.length como caracteres visibles.O(n²) sin definir dimensiones.O(1) amortizado, no peor caso constante.¿Por qué Array(3).fill([]) suele ser incorrecto para crear tres filas independientes?
Porque fill coloca la misma referencia de array en las tres posiciones. Modificar una fila modifica el único array compartido y el cambio aparece en todas.