Introducción a Arrays y Strings

Casi todos los problemas de DSA empiezan con un arreglo o un string. Entender cómo funcionan internamente cambia la forma en que escribes código eficiente.

Cómo se guarda un arreglo en memoria

Un arreglo es un bloque contiguo de memoria. Si tienes un arreglo de 100 enteros y cada entero ocupa 8 bytes, el arreglo ocupa 800 bytes consecutivos. La dirección del elemento i se calcula como dirección_base + i × tamaño_elemento.

Eso permite acceso en O(1): dada cualquier posición, la computadora calcula la dirección de memoria con una multiplicación y un acceso directo. No importa si el arreglo tiene 10 o 10 millones de elementos, leer arr[i] siempre tarda lo mismo.

Costos típicos

Operación	Complejidad	Por qué
Leer arr[i]	O(1)	Dirección de memoria calculable directamente
Modificar arr[i] = v	O(1)	Igual que leer
Recorrer el arreglo entero	O(n)	Visitar n posiciones
Buscar un valor (sin orden)	O(n)	Hay que mirar todos
Insertar al final	O(1) amortizado	Append en lista dinámica
Insertar al medio	O(n)	Hay que mover todos los que están a la derecha
Borrar del medio	O(n)	Igual: hay que cerrar el hueco

La regla mental: modificar en el medio es caro, modificar en los extremos es barato.

Arrays dinámicos vs arrays fijos

Lenguajes como Python (list), JavaScript (Array), Java (ArrayList) tienen arrays dinámicos: crecen automáticamente cuando hace falta. Cuando se llenan, el lenguaje pide un buffer más grande (típicamente al doble), copia los elementos y libera el viejo.

Eso hace que append sea O(1) amortizado (ya lo vimos en la lección de complejidad). Si insertas 1 millón de elementos uno por uno, el costo total es lineal, aunque algunas operaciones internas individuales sean caras.

C y Rust manejan arrays fijos: definís el tamaño al crear y no cambia. Más rápidos (sin overhead de redimensionado), menos flexibles.

Mutabilidad de arrays vs strings

En la mayoría de los lenguajes, los arrays son mutables (puedes cambiar elementos in-place):

arr = [1, 2, 3]
arr[0] = 99  # ahora arr = [99, 2, 3]

Los strings, sin embargo, son inmutables en Python, JavaScript, Java, C#:

s = "hola"
s[0] = "H"  # TypeError en Python: 'str' object does not support item assignment

Esto tiene consecuencias importantes de performance. Concatenar strings repetidamente en un loop es caro porque cada concatenación crea un string nuevo:

# MAL: O(n²)
resultado = ""
for c in lista:
    resultado += c

Cada += crea un string nuevo de tamaño creciente. Para n caracteres, el costo total es 1 + 2 + 3 + ... + n ≈ n²/2.

# BIEN: O(n)
resultado = "".join(lista)

join reserva el espacio total una vez y copia todos los caracteres. O(n).

En JavaScript es similar:

// MAL: O(n²)
let resultado = "";
for (const c of lista) {
  resultado += c;
}

// BIEN: O(n)
const resultado = lista.join("");

Slicing: cuidado con el costo oculto

Tanto Python como JavaScript permiten "slicing" para tomar una subsección de un arreglo o string:

sub = arr[i:j]  # Python
sub = arr.slice(i, j)  # JS Array
sub = s.substring(i, j)  # JS string

Esto cuesta O(j - i), no O(1). Crea una copia nueva de los elementos del rango. Es fácil olvidarlo y terminar con un algoritmo O(n²) sin querer.

Si necesitas "ventana sobre un arreglo sin copiar", trabajá con índices i y j en lugar de slicing:

def operacion(arr, izq, der):
    # operas directamente sobre arr[izq:der] sin crear copia
    for k in range(izq, der):
        ...

Modificar in-place

"In-place" significa modificar el arreglo original sin crear uno nuevo. Ahorra O(n) memoria.

Ejemplo: revertir un arreglo in-place.

def revertir(arr):
    izq, der = 0, len(arr) - 1
    while izq < der:
        arr[izq], arr[der] = arr[der], arr[izq]
        izq += 1
        der -= 1

Versión no-in-place:

def revertir(arr):
    return arr[::-1]  # crea arreglo nuevo

La diferencia: la primera modifica el arreglo que recibió. La segunda devuelve uno nuevo. En entrevistas, "in-place" suele referirse a la primera y se pide explícitamente.

Lo que practicas en este tema

1. Operaciones in-place sobre arreglos.
2. Slicing en Python vs JS y cuándo es seguro usarlo.
3. Construcción eficiente de strings evitando concatenaciones cuadráticas.
4. Buffers y dynamic arrays desde adentro: cómo se redimensionan y por qué importa.

Estos conceptos aparecen en todos los temas que vienen. Búsqueda binaria, dos punteros, ventana deslizante, todos operan sobre arreglos. Saber qué operaciones son baratas y cuáles caras es lo que diferencia una solución elegante de una que pasa los tests pero sería un desastre en producción.