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 makes it impossible to reach the last index.

Clarifying Questions

  1. Can the input array be empty?
    • No, according to the problem, the array will contain at least one element.
  2. What are the constraints on the length of the input array?
    • 1 <= nums.length <= 10^4
  3. What are the constraints on the values within the array?
    • 0 <= nums[i] <= 10^5

Strategy

To solve this problem, we can utilize a greedy approach. We need to keep track of the farthest point that can be reached while iterating through the array. Here’s the plan:

  1. Initialize a variable maxReach to keep track of the maximum index we can reach so far.
  2. Iterate through the array; for each index i:
    • If i is greater than maxReach, it means we can’t reach index i, hence return false.
    • Update maxReach to be the maximum of maxReach and i + nums[i].
    • If at any point maxReach is greater than or equal to the last index of the array, return true.
  3. Return true if the loop completes successfully.

Code

public class JumpGame {
    public boolean canJump(int[] nums) {
        int maxReach = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > maxReach) {
                return false;
            }
            maxReach = Math.max(maxReach, i + nums[i]);
            if (maxReach >= nums.length - 1) {
                return true;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        JumpGame jumpGame = new JumpGame();
        int[] nums1 = {2, 3, 1, 1, 4};
        int[] nums2 = {3, 2, 1, 0, 4};
        System.out.println(jumpGame.canJump(nums1)); // Output: true
        System.out.println(jumpGame.canJump(nums2)); // Output: false
    }
}

Time Complexity

This solution effectively determines whether you can reach the end of the array using a greedy approach, making it efficient and straightforward.

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