[LeetCode] 55. Jump Game

https://leetcode.com/

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^4
• 0 <= nums[i] <= 10^5

 

Code :

var canJump = function(nums) {
    // 마지막 인덱스
    const lastIdx = nums.length - 1;
    // 현재까지 도달할 수 있는 최대 인덱스
    let maxIdx = 0;
    // 배열을 순회하며 최대 인덱스를 갱신합니다.
    for (let i = 0; i <= maxIdx; i++) {
        maxIdx = Math.max(maxIdx, i + nums[i]);
        // 최대 인덱스가 마지막 인덱스보다 크거나 같으면 true를 반환합니다.
        if (maxIdx >= lastIdx) {
            return true;
        }
    }
    // 최대 인덱스가 마지막 인덱스보다 작으면 false를 반환합니다.
    return false;
};

 

Solutions Code :

var canJump = function(nums) {
    // 배열 길이가 1 이하인 경우 항상 점프 가능
    if (nums.length <= 1)
        return true;
    // 현재까지의 최대 도달 가능한 인덱스를 저장하는 변수
    let maximum = nums[0];
    // 배열을 순회하면서 각 인덱스에서의 도달 가능한 최대 인덱스를 갱신
    for (let i = 0; i < nums.length; i++) {
        // 만약 현재 위치에서의 점프가 불가능한 경우
        if (maximum <= i && nums[i] === 0)
            return false;
        // 현재 위치에서의 도달 가능한 최대 인덱스 갱신
        if (i + nums[i] > maximum) {
            maximum = i + nums[i];
        }
        // 최대 도달 가능한 인덱스가 배열의 끝에 도달하면 점프 가능
        if (maximum >= nums.length - 1)
            return true;
    }
    // 마지막까지 끝에 도달하지 못하면 점프 불가능
    return false;
};

 

 

출처 : https://leetcode.com/problemset/all/

Problems - LeetCode