Leetcode 55. Jump Game

Problem Description

The problem requires us to find if it's possible to reach the end of an array starting from the first element. Each element in the array represents the maximum length of the jump we can make at that position. We are required to decide if we can make it to the end of the array by choosing the optimal jumps at each position.

For example, if we are given the array [2,3,1,1,4], the output should be true because we can jump one step from index 0 to 1, and then three steps to the last index.

On the other hand, if we are given the array [3,2,1,0,4], the output should be false. No matter which path we choose, we will always arrive at index 3. Its maximum jump length is 0, which makes it impossible to reach the last index.

Solution Approach

The approach to the problem is to use a greedy strategy. We initialize a variable, reach, to keep track of the furthest index that we can jump to. For each index, i, we update our reach to the maximum of reach and i + nums[i]. If at any point, i becomes greater than reach, we return false because we've landed in a position where we can't jump anymore.

For instance, let's take an array [2,3,1,1,4]. Here are the steps our algorithm would follow:

• Initialize reach to 0 and i to 0.
• Our current reach is 0 which is less than i + nums[i] (2) so we set reach to i + nums[i].
• We increment i, which becomes 1. Our current reach is 2 which is less than i + nums[i] (4) so we set reach to i + nums[i].
• We increment i, which becomes 2. Our current reach is 4 which is greater than i + nums[i] (3) so we skip to the next iteration.
• We keep iterating and updating our reach. When i becomes greater than nums.size(), we break out of our loop.
• Since i == nums.size(), we return true, indicating that we can reach the last index of the array.

If we used the array [3,2,1,0,4] instead, our reach would become 0 at one point (i 3). Since i isn't greater than nums.size(), i becomes greater than reach and we return false.

Solution Code (Python)

1
2python
3class Solution:
4    def canJump(self, nums):
5        i, reach = 0, 0
6        while i < len(nums) and i <= reach:
7            reach = max(reach, i + nums[i])
8            i += 1
9        return i == len(nums)

Solution Code (Java)

1
2java
3public class Solution {
4    public boolean canJump(int[] nums) {
5        int i = 0, reach = 0;
6        while (i < nums.length && i <= reach) {
7            reach = Math.max(reach, i + nums[i]);
8            i++;
9        }
10        return i == nums.length;
11    }
12}

Solution Code (JavaScript)

1
2javascript
3var Solution = function() {
4  this.canJump = function(nums) {
5    let i = 0, reach = 0;
6    while (i < nums.length && i <= reach) {
7        reach = Math.max(reach, i + nums[i]);
8        i++;
9    }
10    return i === nums.length;
11  }
12}

Solution Code (C++)

1
2cpp
3class Solution {
4public:
5    bool canJump(vector<int>& nums) {
6        int i = 0, reach = 0;
7        while (i < nums.size() && i <= reach) {
8            reach = max(reach, i + nums[i]);
9            i++;
10        }
11        return i == nums.size();
12    }
13};

Solution Code (C#)

1
2csharp
3public class Solution {
4    public bool CanJump(int[] nums) {
5        int i = 0, reach = 0;
6        while (i < nums.Length && i <= reach) {
7            reach = Math.Max(reach, i + nums[i]);
8            i++;
9        }
10        return i == nums.Length;
11    }
12}

The max function is used in all the codes to track the furthest jump that we can make. If, at any point, we reach a position from where we can't make a jump forward, we return false.## Time Complexity

The time complexity for this problem is O(n), where n is the length of the input array. Each index of the input array is processed only once, hence the linear time complexity.

The space complexity is O(1) as we are using only a fixed amount of space, regardless of the size of the input array.

Conclusion

We have provided a solution to the problem in Python, Java, JavaScript, C++ and C#. The problem involves understanding greedy algorithms and how to properly set up a loop to iterate through the array. By maintaining a reach variable, we can constantly update the maximum reachable index based on current index plus the jump size at that index. By comparing reach with the array's length, we can determine whether the end of the array can be reached from the first position.

This problem shows the utility of the greedy strategy where making the locally optimal choice at each step will result in the globally optimal result. Moreover, it also practices your skills in dealing with array index operations and edge cases. This kind of problem is quite typical in coding interviews of tech firms, and you may come across similar type of problems during your real interviews.