Cracked Tile Crossing
Medium1-D Dynamic Programming
Problem
A corridor floor is a string tiles of '0' (solid) and '1' (cracked). You start on tile 0, which is solid. From a solid tile i you may jump to tile j when i + minHop ≤ j ≤ i + maxHop and tile j is solid.
Return true if you can land on the last tile.
Example 1
- Input:
- tiles = "0110100", minHop = 2, maxHop = 3
- Output:
- true
0 → 3 → 6.
Example 2
- Input:
- tiles = "0101110", minHop = 2, maxHop = 3
- Output:
- false
From 0 you reach 2; from 2 the candidates 4 and 5 are cracked.
Constraints
- 1 ≤ tiles.length ≤ 10^5 (with one tile you are already there)
- tiles[0] == '0'
- 1 ≤ minHop ≤ maxHop ≤ 10^5
Hint
Show the first hint
Tile j is reachable iff it is solid and at least one tile in [j - maxHop, j - minHop] is reachable.
Walkthrough
How to approach it
01Clarify before coding
- Can I land on a cracked tile even briefly? No: every landing tile must be '0'.
- Is the last tile possibly cracked? Yes, then the answer is false.
- How large is the hop range? Up to n, so scanning it per tile is quadratic.
02Brute force
DP where each tile scans every tile in its incoming window [j - maxHop, j - minHop].
Cost: O(n · (maxHop - minHop)): up to 10^10 steps.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.