Jump Game

Jump Game 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.

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
• All coding practice problems

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
• Distant Barcodes — Medium, same pattern
• Divide Intervals Into Minimum Number of Groups — Medium, same pattern
• Employee Free Time — Hard, same pattern