algoadvance

Leetcode 55. Jump Game

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.

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 means you cannot move from there.

Constraints:

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 10^5

Clarifying Questions

1. Can we assume the input array will always have at least one element?
   • Yes, the constraints specify that the length is at least 1.
2. Is there any restriction on the value of the elements in the array?
   • Each element is between 0 and 100,000 inclusive.
3. Should we consider empty arrays?
   • No, given the constraints, the array will have at least one element.

Strategy

The problem can be solved using a greedy approach. The idea is to keep track of the farthest index that can be reached as we iterate through the array. If we find any index where the farthest index is less than the current index, it means we can’t proceed further and hence cannot reach the last index.

Steps:

1. Initialize a variable maxReach to 0, which keeps track of the farthest index we can reach.
2. Traverse the array using a loop.
3. For each index i:
   • If i is greater than maxReach, return false.
   • Update maxReach to be the maximum of maxReach and i + nums[i].
   • If maxReach is greater than or equal to the last index, return true.
4. If the loop completes, return true.

Code

Here is the C++ solution based on the above strategy:

#include <vector>
#include <iostream>

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

int main() {
    std::vector<int> nums1 = {2, 3, 1, 1, 4};
    std::vector<int> nums2 = {3, 2, 1, 0, 4};
    
    std::cout << "Example 1: " << (canJump(nums1) ? "true" : "false") << std::endl;
    std::cout << "Example 2: " << (canJump(nums2) ? "true" : "false") << std::endl;
    
    return 0;
}

Time Complexity

• The time complexity of this solution is O(n), where n is the length of the array. This is because we are iterating through the array once.

Space Complexity

• The space complexity is O(1) since we are using only a constant amount of extra space regardless of the input size.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?