Después de resolver el primer ejercicio de la serie, seguí en LeetCode para trabajar la lógica sin pedir una solución lista. El desafío 011 es Container With Most Water.
Recibimos un array de alturas y necesitamos elegir dos líneas que formen el recipiente con el área mayor.
Cómo calcular el área
Si elijo las posiciones left y right, el ancho es la distancia entre ellas. La altura del recipiente está limitada por la menor de las dos líneas.
área = min(altura izquierda, altura derecha) × distanciaPor ejemplo, con estas alturas:
[1, 8, 6, 2, 5, 4, 8, 3, 7]Las líneas en las posiciones 1 y 8 tienen alturas 8 y 7. La menor altura es 7, y la distancia entre ellas es 7. Esa combinación produce un área de 49.
Mi primer intento
Empecé con dos punteros, uno en cada punta del array. Después de calcular el área actual, simulaba dos posibilidades:
- avanzar el puntero de la izquierda;
- retroceder el puntero de la derecha.
Calculaba el área de los dos próximos pares y elegía la mayor. El tramo principal era este:
const paddingLeftArea =
Math.min(heights[leftIndex + 1], heights[rigthIndex]) *
(rigthIndex - leftIndex + 1);
const paddingRightArea =
Math.min(heights[leftIndex], heights[rigthIndex - 1]) *
(rigthIndex - 1 - leftIndex);
if (paddingLeftArea > paddingRightArea && paddingLeftArea > maxArea) {
leftIndex += 1;
} else {
rigthIndex -= 1;
}El problema estaba en la hipótesis. La mejor decisión local no garantiza la mejor área en el resto del array. Intentaba adivinar el camino mirando solo los dos próximos movimientos. También había un error en la fórmula de la distancia de ese borrador: para un par de posiciones, el ancho es right - left.
La observación que destraba el problema
El área depende de dos cosas: ancho y menor altura.
Cuando los punteros están en las posiciones left y right, mover el puntero de la mayor altura no puede aumentar la altura mínima del recipiente. El ancho siempre disminuye, y la altura que limita el área sigue presente.
Por eso, el puntero que debe avanzar es el de la menor altura. Es el único movimiento que puede encontrar una línea más alta y compensar la pérdida de ancho.
Si las alturas son iguales, cualquiera de los dos puede avanzar. En el código, elegí avanzar el de la izquierda cuando heights[leftIndex] <= heights[rigthIndex].
Solución con dos punteros
/**
* @param {number[]} heights
* @return {number}
*/
var maxArea = function (heights) {
let leftIndex = 0;
let rigthIndex = heights.length - 1;
let maxArea = 0;
while (leftIndex < rigthIndex) {
const minH = Math.min(heights[leftIndex], heights[rigthIndex]);
const currentArea = minH * (rigthIndex - leftIndex);
maxArea = Math.max(maxArea, currentArea);
if (heights[leftIndex] <= heights[rigthIndex]) {
leftIndex++;
} else {
rigthIndex--;
}
}
return maxArea;
};En cada ronda, calculo el área del par actual, actualizo la mayor área encontrada y muevo uno de los punteros. El while se aproxima al centro y termina.
El detalle del avance importa. En la versión que yo había escrito, los punteros solo avanzaban cuando el área actual no era mayor que maxArea. Si se encontraba una nueva área máxima, la misma combinación se calculaba de nuevo, sin salir del loop. La corrección fue separar las dos decisiones: registrar el área y, después, mover el puntero de la menor altura.
El resultado de los intentos
El historial de LeetCode quedó así:
- JavaScript: aceptada,
3 msy63.6 MB. - JavaScript: respuesta incorrecta.
- JavaScript: respuesta incorrecta.
- Go: aceptada,
0 msy9.6 MB. - TypeScript: aceptada,
3 msy63.9 MB. - Go: respuesta incorrecta.
Fueron tres intentos con respuesta incorrecta antes de llegar a las soluciones aceptadas en JavaScript, Go y TypeScript. Más que contar envíos, yo quería mirar el error, entender la hipótesis que falló e intentarlo de nuevo sin tercerizar todo el razonamiento.
Complejidad
El algoritmo recorre el array una vez. En cada iteración, uno de los punteros avanza, entonces la complejidad de tiempo es O(n) y la complejidad de espacio es O(1).
El primer intento también usaba dos punteros, pero hacía trabajo extra para comparar posibilidades futuras. La segunda solución usa una propiedad del problema para descartar con seguridad parte de las combinaciones.
Ese fue el ejercicio esta vez: no confundir una elección que parece buena ahora con una decisión que el problema realmente permite justificar.
Serie Desenoxidando la lógica #02 — Container With Most Water. Problema en leetcode.com/problems/container-with-most-water.