Simple O(m+n) Solution using a Double-Ended Queue || Beats 99.6% of Python submissions
Intuition\nTo solve the problem, we need to simulate a robot starting from each instruction until that robot leaves the board. With the direct approach of simul
# Intuition\nTo solve the problem, we need to simulate a robot starting from each instruction until that robot leaves the board. With the direct approach of simulating each robot individually, we\'d have to run $$m$$ simulations for up to $$m$$ instructions. That\'s too slow!\nWhat if we could use a data structure to track multiple simulations simultaneously?...\n\nAlso, note that all instructions are in the cardinal directions. If an instruction moves the robot off the board, it will either be in the $$x$$ or $$y$$ direction, but never both in the same move.\n\n# Approach\nThe inline code comments should guide you to understand the full solution. However, some more intution is included here too.\n\nWe will use the Double-Ended Queue: a data structure that is like a stack and a queue put together, with fast $$pop$$s and $$append$$s to both sides. We will use one deque to track all $$x$$ indices at the same time, and one for all $$y$$ indices. Each element in our deques will be a list of all active robots at a specific $$x$$ or $$y$$ coordinate. (E.g. `xDeque[k]` is a list of bots at $$x=k$$.) This way, we can pop from the front & append to the back to move in one direction, and we can pop from the back and append to the front to move in the opposite direction. Any robots on the side of the deque that is popped are finished: we can write down how many instructions they could successfully complete.\n\nOne small complication is that popping a bot out of one deque does not remove them from the other deque. To solve this, we check that the bot is still running before saving the number of instructions we think it ran.\n\n# Complexity\n- Time complexity: $$O(m + n)$$ where $$m$$ is the length of the instructions and $$n$$ is the width of the board.\n  - For a similar size $$m$$ and $$n$$ (or for a small board and long instructions) this solution is very good. ($$O(m + n) \\sim O(m) < O(m^2)$$ when $$n \\sim m$$).\n    - If $$n$$ were much larger than $$m$$ (if the board were much longer than the instructions), this solution would be worse than the naive approach ($$O(m + n) > O(m^2)$$ when $$n >> m$$).\n  - Even though there are loops inside the main for loop, in total, they can only run up to $$2m$$ times... there are $$m$$ bots, and each bot can trigger those loops up to once in the $$x$$ direction and once in the $$y$$ direction.\n  - We also have to loop through the instructions 2 times, which also results in $$2m$$ iterations.\n  - Because we have to initalize the board along each axes, the deques cost $$O(n)$$ to initialize.\n\n- Space complexity: $$O(m + n)$$\n  - Each deque is $$n$$ tiles long, and the sum of all items in their child lists is at most $$m$$, which is one for each bot. In addition, the results are $$m$$ items long as well.\n\n# Code\n```python3 []\nclass Solution:\n    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n        (y0, x0) = startPos\n        m = len(s)\n\n        # These will separately track the x and y coordinates of all running bots.\n        yDeque = collections.deque((list() for _ in range(n)))\n        xDeque = collections.deque((list() for _ in range(n)))\n\n        # result[k] will correspond to how many instructions a bot can execute if it starts from the `k`th instruction.\n        # We will fill the results in as we go, and we use a negative number to indicate that the bot is still running.\n        result = [-1] * m\n\n        # Iterate through all instructions. At each instruction, we add a bot to the board & move all bots according to the instruction.\n        for i in range(m):\n            # Place the `i`th bot at (x0, y0)\n            xDeque[x0].append(i)\n            yDeque[y0].append(i)\n\n            # Move the bots based on `s[i]`\n            match s[i]:\n                case "L":\n                    # When moving left, all bots at x=0 will fail, so we use popleft to get all bots at x=0.\n                    # This will also shift all bots at x>0 by one to the left.\n                    for j in xDeque.popleft():\n                        # Only update bot `j` if it\'s still running. It already failed if a nonnegative result is present.\n                        if result[j] < 0:\n                            # Bot `j` started at `j` and failed on `i`. The difference between i and j is the number of successes.\n                            result[j] = i - j\n                    # `popleft` reduced the deque\'s length by one, so we have to initialize a new slot at the right side of the board.\n                    xDeque.append(list())\n                # Right is just like Left, except we pop from the right side & reinitialize on the left.\n                case "R":\n                    for j in xDeque.pop():\n                        if result[j] < 0:\n                            result[j] = i - j\n                    xDeque.appendleft(list())\n                # Up is just like Left, except we use `yDeque` instead of `xDeque`.\n                case "U":\n                    for j in yDeque.popleft():\n                        if result[j] < 0:\n                            result[j] = i - j\n                    yDeque.append(list())\n                # Down is to Up as Right is to Left.\n                case "D":\n                    for j in yDeque.pop():\n                        if result[j] < 0:\n                            result[j] = i - j\n                    yDeque.appendleft(list())\n\n        # If any bots are still running at the end (result[k] = -1), they need to be accounted for.\n        # If they started at 0, they ran for `m` aka `len(s)` moves.\n        # If they started at i, they ran for `m - i` moves.\n        for i in range(m):\n            if result[i] < 0:\n                result[i] = m - i\n\n        return result\n```
['Python3']