[Simple & Elegant] [O(n) time] [O(maxJump) space] Linear scan using sliding window
Intuition\n Describe your first thoughts on how to solve this problem. \nFor computing if any index i is reachable from index 0 or not, we only need the reachab
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nFor computing if any index i is reachable from index 0 or not, we only need the reachability information of indices in the range (i-maxJump, i-1). This is because if index i is reachable and has a path from index 0, then it has to have a predecessor node / index in the range (i-maxJump, i-1).\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. We linearly scan each index / element of s.\n\n2. For each index i (if s[i] = 0) we check if it\'s reachable from index 0 or not.\n\n3. For this check, we manitain a sliding window that contains all the reachable-from-index-0 indices in the range (i-maxJump, i-1). This window contains all indices in increasing order.\n\n4. So for each i we check if the first element f (smallest and farthest from i) in the window doesn\'t skip i with the smallest possible jump. That is, i >= f + minJump. This is because if i < f + minJump, then no other index j in the window can jump to i (all of them will jump ahead of i).\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n) for linear scanning of s\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(maxJump) for the sliding window\n\n# Code\n```\nclass Solution:\n    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n        \n        window = deque()\n        # to keep the list of past maxJump reachable indices\n        \n        window.append(0)\n        for i in range(1, len(s)):\n            \n            # clear the window beyond maxJump\n            if window and window[0] + maxJump < i:\n                window.popleft()\n\n            # check reachability of i\n            if s[i] == \'0\' and window and window[0] + minJump <= i:\n                window.append(i)\n\n        return window and window[-1] == len(s) - 1\n```
['Dynamic Programming', 'Sliding Window', 'Python3']