LeetCode 55 — Jump Game

Segundo problema de Greedy. ¿Puedo llegar desde 0 al final con saltos de longitud variable? Trackear el “máximo alcance” mientras avanzas.

Enunciado

Array nums donde nums[i] es el salto máximo desde i. Empiezas en 0. ¿Puedes llegar al último índice?

---

Solución — Greedy max reach

class Solution:
    def canJump(self, nums):
        max_reach = 0
        for i, n in enumerate(nums):
            if i > max_reach:
                return False                     # no puedo alcanzar i
            max_reach = max(max_reach, i + n)
        return True

Análisis: O(n).

---

Conexiones

• Próximo: 45-jump-game-ii — minimizar número de saltos.

Estado

• Leído
• Implementado desde cero
• Resuelto en LeetCode