LeetCode #55 Jump Game

Medium

Problem

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Solution — Dynamic Programming

We can check each index and find out if there is any point that can reach this index. However, this approach reaches time limitation of LeetCode.

Complexity

This approach checks 1 + 2 + … + (n-1) elements, where n denotes to length of nums. Therefore, its time complexity is O(n²). And it needs O(n) extra space for dp list.

Solution — Greedy

Instead of check all visited positions, we can start from the last point and find out which point is the leftest point that can reach the last point. Once the leftest point is the start point, it meets the problem’s requirement.

Complexity

It’s clear that we only iterate the list once, so the time complexity is O(n). And it’s trivial that space complexity is O(1).