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 andi
to 0. - Our current reach is 0 which is less than
i + nums[i]
(2) so we setreach
toi + nums[i]
. - We increment
i
, which becomes 1. Our current reach is 2 which is less thani + nums[i]
(4) so we setreach
toi + nums[i]
. - We increment
i
, which becomes 2. Our current reach is 4 which is greater thani + nums[i]
(3) so we skip to the next iteration. - We keep iterating and updating our reach. When
i
becomes greater thannums.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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.