https://leetcode.com/problems/jump-game-vii/ from Google

Thinking process:

For each reachable 0, we want to find other 0s which can be reached from the current position by jumpping minJump to maxJump steps. The worst case for the approach is O(N^2) if it’s all 0 and maxJump - minJump = N. Since O(N) is 10^5, O(N^2) will cause a TLE, so this can’t pass the test.

The main observation here is: if we already know that from our current position, the current + maxJump = x, then starting from the next reachable position, let’s say current + 1, we don’t need to check anything before x because we know that they are reachable.

With the algorithm, we will visit every position at least once, so it’s an O(N) solution and can pass the tests.

Here is the code.

 1class Solution {
 2public:
 3    bool canReach(string s, int minJump, int maxJump) {
 4        int N = s.size();
 5        vector<int> good(N);
 6        good[0] = 1;
 7        int M = 0;
 8        for (int i=0; i<N; i++) {
 9            if (s[i] == '0' and good[i]) {
10                int l = i + minJump;
11                int r = min(N-1, i + maxJump);
12                for (int j=max(l, M); j<=r; j++) {
13                    good[j] = 1;
14                }
15                M = r + 1;
16                if (M >= N) break;
17            }
18        }
19        return good.back() == 1 and s.back() == '0';
20    }
21};