English flagEnglish  
CLOSE

Suggested:

🛠️ Settings

Problem Statement

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.

LeetCode

Constraints

1 <= nums.length <= 10^4
0 <= nums[i] <= 10^5
  • 1 ≤ nums.length ≤ 10^4
    • The array nums must have at least 1 element and at most 10,000 elements.
    • Implication:
      • Avoid brute force (O(n^2)) – these could lead to Time Limit Exceeded (TLE) in the worst case.
      • Aim for O(n) or O(n log n) complexity.
  • 0 ≤ nums[i] ≤ 10^5
    • Each element in the array (i.e nums[i]) represents the maximum number of indices you can jump forward from index i.
    • Examples:
      • If nums[0] = 0, you can't move forward from that index.
      • If nums[i] = 3, you can jump to i + 1, i + 2, or i + 3.
    • Since the jump length can be up to 100000, it might seem like we can jump very far, but we're still bound by the size of the array (which is at most 10,000).
    • Even if a value is large, you can't jump beyond the array—you just need to reach the last index, not go past it.

 

Examples

Example 1:

Input: nums = [2, 3, 1, 1, 4]
Output: true

Explanation:
- Start at index 0, jump to index 1 (jump length = 2)
- From index 1, jump to index 4 (jump length = 3)
- You’ve reached the last index
Example 2:

Input: nums = [3, 2, 1, 0, 4]
Output: false

Explanation:
- Start at index 0, can jump to indices 1, 2, or 3
- All of those eventually hit a `0` before reaching index 4
- You cannot reach the last index

Different Approaches

1️⃣ Brute Force Approach (TLE)

Intuition:

The problem is essentially about finding if there is a way to jump from the start (index 0) to the last index in the array by making jumps. Each element in the array represents the maximum number of steps you can take from that index.

The intuition behind the recursive approach is:

  • Start at index 0 and try to jump to all possible positions from that index (based on the value of the current index).
  • After each jump, recursively check if you can reach the last index from the new position.
  • If you find any path to the last index, return true.
  • If none of the jumps can lead to the last index, return false.

Approach:

  1. Recursive Function:
    1. Start from the first index (i = 0).
    2. If you're already at the last index (i == nums.size() - 1), return true because you've reached the goal.
    3. Otherwise, for each position i, try all possible steps from 1 to nums[i] (i.e., all jumps that can be made from the current index).
    4. Recursively check if you can reach the last index from each of these new positions.
    5. If any of the recursive calls returns true, the current call will return true, signifying that a valid path exists. Otherwise, it returns false.
  2. Base Case:
    1. If you reach the last index, return true as you've successfully reached the goal.
  3. Termination Condition:
    1. If you can't make any valid jump that leads to the last index, return false.
  4. Overall Plan:
    1. Start at the first index.
    2. Try every possible jump and recursively check if it leads to the last index.

Code:

class Solution {
public:
    // Recursive function to check if it's possible to reach the last index
    bool recursive(vector<int>& nums, int i) {
        // Base case: if we have reached the last index, return true
        if (i == nums.size() - 1) {
            return true;
        }

        // Try all steps from 1 to nums[i] (the number of steps we can jump from i)
        bool possible = false;
        for (int steps = 1; steps <= nums[i]; steps++) {
            // Check if the new index is within bounds and recursively check the jump
            if (i + steps < nums.size() && recursive(nums, i + steps)) {
                possible = true;
            }
        }

        // Return whether any of the jumps led to the last index
        return possible;
    }

    // Main function to check if it's possible to jump from index 0 to the last index
    bool canJump(vector<int>& nums) {
        return recursive(nums, 0);  // Start the recursive process from index 0
    }
};

Complexity Analysis:

  • Time Complexity:O(2^n)
    • The recursive approach explores all possible jumps from every index, leading to an exponential time complexity. Each index can have multiple recursive calls branching out, making it inefficient for larger input sizes.
    • Worst-case scenario: Every possible jump from each index could lead to a branching path that results in exponential growth.
  • Space Complexity:O(n)
    • The maximum depth of the recursion stack is n (where n is the size of the array), which leads to a space complexity of O(n).

2️⃣ Memoization

Code:

class Solution {
public:
    // Memoization helper function
    bool recursive(vector<int>& nums, int i, vector<int>& memo) {
        // If already computed, return the result
        if (memo[i] != -1) {
            return memo[i] == 1;
        }
        
        // Base case: if we have reached the last index, return true
        if (i == nums.size() - 1) {
            return true;
        }

        // Try all steps from 1 to nums[i] (the number of steps we can jump from i)
        bool possible = false;
        for (int steps = 1; steps <= nums[i]; steps++) {
            // Check if the new index is within bounds and recursively check the jump
            if (i + steps < nums.size() && recursive(nums, i + steps, memo)) {
                possible = true;
                break; // Once we find a valid path, no need to check further
            }
        }

        // Memoize the result for index i
        memo[i] = possible ? 1 : 0;
        return possible;
    }

    // Main function to check if it's possible to jump from index 0 to the last index
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        vector<int> memo(n, -1);  // Memoization array, initialized to -1 (unvisited)

        return recursive(nums, 0, memo);  // Start the recursive process from index 0
    }
};

Complexity Analysis:

  • Time Complexity:O(n^2)
    • In worst-case for each of n positions, we try up to n possible next jumps.
  • Space Complexity:O(n)
    • For the memoization array  and recursion call stack.

3️⃣ Greedy Algorithm (Optimal)

Intuition:

Keep track of the farthest position that can be reached at any point. If at an index where it's impossible to move to the next one because it's too far away, then it's impossible to get to the end, and the process must stop.
Otherwise, continue updating the farthest reachable index while moving forward. If the traversal manages to reach or pass the last index, then reaching the end is possible.

Approach:

  1. Start by setting a pointer to track the farthest point that can be reached from the beginning of the array.
  2. Iterate through each position in the array, checking if the current position exceeds the farthest point reached so far.
  3. If the current position is beyond the reachable point, it indicates that further progress is not possible, and reaching the end is infeasible.
  4. If the current position is within the reachable point, update the pointer to reflect the farthest position that can be reached from the current spot.
  5. If the entire array is traversed without finding an unreachable position, it confirms that the last index is reachable, thus making it possible to reach the end.

Code:

#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    // To determine if last index is reachable
    bool canJump(vector<int>& nums) {
        // Initialize maximum index
        int maxIndex = 0;

        // Iterate through each index of the array
        for (int i = 0; i < nums.size(); i++) {
            /*If the current index 
            is greater than the 
            maximum reachable index
            it means we cannot move 
            forward and should 
            return false*/
            if (i > maxIndex) {
                return false;
            }

           /* Update the maximum index that can be 
           reached by comparing
            the current maxIndex with the sum 
            of the current index and
            the maximum jump from that index*/
            maxIndex = max(maxIndex, i + nums[i]);
        }

       /* If we complete the 
       loop, it means we 
       can reach the 
       last index*/
        return true;
    }
};

int main() {
    vector<int> nums = {4, 3, 7, 1, 2};

    cout << "Array representing maximum jump from each index: ";
    for (int i = 0; i < nums.size(); i++) {
        cout << nums[i] << " ";
    }
    cout << endl;

    Solution solution;
    bool ans = solution.canJump(nums);

    if (ans) {
        cout << "It is possible to reach the last index." << endl;
    } else {
        cout << "It is not possible to reach the last index." << endl;
    }

    return 0;
}

Complexity Analysis:

  • Time Complexity:O(N) where N is the length of the array. We iterate through the input array exactly once and at each element perform constant time operations.
  • Space Complexity:O(1) no extra space used.
Your experience on this site will be improved by allowing cookies Cookie Policy