C++ O(N) Time O(1) Space Two Pointers
See my latest update in repo LeetCode\n\n## Solution 1. Two Pointers\n\nMark reacheable position using \'2\'. For each s[i] == \'2\', we traverse i + minJump <=
See my latest update in repo [LeetCode](https://github.com/lzl124631x/LeetCode)\n\n## Solution 1. Two Pointers\n\nMark reacheable position using `\'2\'`. For each `s[i] == \'2\'`, we traverse `i + minJump <= j <= i + maxJump` and turn `s[j]` to `2` if `s[j] == \'0\'`.\n\nPointer `j` can be monotonically increasing so that both pointer `i` and `j` at most traverse the array once.\n\n```cpp\n// OJ: https://leetcode.com/problems/jump-game-vii/\n// Author: github.com/lzl124631x\n// Time: O(N)\n// Space: O(1)\nclass Solution {\npublic:\n    bool canReach(string s, int minJump, int maxJump) {\n        if (s.back() == \'1\') return false;\n        s[0] = \'2\'; // mark s[0] as reacheable\n        int j = 0;\n        for (int i = 0; i < s.size() && s.back() != \'2\'; ++i) {\n            if (s[i] != \'2\') continue; // only extend reacheable points\n            j = max(j, i + minJump); // `j` is at least `i + minJump`\n            while (j < s.size() && j - i <= maxJump) { // try to extend until `j > i + maxJump`\n                if (s[j] == \'0\') s[j] = \'2\'; // mark `s[j]` as reacheable if `s[j] == \'0\'`\n                ++j;\n            }\n        }\n        return s.back() == \'2\';\n    }\n};\n```\n\n## Solution 2. DP + Sliding Window\n\nInspired by [[Java/C++/Python] One Pass DP](https://leetcode.com/problems/jump-game-vii/discuss/1224804/JavaC%2B%2BPython-One-Pass-DP)\n\n`active` is the number of previous positions that we can jump from.\n\nFor each `i`, the `[i - maxJump, i + minJump]` forms a sliding window, and we only update the `active` when reacheable points goes in/out of the window (i.e. only update on the edges). We mark `s[i]` as reacheable if `s[i] == \'0\' && active`.\n\n```cpp\n// OJ: https://leetcode.com/problems/jump-game-vii/\n// Author: github.com/lzl124631x\n// Time: O(N)\n// Space: O(1)\nclass Solution {\npublic:\n    bool canReach(string s, int minJump, int maxJump) {\n        if (s.back() == \'1\') return false;\n        int N = s.size(), active = 0;\n        s[0] = \'2\';\n        for (int i = 1; i < N && s.back() != \'2\'; ++i) {\n            if (i - minJump >= 0 && s[i - minJump] == \'2\') ++active;\n            if (i - maxJump - 1 >= 0 && s[i - maxJump - 1] == \'2\') --active;\n            if (s[i] == \'0\' && active) s[i] = \'2\';\n        }\n        return s.back() == \'2\';\n    }\n};\n```
[]