Arrays y Strings

Arrays y Strings son las estructuras de datos más fundamentales y aparecen en el 80% de los problemas de entrevistas. La técnica Two Pointers usa dos índices que se mueven en el array para encontrar pares, subsecuencias o ventanas sin necesitar bucles anidados, reduciendo O(n²) a O(n).

Sliding Window mantiene una "ventana" de tamaño fijo o variable deslizándose por el array para calcular sumas, máximos o substrings en O(n) en lugar de O(n²).

Hashing (usar un Map/diccionario) es la técnica más poderosa para optimizar arrays: convierte muchos problemas que parecen O(n²) (buscar pares, contar frecuencias, encontrar duplicados) en O(n). El patrón es: en un primer pass, guardar los elementos en un Map. En el segundo pass, buscar en el Map en O(1) en lugar de O(n).

El problema "Two Sum" (encontrar dos números que sumen un objetivo) es el ejemplo más famoso: O(n²) naive vs O(n) con HashMap.

// Two Pointers - O(n) para encontrar par con suma objetivo
function dosSuma(arr, objetivo) {
  let izq = 0, der = arr.length - 1;
  while (izq < der) {
    const suma = arr[izq] + arr[der];
    if (suma === objetivo) return [izq, der];
    suma < objetivo ? izq++ : der--;
  }
  return [];
}
// Requiere array ordenado

// Sliding Window - ventana deslizante
function sumaMaxima(arr, k) {
  let suma = arr.slice(0, k).reduce((a, b) => a + b);
  let maxSuma = suma;
  for (let i = k; i < arr.length; i++) {
    suma = suma - arr[i - k] + arr[i]; // Deslizar ventana
    maxSuma = Math.max(maxSuma, suma);
  }
  return maxSuma;
}
// Máxima suma de k elementos consecutivos - O(n)

// Hashing - frecuencia de caracteres
function esAnagrama(s1, s2) {
  if (s1.length !== s2.length) return false;
  const freq = {};
  for (const c of s1) freq[c] = (freq[c] || 0) + 1;
  for (const c of s2) {
    if (!freq[c]) return false;
    freq[c]--;
  }
  return true;
}

// Prefix Sum - suma acumulada O(1) por consulta
function crearPrefixSum(arr) {
  const prefix = [0];
  for (const n of arr) prefix.push(prefix.at(-1) + n);
  return prefix;
}
function sumaRango(prefix, i, j) {
  return prefix[j+1] - prefix[i]; // O(1)!
}