Patrones Two Pointers HashMap Stack para entrevistas

Tres Patrones Esenciales para Algoritmos en Entrevistas de Código

El patrón de Dos Punteros utiliza dos punteros para recorrer los datos en una sola pasada. Reduce la complejidad de O(n²) a O(n) en palíndromos, pares de elementos y tareas de filtrado.

Dos variantes principales:

• Izquierda-Derecha (convergente): izquierda empieza en el índice 0, derecha en s.length - 1. Los mueves hacia el centro para verificar simetría.
• Lento-Rápido: lento actualiza el resultado, rápido avanza para eliminar duplicados o desplazar elementos.

Ejemplo: verificar un palíndromo ignorando caracteres no alfabéticos.

const isPalindrome = (s) => {
  let left = 0;
  let right = s.length - 1;

  while (left < right) {
    if (s[left] !== s[right]) {
      return false;
    }
    left++;
    right--;
  }

  return true;
};

console.log(isPalindrome("madam")); // true
console.log(isPalindrome("abc")); // false

HashMap: Búsquedas Rápidas y Agrupación

HashMap (objeto o Map) almacena pares clave-valor para acceso en O(1). Ideal para conteos de frecuencia, verificaciones de unicidad, anagramas y caché.

Algoritmo: una pasada para construir, otra para consultar. Evita bucles anidados por completo.

Ejemplo: primer carácter único en una cadena.

const firstUniqueChar = (s) => {
  const map = {};

  for (const char of s) {
    map[char] = (map[char] || 0) + 1;
  }

  for (const char of s) {
    if (map[char] === 1) {
      return char;
    }
  }

  return null;
};

console.log(firstUniqueChar("banana")); // 'b'
console.log(firstUniqueChar("aabbc")); // 'c'

Pila: Manejo de Estructuras LIFO

La Pila sigue el principio Último en Entrar - Primero en Salir. Un array con push/pop brilla en validación de paréntesis, pilas sin recursión y retroceso.

Ejemplo: validar secuencias de paréntesis.

const isValidBrackets = (s) => {
  const stack = [];
  const map = {
    ')': '(',
    ']': '[',
    '}': '{' 
  };

  for (const char of s) {
    if ('([{'.includes(char)) {
      stack.push(char);
    } else {
      const last = stack.pop();
      if (last !== map[char]) {
        return false;
      }
    }
  }

  return stack.length === 0;
};

console.log(isValidBrackets("{[()()]}"));
console.log(isValidBrackets("{[(])}"));

Cuándo Usar Cada Patrón

Antes de codificar, detecta estas señales:

Dos Punteros:

• Array/cadena con simetría (palíndromo).
• Buscar pares de elementos.
• Array ordenado.
• Comparar desde ambos extremos.

HashMap:

• Contar frecuencias o unicidad.
• Anagramas, agrupación.
• Verificar existencia de elementos.
• Datos desordenados que necesitan búsquedas rápidas.

Pila:

• Paréntesis o estructuras anidadas.
• Lógica LIFO (el último abierto se cierra primero).
• Retroceso o historial de estados.

Lecciones Clave

• Dos Punteros ahorra pasadas por los datos, ideal para estructuras lineales.
• HashMap ofrece acceso O(1), cambiando bucles anidados por dos pasadas.
• Pila garantiza el orden correcto de anidamiento sin recursión.
• Practica: resuelve 10 problemas por patrón, luego mézclalos.

Estos patrones resuelven la mayoría de problemas Fáciles/Medios de LeetCode/Codewars. Usarlos regularmente desarrolla la intuición de nivel senior para entrevistas.

— Editorial Team