55. Jump Game
Jump Game (LeetCode 55) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Greedy Patterns pattern, in the Jump Game Reachability/Minimization subpattern.
How to solve Jump Game
Jump Game is a Jump Game problem, part of Greedy Patterns. Solve jump game problems using greedy approach. Check reachability and find minimum jumps.
Work towards the solution in these steps:
- Consider how you can use a greedy approach to track the furthest reachable position as you iterate through the array.
- Think about maintaining a variable that records the maximum index you can reach at each step and updating it as you move forward.
- At each index, check if your current position is within the maximum reachable index; if not, you cannot progress further.
The reference solution runs in O(n) time and O(1) space.
The Jump Game solution and editorial walks through the full approach with reference code.
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.
Constraints:
- 1 <= nums.length <= 104
- 0 <= nums[i] <= 105
Topics and companies
Topics: Array, Dynamic Programming, Greedy.
Reported in interviews at Amazon, Apple, Bloomberg, Facebook, Google, Microsoft.
How to practise Jump Game on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.
Open Jump Game in the code editor, or read the Jump Game editorial for a worked solution with its approach and complexity analysis.
Where Jump Game sits in the DSA pattern sheet
- Greedy Patterns pattern guide
- Jump Game Reachability/Minimization subpattern
- The full DSA patterns sheet
Problems related to Jump Game
Other problems that use the same Jump Game Reachability/Minimization and Greedy Patterns techniques:
- Jump Game II — Medium, same subpattern
- Assign Cookies — Easy, same pattern
- Candy — Hard, same pattern
- Car Pooling — Medium, same pattern
- Distant Barcodes — Medium, same pattern
- Divide Intervals Into Minimum Number of Groups — Medium, same pattern
Jump Game FAQ
What is the LeetCode number of Jump Game?
Jump Game is LeetCode problem 55, rated Medium.
What pattern is used to solve Jump Game?
Jump Game is a Jump Game problem. It belongs to the Greedy Patterns pattern, in the Jump Game Reachability/Minimization subpattern.
What is the time complexity of Jump Game?
The reference solution runs in O(n) time and O(1) space.
Which companies ask Jump Game?
Jump Game has been reported in interviews at Amazon, Apple, Bloomberg, Facebook, Google, Microsoft.