Problema de Par Sum (Paso a Paso) para Entrevistas de Pizarra

Las entrevistas de pizarra evalúan más que velocidad de resolución de problemas. Evalúan comunicación, claridad y pensamiento estructurado. El método REACTO te da un framework repetible: Repeat, Examples, Approach, Code, Test, Optimize. Los entrevistadores quieren escuchar tu razonamiento en voz alta: un recorrido limpio sin respuesta es mejor que una solución apresurada sin explicación.

El Problema Principal

Dado un array de números y una suma objetivo, determina si algún par de números en el array suma al objetivo. Devuelve un boolean.

• Array [1, 2, 3, 9] con suma 8 → devuelve false (no hay par válido)
• Array [1, 2, 4, 4] con suma 8 → devuelve true (4 + 4 = 8)

R: Repetir la Pregunta

Entrada: un array de enteros y una suma objetivo. Salida: un boolean, true si algún par de números suma al objetivo, false en caso contrario.

Aclaraciones para abordar en voz alta:

• ¿Devolver el par o solo un boolean? → Solo boolean
• ¿Los números pueden ser negativos o desordenados? → Sí
• ¿Se puede usar el mismo elemento dos veces? → No, deben ser dos índices distintos
• ¿Qué pasa si el array está vacío o tiene un elemento? → Devolver false

E: Casos de Ejemplo

Antes de tocar código, recorre ejemplos con el entrevistador. Confirma tu comprensión de edge cases: array vacío, un solo elemento, duplicados, negativos. Aquí es donde muchos candidatos pierden puntos por apresurarse.

• [1, 2, 3, 9] target 8 → false
• [1, 2, 4, 4] target 8 → true (4 + 4)
• [-1, 5, 3] target 4 → true (-1 + 5)
• [] target 5 → false
• [5] target 5 → false (se necesitan dos elementos distintos)

A: Enfoque

Fuerza Bruta: O(n²)

Bucles anidados: para cada elemento, verifica todos los demás. Simple de explicar pero no escala. Menciona esto primero: los entrevistadores aprecian saber que entiendes la solución naive antes de optimizar.

Optimizado: HashSet O(n)

Usa un Set para rastrear los números vistos hasta ahora. Para cada elemento, calcula su complemento (objetivo menos actual). Si el complemento ya está en el Set, existe un par válido. De lo contrario, almacena el número actual y continúa. Una pasada por el array, búsqueda O(1) por paso.

C: Código

function hasPairWithSum(arr: number[], sum: number): boolean {
  const seen = new Set<number>();

  for (const num of arr) {
    const complement = sum - num;

    if (seen.has(complement)) {
      return true;
    }

    seen.add(num);
  }

  return false;
}

console.log(hasPairWithSum([1, 2, 3, 9], 8));  // false
console.log(hasPairWithSum([1, 2, 4, 4], 8));  // true
console.log(hasPairWithSum([-1, 5, 3], 4));    // true

T: Testea Tu Solución

Recorre el algoritmo manualmente con [1, 2, 4, 4], sum=8:

• num=1: complemento=7, no está en seen. Agrega 1. seen={1}
• num=2: complemento=6, no está en seen. Agrega 2. seen={1,2}
• num=4: complemento=4, no está en seen. Agrega 4. seen={1,2,4}
• num=4: complemento=4, ESTÁ en seen → devuelve true

Ahora testea un edge case: array vacío. El bucle nunca ejecuta, devuelve false. Un solo elemento [5] con sum 10: una iteración, complemento=5, seen está vacío, agrega 5, el bucle termina, devuelve false. Comportamiento correcto.

O: Optimizar y Discutir Tradeoffs

La solución con HashSet ya es O(n) en tiempo y O(n) en espacio. Si el entrevistador pregunta sobre reducir espacio: un array ordenado con dos punteros logra O(n log n) en tiempo y O(1) en espacio adicional, pero solo si el ordenamiento es in place. Array.prototype.sort en V8 es TimSort, que usa O(n) de memoria auxiliar y muta el array que le pasas, así que ordenar una copia te devuelve a O(n) en espacio. Cuál es mejor depende de las restricciones: si el input ya está ordenado y la memoria es limitada, dos punteros gana.

// Two-pointer approach (requires sorted input)
function hasPairWithSumSorted(arr: number[], sum: number): boolean {
  let left = 0;
  let right = arr.length - 1;

  while (left < right) {
    const current = arr[left] + arr[right];
    if (current === sum) return true;
    if (current < sum) left++;
    else right--;
  }

  return false;
}

// Input must be sorted
console.log(hasPairWithSumSorted([1, 2, 3, 9], 8));  // false
console.log(hasPairWithSumSorted([1, 2, 4, 4], 8));  // true

Bonus: Datos en Streaming

Un entrevistador podría extender el problema: ¿qué pasa si el input es un stream en lugar de un array finito? Puedes aplicar la misma lógica de HashSet usando un generador, pero con una advertencia importante: si no existe un par en el stream, la función nunca termina. En una entrevista, mencionar esta limitación explícitamente demuestra madurez.

function hasPairWithSumStream(
  stream: Iterable<number>,
  sum: number,
  limit = 10_000  // guard against infinite streams with no solution
): boolean {
  const seen = new Set<number>();
  let count = 0;

  for (const num of stream) {
    if (count++ >= limit) return false;  // safety exit: false here means 'not found within limit'
    const complement = sum - num;
    if (seen.has(complement)) return true;
    seen.add(num);
  }

  return false;
}

// Example: finite generator
function* numberStream(values: number[]) {
  for (const v of values) yield v;
}

console.log(hasPairWithSumStream(numberStream([1, 2, 4, 4]), 8));  // true

Lee ese guard con atención, porque cambia lo que significa la función. Devolver false después del límite dice 'no existe ningún par', cuando todo lo que el código sabe es 'no hay par en los primeros 10.000 valores'. Eso es un falso negativo, y es la mitad más interesante del tradeoff. Si quien llama necesita distinguir ambos casos, devuelve tres estados en lugar de un booleano: encontrado, no encontrado, límite alcanzado. Nombrar lo que te cuesta tu salida de seguridad vale más en una entrevista que el guard mismo.

Conceptos Clave Que Debes Dominar

Set: almacena valores únicos con operaciones add y has en O(1) promedio, y di 'promedio' en voz alta, porque el hashing se degrada en el peor caso. Más eficiente que un array para verificaciones de pertenencia. La estructura de datos central detrás de esta solución.

for...of: itera sobre cualquier iterable (array, Set, output de generador). No requiere gestión de índices, funciona limpiamente con generadores.

Funciones generadoras: pausan y reanudan la ejecución usando yield. Devuelven un iterador que produce valores bajo demanda. Útil para simular streams o secuencias lazy. El punto clave en entrevistas: los generadores son lazy, pero si no hay condición de terminación y el problema no tiene solución, la iteración nunca se detiene.

En una entrevista, la calidad de tu explicación es tan valiosa como la corrección de tu código. Recorre el algoritmo paso a paso, testea tu propia solución en voz alta, y nombra los tradeoffs antes de que el entrevistador pregunte.

Referencias

• MDN Web Docs. Set. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set
• MDN Web Docs. Iterators and Generators. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Iterators_and_generators
• LeetCode. Two Sum (classic variant). https://leetcode.com/problems/two-sum/
• GeeksforGeeks. Two Sum, Pair with Given Sum. https://www.geeksforgeeks.org/dsa/check-if-pair-with-given-sum-exists-in-array/