[leetcode #55] Jump Game

Problem

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

Input: nums = [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: nums = [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.

Constraints:

・ 1 <= nums.length <= 10⁴
・ 0 <= nums[i] <= 10⁵

Idea

복잡해보이지만 간단하게 풀 수 있는 문제다. nums array를 탐색하면서 0이 아닐 경우 해당 원소에서 갈 수 있는 최대값을 계산한 뒤, 이전에 갈 수 있는 최대값과 비교한다. 값이 0일 경우, 0인 index가 최대값보다 크거나 같을 경우 더 이상 이동할 수 없으므로 false를 리턴한다. 0이 마지막 index인 경우에는 예외처리를 하여 true를 리턴하면 된다.

알고리즘은 다음과 같다.

1. nums array의 크기가 1인 경우 true를 리턴한다.
2. nums array를 탐색하여 각 원소마다 갈 수 있는 최대값을 계산한다. 이전에 계산한 최대값과 비교하여 더 큰 값을 새로운 최대값으로 설정한다.
3. 원소의 값이 0인 경우, 현재 index와 최대값을 비교한다. 최대값이 index보다 작거나 같을 경우 false를 리턴한다. 단, 현재 index가 마지막 index일 경우 true를 리턴한다.
4. nums array를 전부 탐색했다면 true를 리턴한다.

e.g., max값이 (nums array의 크기-1)보다 크거나 같다면 탐색을 멈추고 true를 곧바로 리턴해도 될 것 같다.

Solution

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int max = 0;

        if (n == 1)
            return true;

        for (int i=0; i < n; i++) {
            int cur = i+nums[i];
            if (nums[i] == 0 && max <= i && i != n-1)
                return false;
            max = Math.max(max, cur);
        }

        return true;
    }
}

Reference

https://leetcode.com/problems/jump-game/