Greedy Algorithms8 sections · 316 units
Open in Course

Problem - Jump Game

Can you reach the end?

Array where nums[i] is the max jump length from index i. Can you reach the last index starting from index 00? Example: [2,3,1,1,4]. From 00, jump to 11 or 22. From 11, jump up to 33 positions.

You can reach index 44.

Example: [3,2,1,0,4]. From 00, jump to 11, 22, or 33.

But all paths lead to index 33 where you are stuck. What is the greedy approach? Constraint: n104n \le 10^4 means O(n)O(n) time using O(1)O(1) space greedy beats O(2n)O(2^n) backtracking.