Algoritmos y Estructuras de Datos

Devolvé `[i, j]` con `i < j` tal que `arr[i] + arr[j] === objetivo`. Si hay varios pares, el de menor `i` (y su primer `j`). Probá con hash map en una pasada. ```ts function dosSuma(arr, objetivo) { const vistos = new Map(); for (let j = 0; j < arr.length; j++) { const falta = objetivo - arr[j]; if (vistos.has(falta)) return [vistos.get(falta), j]; if (!vistos.has(arr[j])) vistos.set(arr[j], j); } return []; } ```

Devolvé el elemento que aparece MÁS de n/2 veces (existe garantido). Sin ordenar: intentá el algoritmo de Boyer-Moore (candidato + contador). ```ts function mayoritario(arr) { let candidato = arr[0]; let votos = 1; for (let i = 1; i < arr.length; i++) { votos += arr[i] === candidato ? 1 : -1; if (votos === 0) { candidato = arr[i]; votos = 1; } } return candidato; } ```

Una escalera de `n` escalones se sube de a 1 o de a 2 por vez. Devolvé de cuántas formas distintas se llega al escalón `n`. ```ts function escaleras(n) { if (n <= 2) return n; let a = 1; let b = 2; for (let i = 3; i <= n; i++) [a, b] = [b, a + b]; return b; } ```

Devolvé la suma del subarray CONTIGUO de mayor suma. El array tiene al menos un elemento. ```ts function subarrayMaximo(arr) { let mejor = arr[0]; let actual = arr[0]; for (let i = 1; i < arr.length; i++) { actual = Math.max(arr[i], actual + arr[i]); mejor = Math.max(mejor, actual); } return mejor; } ```

Porque el hash de la clave te da directamente el índice del bucket: no comparás contra la colección, solo contra los pocos elementos de ese bucket (longitud promedio ~1).

Devolvé `true` si cada paréntesis/llave/corchete que se abre se cierra en el orden correcto. Usá un stack. ```ts function balanceados(s) { const pares = { ")": "(", "]": "[", "}": "{" }; const stack = []; for (const c of s) { if ("([{".includes(c)) stack.push(c); else if (c in pares) { if (stack.pop() !== pares[c]) return false; } } return stack.length === 0; } ```

Devolvé los elementos comunes a ambos arrays, SIN duplicados y ORDENADOS de menor a mayor. ```ts function interseccion(a, b) { const setB = new Set(b); return [...new Set(a)].filter((x) => setB.has(x)).sort((x, y) => x - y); } ```

Hash map (clave → nodo) + doubly linked list en orden de uso: get/put mueven el nodo al frente en O(1); la evicción saca el último de la lista y lo borra del hash.

Devolvé el array rotado `k` posiciones a la derecha (los últimos pasan al frente). `k` puede ser mayor que la longitud. ```ts function rotar(arr, k) { const n = arr.length; if (n === 0) return arr; const r = k % n; return [...arr.slice(n - r), ...arr.slice(0, n - r)]; } ```

[5, 7, 15, 20, 10]: el 7 entra al final (índice 4), sube intercambiando con su padre 10 (índice 1) y se frena con el padre 5.

No siempre parte en dos: con el pivote en un extremo de un array ya ordenado, cada partición separa 1 elemento de n−1 → n niveles de recursión que cuestan O(n) cada uno.

prev = 2→1 (con 1→null) y curr = 3; el nodo 3 todavía apunta al 2 y se corrige en la vuelta siguiente.

Con un hash set de vistos: por cada elemento x consultás si existe `objetivo − x`; si no, agregás x. Devuelve el par en una pasada.

BFS desde el origen: explora por niveles, así que la primera vez que llega al destino ya recorrió la mínima cantidad de aristas.

Un min-heap de tamaño k: cada nuevo elemento entra solo si supera la raíz (sacándola primero); la raíz es SIEMPRE el k-ésimo mayor visto hasta ahora.

−10: se apilan 2, 3 y 8; el − popea 8 y 3 → 3−8 = −5; el × popea −5 y 2 → 2 × (−5) = −10.

Greedy cuando la elección local óptima conduce al óptimo global; DP cuando los subproblemas se solapan y una elección temprana puede arruinar el resultado final.

Porque al extraer un nodo de la cola lo marca como definitivo: una arista negativa posterior podría mejorar un camino ya cerrado, y Dijkstra nunca reabre nodos procesados.

Con un deque monótono decreciente de índices: el frente es siempre el máximo de la ventana actual; sacás del frente lo que salió de rango y del fondo todo lo menor que el nuevo elemento.

El 2 y después el 4 (lo encuentra). Con lo=0, hi=5 y mid = (lo+hi) redondeado hacia abajo: mid=2 vale 8 < 16 → lo=3; mid=4 vale 16 → fin.

Porque el invariante de BST ordena por subárboles (izq < nodo < der) pero NO garantiza altura: con inserciones en orden, el árbol degenera en una cadena y cada comparación descarta un solo elemento.

Un stack (LIFO): apilás cada apertura y al cerrar verificás que coincida con el tope; al final el stack debe quedar vacío.

Devolvé el índice de `target` en un array ORDENADO, o `-1` si no está. Sin usar `.indexOf` ni `.includes`: ventana low/high que se achica por mitad. ```ts function buscar(arr, target) { let low = 0; let high = arr.length - 1; while (low <= high) { const mid = Math.floor((low + high) / 2); if (arr[mid] === target) return mid; if (arr[mid] < target) low = mid + 1; else high = mid - 1; } return -1; } ```