Jump Game VII
Jump Game VII is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Sliding Window pattern, in the Variable Size (Condition-Based) subpattern.
Problem statement
You are given a binary string s, with positions numbered from 0 through s.length - 1. Position 0 is the starting position, and the destination is the final position, s.length - 1. A position is open when its character is '0'; a position containing '1' cannot be landed on.
From a position i, you may move forward to a position j only when minJump <= j - i <= maxJump. Every position on which you land must be open. The starting position is already occupied, so it does not require a jump.
Implement canReach and return true if the destination can be reached from position 0; otherwise, return false.
Example 1:
Input: s = "00100100", minJump = 2, maxJump = 3 Output: false Explanation: Position 3 is reachable from position 0, and position 6 is then reachable from position 3. However, the destination at position 7 is four steps from position 3 and one step from position 6, so it cannot be reached with jumps of length 2 through 3.
Example 2:
Input: s = "0101100", minJump = 2, maxJump = 3 Output: false Explanation: Position 2 is reachable from position 0, but the next possible positions contain '1' or lead past the destination. Thus the final position cannot be reached.
Example 3:
Input: s = "0000000", minJump = 3, maxJump = 4 Output: true Explanation: A valid route is position 0 to position 3, followed by position 3 to the destination at position 6.
Constraints:
- 2 <= s.length <= 10^5 - s consists only of the characters '0' and '1' - s[0] == '0' - 1 <= minJump <= maxJump < s.length
Topics and companies
Topics: Array, String, Sliding Window, Dynamic Programming.
How to practise Jump Game VII on Thita.ai
Starter code is provided in 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 s.length. time and O(n) for the reachability array. space.
Open Jump Game VII in the code editor, or read the Jump Game VII editorial for a worked solution with its approach and complexity analysis.
Where Jump Game VII sits in the DSA pattern sheet
- Sliding Window pattern guide
- Variable Size (Condition-Based) subpattern
- The full DSA patterns sheet
- All coding practice problems
Problems related to Jump Game VII
Other problems that use the same Variable Size (Condition-Based) and Sliding Window techniques:
- Contains Duplicate II — Easy, same subpattern
- Continuous Subarrays — Medium, same subpattern
- Find Longest Special Substring That Occurs Thrice I — Medium, same subpattern
- Frequency of the Most Frequent Element — Medium, same subpattern
- Fruit Into Baskets — Medium, same subpattern
- Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit — Medium, same subpattern