HomeLeetcode55. Jump Game - Leetcode Solutions
Leetcode

55. Jump Game – Leetcode Solutions

Declan Clarke

Description:

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.

Examples:

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.

Solution in Python:

Python
from typing import List

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # Initialize the maximum reachable index to 0
        max_reachable = 0
        
        # Loop through each index and its value in the nums array
        for i, jump in enumerate(nums):
            # If the current index is greater than the maximum reachable index, return False
            if i > max_reachable:
                return False
            
            # Update the maximum reachable index if the current index + jump is greater
            max_reachable = max(max_reachable, i + jump)
            
            # If the maximum reachable index is greater than or equal to the last index, return True
            if max_reachable >= len(nums) - 1:
                return True
        
        # If we finish the loop without reaching the last index, return False
        return False

Explanation:

  1. Initialization:
    • max_reachable is initialized to 0. This variable keeps track of the farthest index that can be reached from the starting index.
  2. Loop Through the Array:
    • We use a for loop to iterate through each index i and its corresponding jump length jump in the array nums.
  3. Check If Current Index is Reachable:
    • If the current index i is greater than max_reachable, it means we cannot reach this index, so we return False.
  4. Update Maximum Reachable Index:
    • Update max_reachable to be the maximum of its current value and i + jump. This accounts for the maximum index we can reach from the current index i.
  5. Check If We Can Reach the Last Index:
    • If max_reachable is greater than or equal to len(nums) - 1, it means we can reach the last index, so we return True.
  6. Return False If Loop Completes Without Reaching Last Index:
    • If the loop completes and we haven’t returned True, it means we cannot reach the last index, so we return False.

This approach ensures that we efficiently check if we can reach the last index in a single pass through the array, making it an O(n) time complexity solution.

Solution in Javascript:

JavaScript
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
    // Initialize the maximum reachable index to 0
    let maxReachable = 0;

    // Loop through each index and its value in the nums array
    for (let i = 0; i < nums.length; i++) {
        // If the current index is greater than the maximum reachable index, return false
        if (i > maxReachable) {
            return false;
        }

        // Update the maximum reachable index if the current index + jump is greater
        maxReachable = Math.max(maxReachable, i + nums[i]);

        // If the maximum reachable index is greater than or equal to the last index, return true
        if (maxReachable >= nums.length - 1) {
            return true;
        }
    }

    // If we finish the loop without reaching the last index, return false
    return false;
};

Solution in Java:

Java
class Solution {
    public boolean canJump(int[] nums) {
        // Initialize the maximum reachable index to 0
        int maxReachable = 0;

        // Loop through each index in the nums array
        for (int i = 0; i < nums.length; i++) {
            // If the current index is greater than the maximum reachable index, return false
            if (i > maxReachable) {
                return false;
            }

            // Update the maximum reachable index if the current index + jump is greater
            maxReachable = Math.max(maxReachable, i + nums[i]);

            // If the maximum reachable index is greater than or equal to the last index, return true
            if (maxReachable >= nums.length - 1) {
                return true;
            }
        }

        // If we finish the loop without reaching the last index, return false
        return false;
    }
}

Solution in C#:

C#
public class Solution {
    public bool CanJump(int[] nums) {
        // Initialize the maximum reachable index to 0
        int maxReachable = 0;

        // Loop through each index in the nums array
        for (int i = 0; i < nums.Length; i++) {
            // If the current index is greater than the maximum reachable index, return false
            if (i > maxReachable) {
                return false;
            }

            // Update the maximum reachable index if the current index + jump is greater
            maxReachable = Math.Max(maxReachable, i + nums[i]);

            // If the maximum reachable index is greater than or equal to the last index, return true
            if (maxReachable >= nums.Length - 1) {
                return true;
            }
        }

        // If we finish the loop without reaching the last index, return false
        return false;
    }
}

Related Post

Subscribe
Notify of

0 Comments
Inline Feedbacks
View all comments

Popular

© 2024 Devexplain.com