Jump Game
Jump Game is a medium arrays & hashing problem solved with the greedy pattern.
The best approach, optimal (greedy furthest reach), runs in O(n) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (dp over reachable indices) up.
Problem
You start at index 0 of an integer array nums. The value nums[i] is the longest jump you may make from index i: from there you can move forward by any number of steps from 1 up to nums[i] (a value of 0 means you cannot move from that index).
Return true if you can reach the last index, and false otherwise.
Examples
Example 1
- Input
nums = [1, 3, 0, 0, 1, 0]- Output
true- Why
- Jump 0 -> 1, then 1 -> 4 (a jump of 3), then 4 -> 5.
Example 2
- Input
nums = [2, 1, 0, 4]- Output
false- Why
- Every route ends on index 2, whose value is 0, so index 3 is never reached.
Example 3
- Input
nums = [0]- Output
true- Why
- You already stand on the last index.
Constraints
1 <= nums.length <= 10^40 <= nums[i] <= 10^5
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (DP over reachable indices) | O(n²) | O(n) |
| Optimal (greedy furthest reach) | O(n) | O(1) |
1Brute force (DP over reachable indices)
O(n²)Each index can mark up to n - 1 later indices.O(n)One flag per index.Mark index 0 as reachable. Go left to right; from every reachable index i, mark each index it can land on (i + 1 up to i + nums[i], capped at the end). The answer is whether the last index ever gets marked.
- reach = boolean array of size n; reach[0] = true.
- For each i with reach[i] true: for j from i + 1 to min(n - 1, i + nums[i]), set reach[j] = true.
- Return reach[n - 1].
class Solution {
public boolean canJump(int[] nums) {
int n = nums.length;
boolean[] reach = new boolean[n];
reach[0] = true;
for (int i = 0; i < n; i++) {
if (!reach[i]) {
continue;
}
int end = (int) Math.min(n - 1, (long) i + nums[i]);
for (int j = i + 1; j <= end; j++) {
reach[j] = true;
}
}
return reach[n - 1];
}
}class Solution:
def canJump(self, nums: List[int]) -> bool:
n = len(nums)
reach = [False] * n
reach[0] = True
for i in range(n):
if not reach[i]:
continue
end = min(n - 1, i + nums[i])
for j in range(i + 1, end + 1):
reach[j] = True
return reach[n - 1]class Solution {
public:
bool canJump(vector<int>& nums) {
int n = nums.size();
vector<bool> reach(n, false);
reach[0] = true;
for (int i = 0; i < n; i++) {
if (!reach[i]) {
continue;
}
int end = (int)min((long long)n - 1, (long long)i + nums[i]);
for (int j = i + 1; j <= end; j++) {
reach[j] = true;
}
}
return reach[n - 1];
}
};function canJump(nums) {
const n = nums.length;
const reach = new Array(n).fill(false);
reach[0] = true;
for (let i = 0; i < n; i++) {
if (!reach[i]) {
continue;
}
const end = Math.min(n - 1, i + nums[i]);
for (let j = i + 1; j <= end; j++) {
reach[j] = true;
}
}
return reach[n - 1];
}2Optimal (greedy furthest reach)
O(n)One pass over the array.O(1)Only the furthest reach is stored.Because the reachable indices always form a prefix, one number describes them: far, the furthest index reachable so far. Scan left to right; if you arrive at an index beyond far, you are stuck. Otherwise extend far with i + nums[i].
- far = 0.
- For i from 0 to n - 1: if i > far, return false.
- far = max(far, i + nums[i]); if far >= n - 1, return true.
- Return true after the loop.
class Solution {
public boolean canJump(int[] nums) {
int far = 0;
for (int i = 0; i < nums.length; i++) {
if (i > far) {
return false;
}
far = Math.max(far, i + nums[i]);
if (far >= nums.length - 1) {
return true;
}
}
return true;
}
}class Solution:
def canJump(self, nums: List[int]) -> bool:
far = 0
for i, x in enumerate(nums):
if i > far:
return False
far = max(far, i + x)
if far >= len(nums) - 1:
return True
return Trueclass Solution {
public:
bool canJump(vector<int>& nums) {
int far = 0;
int n = nums.size();
for (int i = 0; i < n; i++) {
if (i > far) {
return false;
}
far = max(far, i + nums[i]);
if (far >= n - 1) {
return true;
}
}
return true;
}
};function canJump(nums) {
let far = 0;
for (let i = 0; i < nums.length; i++) {
if (i > far) {
return false;
}
far = Math.max(far, i + nums[i]);
if (far >= nums.length - 1) {
return true;
}
}
return true;
}Edge cases to test
- A single element, even if it is 0
- A 0 at the very start of a longer array
- A 0 at the last index, which does not matter
- A wall of zeros that some earlier long jump clears
- Jump lengths far larger than the array
Hints
Hint 1
nums[i] is the maximum jump, so from i you can land on any index from i + 1 to i + nums[i].
Hint 2
If index j is reachable, every index before j is reachable too. So the reachable set is always a prefix.
Hint 3
Track only the furthest index you can reach so far. When does the scan get stuck?
FAQ
What is the best time complexity for Jump Game?
Optimal (greedy furthest reach) runs in O(n) time and O(1) extra space. One pass over the array.
Which pattern does Jump Game use?
It is a arrays & hashing problem that uses the greedy pattern. Other problems with the same pattern: Integer to Roman, Jump Game II, Can Place Flowers.
Is there a brute force solution for Jump Game?
Yes. Brute force (DP over reachable indices) takes O(n²) time and O(n) space. Mark index 0 as reachable.
Which edge cases should I test for Jump Game?
A single element, even if it is 0; A 0 at the very start of a longer array; A 0 at the last index, which does not matter; A wall of zeros that some earlier long jump clears; Jump lengths far larger than the array.