Think of it as BFS. Level is index . Level is all indices reachable in jump. And so on. Track:
- currentEnd: the furthest index reachable with current number of jumps: furthest: the furthest index reachable with one more jump: jumps: number of jumps made When you reach currentEnd, you must jump. Update currentEnd = furthest and increment jumps. Time: . Space: . Without this level-based view, you would try all jump sequences in exponential time.