Leetcode 55: Jump Game

Input: The input is a list of integers, where each number represents the maximum number of steps you can jump from that index.

Example: ["nums = [2, 3, 1, 1, 4]"]

Constraints:

• 1 <= nums.length <= 10^4

• 0 <= nums[i] <= 10^5

Output: Return a boolean value: true if it's possible to reach the last index, false otherwise.

Example: ["true"]

Constraints:

• The function must determine whether reaching the last index is possible.

Goal: To determine if we can jump from the first index to the last index by considering the maximum jump lengths at each index.

Steps:

• 1. Initialize a variable mx to keep track of the farthest index that can be reached.

• 2. Traverse the array, updating mx with the maximum index reachable from each position.

• 3. If at any index, mx is less than the current index, return false (we can't jump further).

• 4. If mx reaches or exceeds the last index, return true.

Goal: The array's length can be large, so an efficient solution is needed.

Steps:

• 1 <= nums.length <= 10^4

• 0 <= nums[i] <= 10^5

Assumptions:

• You can always start from the first index, and there's no need to account for negative or invalid values in the array.

• Input: ["nums = [2, 3, 1, 1, 4]"]

• Explanation: By jumping from index 0 to index 1, and then from index 1 to the last index, you can reach the end of the array.

• Input: ["nums = [3, 2, 1, 0, 4]"]

• Explanation: You will reach index 3, which has a jump length of 0, preventing further movement, so it's not possible to reach the last index.

Approach: The approach involves iterating through the array while keeping track of the farthest index that can be reached. If at any point the farthest index is behind the current index, return false.

Observations:

• We need to track the farthest position that can be reached as we iterate through the array.

• A greedy approach is well-suited for this problem, where we update the maximum reachable index as we go.

Steps:

• 1. Initialize a variable mx to track the farthest reachable index.

• 2. Loop through the nums array, updating mx with the maximum reachable index.

• 3. If at any index, mx is less than the current index, return false.

• 4. If mx reaches or exceeds the last index, return true.

Empty Inputs:

• The problem guarantees that the array has at least one element.

Large Inputs:

• The solution must efficiently handle arrays with lengths up to 10^4.

Special Values:

• If there are zeros in the array, they may prevent further jumps if encountered early.

Constraints:

• The solution must ensure that the algorithm runs in linear time, i.e., O(n).

bool canJump(vector<int>& nums) {
    int mx = 0;
    int n = nums.size();
    for(int i = 0; i < n; i++) {
        if(mx < i) return false;
        mx = max(mx, i + nums[i]);
        if(mx >= nums.size() - 1) return true;
    }
    return false;
}

1 : Function Declaration

bool canJump(vector<int>& nums) {

This line declares a function named `canJump` that takes a vector of integers `nums` as input and returns a boolean value indicating whether it's possible to reach the last index.

2 : Variable Initialization

    int mx = 0;

This line initializes an integer variable `mx` to 0. This variable will keep track of the farthest reachable index from the current position.

3 : Array Size Calculation

    int n = nums.size();

This line calculates the size of the input array `nums` and stores it in the `n` variable.

4 : Iterate Over Array

    for(int i = 0; i < n; i++) {

This loop iterates over each index `i` of the `nums` array.

5 : Check Reachability

        if(mx < i) return false;

This condition checks if the current index `i` is beyond the farthest reachable index `mx`. If so, it's impossible to reach the end, so the function returns `false`.

6 : Update Maximum Reachable Index

        mx = max(mx, i + nums[i]);

This line updates the `mx` variable to the maximum of its current value and the farthest reachable index from the current position `i + nums[i]`. This effectively calculates the maximum possible jump distance from the current position.

7 : Check for Early Success

        if(mx >= nums.size() - 1) return true;

This condition checks if the current maximum reachable index `mx` is greater than or equal to the last index of the array. If so, it means we can reach the end, so the function returns `true`.

8 : Return False

    return false;

If the loop completes without finding a path to the end, the function returns `false`, indicating that it's not possible to reach the last index.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n), where n is the number of elements in the array, since we only make a single pass over the array.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is O(1) as we only need a constant amount of extra space for tracking the maximum reachable index.

Leetcode 55: Jump Game

Solution to LeetCode 55: Jump Game Problem

Explore →