Python 3: FT 97%, TC O(N), SC O(minJump/(maxJump-minJump+2)): Record Reachable Intervals
Intuition\n\nThere are a couple solutions to this problem, but avoid TLE is the tough part. Basic DFS or BFS will fail.\n\nThe reason it fails is because BFS fo
# Intuition\n\nThere are a couple solutions to this problem, but avoid TLE is the tough part. Basic DFS or BFS will fail.\n\nThe reason it fails is because BFS for example would have a lot of indices, `O(N)` of them, and we\'d check `O(maxJump-minJump)` target destinations for each. That\'s a lot of combinations.\n\nBut we can do something similar to BFS. Instead of recording individual indices, we can do this:\n* from index `0` we can reach `minJump..maxJump`\n* advance `i` to the next reachable index, if any, we haven\'t explored\n* from `i` we can reach `i+minJump..i+maxJump`\n  * this interval may overlap `minJump..maxJump`. If so, union them\n    * we explored earlier `i` so this new interval definitely starts later. Thus the union simplifies to taking maxJump as the new end point\n  * if they don\'t overlap, this is a new interval\n\nWe process `i` in order so there\'s no way we\'d have to insert an interval. It\'s either\n* get a new interval\n* merge with an existing one\n\nThe check if we can merge or not is `O(1)` if we have a deque or stack of intervals.\n\nMemory use is a bit lower overall if we use a `deque` because we can pop intervals we\'ve already explored. It also makes the code a bit cleaner: if the `deque `is empty then we\'re out of options and return `False`.\n\n# Complexity\n- Time complexity: `O(N)`. For each next index, of which there are `O(N)`, it takes `O(1)` operations to get the reachable interval and union or append to the existing `deque`.\n\n- Space complexity: `O(N / (maxJump-minJump+1))` at the very worst, but I suspect the space complexity is actually even better\n  - the most nonoverlapping intervals we can possibly have is produced by taking `R =maxJump-minJump+1` range windows, then placing them side-to-side with one index between them. Hence `N/(R+1)` as the complexity\n  - but I think it\'s better. Suppose we can reach `l..r` as the current interval. Then later intervals we add must start after `r` (otherwise they overlap and space doesn\'t increase). So we have to be about `minJump` before `r`. And then the output intervals can\'t overlap either, meaning only every `R+1`th index can produce a new interval - if it were more frequent, we\'d union intervals. So at most we make new intervals from every `R+1`th index in the last `minJump` indices of the current range. That\'s `minJump/(R+1) = minJump(maxJump-minJump+2)`\n  - The worst case is minJump is `O(N)` and `maxJump = minJump` such that the space usage is `O(N/2)`\n\nOur two alternatives for space complexity are\n* `O(N/(R+1))`\n* `O(minJump / (R+1))`\n* the lesser of these is the latter, hence `O(minJump/(maxJump-minJump+2))`\n\n# Code\n```\nclass Solution:\n    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n        # start at index 0, \'0\'\n        #     can move from i to j iff\n        #        > j is [minJump, maxJump] later than i and in bounds\n        #        > s[j] is zero\n\n        # naive: can do O(N*(max-min)) DP\n        #    for index i, we can get there iff s[i] == \'0\' and there\'s a s[i-minJump..i-maxJump] we can reach\n\n        # but that\'s too expensive\n\n        # other idea: record interval(s) of indices we can reach\n\n        # for 0 we can reach minJump..maxJump\n        #   then for each index in minJump..maxJump we can find intervals we can reach\n        #   repeatedly merge intervals as we go\n        # Pro: probably cheaper. Con: not provably cheaper, and complicated interval merge stuff is complicated.\n\n        # segment tree:\n        #     we can quickly get the sum over i-maxJump .. i-minJump in O(log(N)) time\n        #     or we can use a Fenwick tree, track the number of indices in that range we can reach\n        # this is O(N log(N)) which is better than O(N*jumpRange) ~ O(N**2) at worst\n\n\n        # intervals: more promising than I thought\n        #     suppose we have intervals [[0, 0]] to start\n        #      for each item in current interval: if a valid destination, find interval\n        #    that interval starts after the last interval thus far\n        #    if it intersects at all, then union it: max of last\n        #    otherwise it starts a new interval\n        if s[-1] == \'1\': return False # can\'t jump to a \'1\'\n\n        N = len(s)\n\n        ivals = deque()\n        ivals.append([0, 0])\n        i = 0\n        while ivals:\n            if not ivals:\n                return False\n            elif i > ivals[0][1]:\n                ivals.popleft() # done with this interval\n            else:\n                i = max(i, ivals[0][0]) # ffw to next i we can jump to\n\n                if s[i] == \'0\':\n                    l = i+minJump\n                    r = i+maxJump\n\n                    if l > N-1: return False\n                    if r >= N-1: return True\n\n                    if l < ivals[-1][1]:\n                        # union intervals\n                        ivals[-1][1] = r\n                    else:\n                        # new interval\n                        ivals.append([l, r])\n\n                i += 1 # explore next index\n\n        return False\n```
['Python3']