O(m)g vs. Brute-Force
Because m is limited to 1000, a brute-force solution (see approach 2) would work.\n\nHowever, the O(n) solution is like OMG - as short as brute-force but very h
Because `m` is limited to 1000, a brute-force solution (see approach 2) would work.\n\nHowever, the O(n) solution is like OMG - as short as brute-force but very hard to comprehend (I am still trying). The C++ runtime for these solutions is 0ms vs. 28ms. \n\n#### Approach 1: O(n)\nHere we use arrays instead of hashmap - for two reasons (besides the obvious performance boost). It simplifies the calculations - so it\'s easier to follow the logic. And also, it helps visualize what\'s going on, step-by-step.\n\nMy first question was whether an O(n) solution is even possible. I think it is possible because the robot can only move one step at a time. Therefore, we can always catch it on the border. If the robot could jump over multiple steps, the best we could do is a linearithmic solution. \n\n**C++**\n```cpp\nvector<int> executeInstructions(int n, vector<int>& st, string s) {\n    int m = s.size(), h = m + n, v = m + n;\n    vector<int> hor((m + n) * 2, m), ver((m + n) * 2, m), res(m);\n    for (int i = m - 1; i >= 0; --i) {\n        hor[h] = ver[v] = i;\n        h += s[i] == \'L\' ? 1 : s[i] == \'R\' ? -1 : 0;\n        v += s[i] == \'U\' ? 1 : s[i] == \'D\' ? -1 : 0;\n        res[i] = min({m, hor[h - st[1] - 1], hor[h - st[1] + n], ver[v - st[0] - 1], ver[v - st[0] + n]}) - i;\n    }\n    return res;\n}    \n```\n\nI am still trying to comprehend why it works, and I drew the illustration below to help debugging the `[0,1] "RRDDLU"` test case. We go backward starting from the "center" cell, and sort of track our limits in `hor` and `ver`. If the robot boundaries (blue arrows) overlap with the limits, it means that the robot will go off the grid at the step recorded in that limit.\n\n![image](https://assets.leetcode.com/users/images/c2dd23fe-e5e7-4f5f-ba82-93a2ca7b11a7_1640562125.7951396.png)\n\n#### Approach 2: Brute-Force\nThe complexity is O(m ^ 2), where `m` is the size of the path.\n\n**C++**\n```cpp\nvector<int> executeInstructions(int n, vector<int>& startPos, string s) {\n    vector<int> res;\n    for (int k = 0, i = 0; k < s.size(); ++k) {\n        int h = startPos[1], v = startPos[0];\n        for (i = k; i < s.size() && min(h, v) >= 0 && max(h, v) < n; ++i) {\n            h += s[i] == \'L\' ? -1 : s[i] == \'R\' ? 1 : 0;\n            v += s[i] == \'U\' ? -1 : s[i] == \'D\' ? 1 : 0;\n        }\n        res.push_back(i - k - 1 + (min(h, v) >= 0 && max(h, v) < n));\n    }\n    return res;\n}\n```
[]