python | 100% faster, 5 methods with explanations
Before I get into the specifics of each method there are 3 cases I checked which make solving the puzzle easier. First, if the target itself can\'t be landed on
Before I get into the specifics of each method there are 3 cases I checked which make solving the puzzle easier. First, if the target itself can\'t be landed on then there can\'t be a solution. Second, if minJump and maxJump are the same, then there\'s only 1 possible path through the string, does it work? And finally, if minJump is 1, then we can ignore all repeated 0\'s. In practice though, it\'s been faster for me to remove all leading/trailing 0\'s (except for the source/target). Doing this allows the rest of the code to run faster and with less memory usage in some cases. Since I use this code at the start of all of my solutions, I decided to put it here as its own section to save space later.\n\nEdit: I came up with something better for the case when minJump == 1, where instead of removing 0\'s, we can check if a string of 1\'s with length maxJump exists in the puzzle input, since such a string would be impossible to jump over. I\'ve edited the code here to reflect that change, and included the old version of the code at the end of the post for reference. It might be more efficient to find the length of the longest string of 1\'s in the puzzle input, but I didn\'t feel like the extra complexity in the code was worth it. Technically, checking if a run of maxJump \'1\'s exists in the puzzle will disprove the existance of a path for any puzzle, but it\'s only really worth doing this work when minJump is 1.\n\nTime Complexity: O(1) <= O <= O(n)\nSpace Complexity: O(1) <= O <= O(maxJump)\n\n\'\'\'\n\n    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:\n        #Check for Easy Cases\n        I = len(s) - 1 # there are several places having the last index was convenient, so I compute/store it here\n        if s[I] == \'1\':\n            #It\'s Impossible to Land on the Target\n            return False\n        elif minJump == maxJump:\n            #There\'s Only 1 Possible Path\n            return I%minJump == 0 and all(c == \'0\' for c in s[minJump:I:minJump])\n        elif minJump == 1:\n            #Check if There\'s an Un-Jumpable String of 1\'s\n            return \'1\'*maxJump not in s\n        else:\n\t\t\t#Solve the Puzzle Using the Method of Your Choice\n\t\t\t...\n\'\'\'\n\n## Method 1: Best-First Search (Simplified A*)\nThis is the first method I tried, and while it is fairly fast, it\'s memory usage is pretty poor. I prioritized indices in a min heap based on their linear distance to the target (which is equivalent to the negated index). The only interesting thing I really did here was that  I cast the string to a character array, allowing me to mark nodes as visited in a way that plays nicely in python. I also computed bounds on indecies which can jump directly to the finish, allowing me to end the search a little faster.\n\nTime Complexity: O(nlogn)\nSpace Complexity: O(n)\nBest Performance: 72 ms/19.6 MB : 100%/22%\n\n\'\'\'\n\n\t\t\t...\n\t\t\t\n\t\t\t#Compute the Bounds for Finishing\n            X = I - maxJump\n            Y = I - minJump\n            \n            #Update the Minimum Jump for Convenience\n            minJump -= 1\n            \n            #Do a BFS\n            s = list(s)\n            queue = [0]\n            while queue:\n                #Get the Next Index\n                i = -heappop(queue)\n                \n                #Check if a Solution was Found\n                if i < X:\n                    #Add Child Nodes to the Queue\n                    for j in range(i + maxJump, i + minJump, -1):\n                        #Check if the Index Can be Jumped to\n                        if s[j] == \'0\':\n                            #Add the Index to the Queue\n                            heappush(queue, -j)\n\n                            #Mark the Index as Visited\n                            s[j] = \'2\'\n\t\t\t\telif i <= Y:\n\t\t\t\t\treturn True\n            \n            #No Solution was Found\n            return False\n\'\'\'\n\n## Method 2: Depth-First Search\nThis idea here is basically the same as for my bfs, except that I realized that the heuristic I was using basically just gave me a depth-first search anyway, except that the bfs required more work since heap operations run in O(logn) while stack operations run in O(1). The ordering indices are visited isn\'t identical between this dfs and the bfs in method 1, but it\'s close enough that for this puzzle the faster stack operations outweigh the less optimal index ordering, leading to a small performance gain.\n\nTime Complexity: O(n)\nSpace Complexity: O(n)\nBest Performance: 60 ms/18.9 ms : 100%/31%\n\n\'\'\'\n\n\t\t\t...\n\t\t\t\n\t\t\t#Compute the Bounds for Finishing\n            X = I - maxJump\n            Y = I - minJump\n            \n            #Update the Maximum Jump for Convenience\n            maxJump += 1\n            \n            #Do a DFS\n            s = list(s)\n            stack = [0]\n            while stack:\n                #Get the Next Index\n                i = stack.pop()\n                \n                #Check if a Solution was Found\n                if i < X:\n                    #Add Child Nodes to the Stack\n                    for j in range(i + minJump, i + maxJump):\n                        #Check if the Index Can be Jumped to\n                        if s[j] == \'0\':\n                            #Add the Index to the Stack\n                            stack.append(j)\n\n                            #Mark the Index as Visited\n                            s[j] = \'2\'\n\t\t\t\telif i <= Y:\n\t\t\t\t\treturn True\n\t\t\t\n            #No Solution was Found\n            return False\n\'\'\'\n\n## Method 2.5 : DFS with Backtracking\nThis is a much more recent addition to this post, and it was inspired by https://leetcode.com/problems/jump-game-vii/discuss/1400399/python-dfs-%2B-backtracking-44ms-15mb\n\nDoing the DFS with backtracking helps keep the stack smaller, and avoids some unnecessary computation when the path is nice! It still explores nodes in the same order as the DFS in method 2 though, making it a very efficient solution! I\'ve also posted a recursive version of this in the comments which I find a little easier to follow, but performs worse due to the recursive overhead.\n\nTime Complexity: O(n)\nSpace Complexity: O(n)\nBest Performance: 40 ms/15.2 ms : 100%/98%\n\n\'\'\'\n\n            ...\n\t\t\t\n\t\t\t#Compute the Bounds for Stopping \n            X = I - maxJump\n            Y = I - minJump\n            \n            #Update the Min Jump for Convenience\n            minJump -= 1\n            \n            #Do a DFS With Backtracking\n            s = list(s[:Y + 1])\n            stack = [(maxJump, minJump)]\n            while stack:\n                #Get the Next Range Off the Stack\n                i, j = stack.pop()\n                \n                #Find the Next Largest Jump\n                for i in range(min(i, Y), j, -1):\n                    #Check if the Square Can be Jumped to\n                    if s[i] == \'0\':\n                        #Mark the Square as Visited/Reachable\n                        s[i] = \'2\'\n\n                        #Check the Case (if neither condition is true then the finish isn\'t reachable from the current position)\n                        if i < X:\n                            #Add the Current Range Back to the Stack (for backtracking)\n\t\t\t\t\t\t\tstack.append((i, j))\n\t\t\t\t\t\t\t\n                            #Add the Next Range to the Stack\n                            stack.append((i + maxJump, i + minJump))\n                            \n                            #Move on to the Next Range on the Stack\n                            break\n                        else:\n                            #A Solution was Found\n                            return True\n            \n            #No Solution is Possible\n            return False\n\'\'\'\n\n## Method 3: 2 Pointer\nIn this method I also cast the string to a character array so that I could mark which nodes were reachable. The basic idea is that we want to know if the position at the right pointer (\'i\') is reachable. The right pointer will be reachable if it\'s open (s[i] == \'0\') and if there\'s a different reachable index in the appropriate range. So, assuming it\'s open, we increment a left pointer searching for indices we could jump to position i from (these indices were previously marked as reachable when the right pointer landed on them). Also, if the left pointer ever catches up to the right pointer then we return False since there was a chain of unreachable points too long for any future points to be reached. (I think the memory usage for this method is still O(n) becasue I casted the string to a character array, but it\'s a much smaller O(n) than either my bfs or dfs).\n\nTime Complexity: O(n)\nSpace Complexity: O(n)\nBest Performance: 108 ms/15.6 MB : 100%/95%\n\n\'\'\'\n\t\t\t\n\t\t\t...\n\t\t\t\n\t\t\t#Cast the String to a Character Array\n            s = list(s)\n            s[0] = \'2\'\n            \n            #2 Pointer Solution\n            j = 0\n            for i in range(minJump, len(s)):\n                #Check if the Right Pointer is Open\n                if s[i] == \'0\':\n                    #Increment the Left Pointer\n                    k = i - maxJump\n                    while j < i and (s[j] != \'2\' or j < k):\n                        j += 1\n                    \n                    #Check if the Right Index is Reachable from the Left Index\n                    if s[j] == \'2\' and j + minJump <= i:\n\t\t\t\t\t\t#Mark the Right Index as Reachable\n                        s[i] = \'2\'\n\t\t\t\t\telif i == j:\n\t\t\t\t\t\t#No Solution is Possible\n\t\t\t\t\t\treturn False\n            \n            #Check if the Final Square is Reachable\n            return s[I] == \'2\'\n\'\'\'\n## Method 4: Monotonic Deque\nFor this method I took the 2 pointer method, and replaced the left pointer with a monotonically increasing queue of reachable indices. Essentially, every time an index is found to be reachable it gets added to the end of the queue, and then the front of the queue gets removed as necessary. Compared to the 2 pointer solution, this solution has far fewer unnecessary comparisons at the expense of a little extra memory. Also, it doesn\'t require replacing the string with a character array.\n\nTime Complexity: O(n)\nSpace Complexity: O(maxJump - minJump)\nBest Performance: 72 ms/18.2 MB : 100%/55%\n\n\'\'\'\n\n\t\t\t...\n\t\t\t\n\t\t\t#Monotonic Queue Solution\n            queue = deque([0])\n            for i in range(minJump, len(s)):\n                #Check if the Right Pointer is Open\n                if s[i] == \'0\':\n                    #Work Through Possible Values for the Left Index\n                    k = i - maxJump\n                    while queue and queue[0] < k:\n                        queue.popleft()\n                    \n                    #Check if the Right Index is Reachable\n                    if not queue:\n                        return False\n                    elif queue[0] + minJump <= i:\n                        #Add Index i to the Queue Since it\'s Reachable\n                        queue.append(i)\n            \n            #Check if the Final Square is Reachable\n            return queue[-1] == I\n\'\'\'\n\n## Method 5: Greedy (Cheating)\nOk, so I can\'t really take credit for this since I got the idea by looking at the sample code for the fastest submission on record when I first solved the puzzle (it solved the puzzle in 116 ms). That being said, I think my code is cleaner, and I did end up beating their time by quite a bit, so I thought I\'d include it here. The basic idea of this method is to start at the end and always take the largest jump backwards possible. Unfortunately, it\'s very easy to craft test cases which beat this algorithm, so it isn\'t actually a solution. There are only 2 cases in LeetCode\'s test set which beat this algorithm though, so they\'re easy to hard-code solutions for.\n\nTime Complexity: O(n)\nMemory Complexity: O(1)\nBest Performance: 40 ms/15 MB : 100%/99%\n\n\'\'\'\n\t\t\t\n\t\t\t...\n\t\t\t\n\t\t\t#Check for Cases Which Break the Algorithm\n\t\t\tif s == "0100100010" and minJump == 3 and maxJump == 4:\n\t\t\t\t#Broken Case #1\n\t\t\t\treturn True\n\t\t\telif s == \'0111000110\' and minJump == 2 and maxJump == 4:\n\t\t\t\t#Broken Case #2\n\t\t\t\treturn True\n\t\t\t\n\t\t\t#Update the Minimum Jump for Convenience\n            minJump -= 1\n            \n            #Work Backwards (Always Taking the Largest Possible Step)\n            while I > maxJump:\n                #Try Jumping Backwards\n                for i in range(I - maxJump, I - minJump):\n                    #Try to Perform the Jump\n                    if i > minJump and s[i] == \'0\':\n                        #Decrement I\n                        I = i\n                        \n                        #Move On\n                        break\n                \n                #Check if a Jump was Performed\n                if i != I:\n                    break\n            \n            #Check if a Solution was Found\n            return minJump < I <= maxJump\n\'\'\'\n\n## Notes:\nI say that the bfs is a simplified A* algorithm because paths in this problem don\'t have a cost per say. This means that my priority queue was sorting the paths using only the heuristic function: distance to the target. Because of this, the bfs prioritized searching deeper before searching broader, which is why my dfs searched indices in a similar order to my bfs. Because the dfs only performs as well as it did due to this quirk, it is less adaptable to other similar problems than the bfs. Also, it\'s entirely possible that a different heuristic function could improve the bfs, whereas the dfs is essentially at it\'s optimal performance (unless there\'s simple pruning I\'ve missed).\n\nAlthough the monotonic deque method is only really suitable for 1D graphs with limited motion (i.e. you can only jumpt so far from your current position), it could be modified to include a cost/reward for the path taken relatively easilly, and would likely perform better than a bfs on such a problem since it should be able to run in linear time without too much trouble (I think a bfs could also do such a problem in linear time, but it\'d be trickier, and I don\'t think it\'d be as effective).\n\nSince LeetCode updated the submissions for this puzzle to include mine, only the greedy/cheating solution still achieves 100% faster. \n\n## Old Header Code:\n\nTime Complexity: O(1) <= O <= O(n)\nSpace Complexity: O(1) <= O <= O(n)\n\n\'\'\'\n\n\t\t#Check for Easy Cases\n        I = len(s) - 1 # there are several places having the last index was convenient, so I compute/store it here\n        if s[I] == \'1\':\n            #It\'s Impossible to Land on the Target\n            return False\n        elif minJump == maxJump:\n            #There\'s Only 1 Possible Path\n            return I%minJump == 0 and all(c == \'0\' for c in s[minJump:I:minJump])\n        else:\n            #Check if the Minimum Jump is 1\n            if minJump == 1:\n                #Remove All Leading/Trailing 0\'s\n                s = s.strip(\'0\')\n                \n                #Check if a Solution Was Found\n                I = len(s) + 1\n                if s and I >= maxJump:\n                    #Add 1 \'0\' Back On Each End\n                    s = \'0\' + s + \'0\'\n                else:\n                    #You Can Reach the End\n                    return True\n\t\t\t\n\t\t\t#Solve the Puzzle Using the Method of Your Choice\n\t\t\t...\n\'\'\'
['Two Pointers', 'Greedy', 'Depth-First Search', 'Breadth-First Search', 'Heap (Priority Queue)', 'Monotonic Queue', 'Python', 'Python3']