Jump Game II

Jump Game II 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 a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

- 0 <= j <= nums[i] and

- i + j < n

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

Example 1:

Input: nums = [2,3,1,1,4] Output: 2 Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [2,3,0,1,4] Output: 2

Constraints:

- 1 <= nums.length <= 104

- 0 <= nums[i] <= 1000

- It's guaranteed that you can reach nums[n - 1].

Topics and companies

Topics: Array, Dynamic Programming, Greedy.

Reported in interviews at Amazon, Apple, Facebook, Google, Microsoft.

How to practise Jump Game II 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), where n is the length of nums. We iterate through the array once. time and O(1), only a constant amount of extra space is used for variables. space.

Open Jump Game II in the code editor, or read the Jump Game II editorial for a worked solution with its approach and complexity analysis.

Where Jump Game II 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 II

Other problems that use the same Jump Game Reachability/Minimization and Greedy Patterns techniques:

• Jump Game — 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