Intuitive O(m) Solutions in C++ and Python based on hxu10's algorithm
Intuitive O(m) Solutions in C++ and Python based on hxu10\'s algorithm\n\n This is a refactoring of hxu10\'s O(m) Solution.\n The refactoring makes it more intu
### Intuitive O(m) Solutions in C++ and Python based on hxu10\'s algorithm\n\n* This is a refactoring of [hxu10\'s O(m) Solution](https://leetcode.com/problems/execution-of-all-suffix-instructions-staying-in-a-grid/discuss/1647617/python-O(m)-solution-with-detailed-explanation.).\n* The refactoring makes it more intuitive and easy-to-understand.\n\t* avoided the negation of `upmost` and `leftmost` which is counter-intuitive.\n\t* added the reasoning about why we should look up the pos such `curr_row_pos + up_too_far` in the dictionary.\n\nPlease see the detailed comments in the code. \n\n### C++17\n```\nclass Solution {\npublic:\n    // Linear time solution: scanning backward. fzh-to-review-recite.\n    vector<int>\n    executeInstructions(const int n, const vector<int>& startPos, const string commands) {\n        const int m = commands.size();\n        vector<int> res(m);\n        if (n == 1) {\n            return res;\n        }\n        const int startRow = startPos[0], startCol = startPos[1];\n\n        // row delta means the change in row positions\n        // if the row delta equals `up_too_far`, the robot goes too far upward.\n        const int upTooFar = -startRow - 1;\n        // if the row delta equals `downTooFar`, the robot goes too far downward.\n        const int downTooFar = n - startRow;\n        // if the col delta equals `leftTooFar`, the robot goes too far leftward.\n        const int leftTooFar = -startCol - 1;\n        // if the col delta equals `rightTooFar`, the robot goes too far rightward.\n        const int rightTooFar = n - startCol;\n        // the current row/col positions of the robot in the virtual coordinate system.\n        int currRowPos = 0, currColPos = 0;\n\n        // here `command` is synonymous with `instruction`.\n        // u_map futRowToCmdId maps the future row positions to the command id.\n        // futColToCmdId does the same thing for future col positions.\n        unordered_map<int, int> futRowToCmdId{{0, m}};\n        unordered_map<int, int> futColToCmdId{{0, m}};\n\n        for (int i = m - 1; i >= 0; --i) {\n            // since we\'re running the simulation in reverse order,\n            // the pos would increment whereas in forward order it should decrement.\n            switch (commands[i]) { // the current command\n            case \'L\':\n                ++currColPos;\n                break;\n            case \'R\':\n                --currColPos;\n                break;\n            case \'U\':\n                ++currRowPos;\n                break;\n            case \'D\':\n                --currRowPos;\n                break;\n            }\n            int maxSteps = m - i;\n\n            // let\'s suppose there might be a future row pos `fut_row_pos` that make the robot goes\n            // too far upward, then we\'ll have: the delta in row pos (i.e. fut_row_pos -\n            // curr_row_pos) equals to `up_too_far`:\n            //       fut_row_pos - curr_row_pos == up_too_far\n            // the equation is equivalent to:\n            // ==> fut_row_pos == curr_row_pos + up_too_far.\n            // that means, the fut_row_pos, if exists, should be `curr_row_pos + up_too_far`.\n            // So, if that value do exist in the future row pos dictionary, the robot\n            // will go too far upward at that command id. (we discount the last command because it\'s\n            // not allowed.)\n            if (futRowToCmdId.count(currRowPos + upTooFar)) {\n                maxSteps = min(maxSteps, futRowToCmdId[currRowPos + upTooFar] - i - 1);\n            }\n\n            // let\'s suppose there might be a future row pos `fut_row_pos` that make the robot goes\n            // too far downward, then we\'ll have: the delta in row pos (i.e. fut_row_pos -\n            // curr_row_pos) equals to `down_too_far`:\n            //       fut_row_pos - curr_row_pos == down_too_far\n            // the equation is equivalent to:\n            // ==> fut_row_pos == curr_row_pos + down_too_far.\n            // that means, the fut_row_pos, if exists, should be `curr_row_pos + down_too_far`.\n            // So, if that value do exist in the future row pos dictionary, the robot\n            // will go too far downward at that command id. (we discount the last command because\n            // it\'s not allowed.)\n            if (futRowToCmdId.count(currRowPos + downTooFar)) {\n                maxSteps = min(maxSteps, futRowToCmdId[currRowPos + downTooFar] - i - 1);\n            }\n\n            // for col pos, the reasoning are the same as the row pos\n            if (futColToCmdId.count(currColPos + leftTooFar)) {\n                maxSteps = min(maxSteps, futColToCmdId[currColPos + leftTooFar] - i - 1);\n            }\n            if (futColToCmdId.count(currColPos + rightTooFar)) {\n                maxSteps = min(maxSteps, futColToCmdId[currColPos + rightTooFar] - i - 1);\n            }\n\n            res[i] = maxSteps;\n\n            // If the robot goes too far multiple times in the future, we care\n            // only about the occurrence that is closest to the scanline at `i` that is moving to\n            // the left. so we\'ll overwrite the entry in the future row pos dictionary if the entry\n            // already exists.\n            futRowToCmdId[currRowPos] = i;\n            futColToCmdId[currColPos] = i;\n        }\n        return res;\n    }\n}\n```\n\n### Python3\n```\n# LC 2120. Execution of All Suffix Instructions Staying in a Grid.\nclass Solution(object):\n    def executeInstructions(self, n: int, startPos: List[int], cmds: str) -> List[int]:\n        """\n        compute how many steps/instructions can the robot execute if it starts\n        executing at s[i].\n        :param n: the grid is an n * n grid\n        :param startPos: [row, col] of the starting position\n        :param cmds: string form of the commands/instructions\n        :return: a list of integers indicating the number of steps if the robot starting at i-th instruction.\n        """\n        m = len(cmds)  # instructions\n        direc = {  #\n            \'U\': [-1, 0],\n            \'D\': [1, 0],\n            \'L\': [0, -1],\n            \'R\': [0, 1],\n        }\n        ROW_IDX, COL_IDX = 0, 1\n\n\t\t# row delta means the change in row positions\n        # if the row delta equals `up_too_far`, the robot goes too far upward.\n        up_too_far = -startPos[ROW_IDX] - 1\n        up_too_far_negated = startPos[ROW_IDX] + 1\n        # if the row delta equals `down_too_far`, the robot goes too far downward.\n        down_too_far = n - startPos[ROW_IDX]\n        # if the col delta equals `left_too_far`, the robot goes too far leftward.\n        left_too_far = -startPos[COL_IDX] - 1\n        left_too_far_negated = startPos[COL_IDX] + 1\n        # if the col delta equals `right_too_far`, the robot goes too far rightward.\n        right_too_far = n - startPos[COL_IDX]\n        # the current row/col positions of the robot in the virtual coordinate system.\n        curr_row_pos, curr_col_pos = 0, 0\n        # here `command` is synonymous with `instruction`.\n        # dict fut_row_to_cmd_id maps the future row positions to the command id.\n        # fut_col_to_cmd_id do the same thing for future col positions.\n        fut_row_to_cmd_id, fut_col_to_cmd_id = {0: m}, {0: m}\n        ans = []\n\n        for i in range(m - 1, -1, -1):  # reverse iterating\n            action = cmds[i]\n            # since we\'re going backward, we minus the step deltas\n            curr_row_pos -= direc[action][0]\n            curr_col_pos -= direc[action][1]\n            maxstep = m - i  # this is the ideal situation where the robot never goes too far.\n\n            # let\'s suppose there might be a future row pos `fut_row_pos` that make the robot goes too far upward,\n            # then we\'ll have: the delta in row pos (i.e. fut_row_pos - curr_row_pos) equals to `up_too_far`:\n            #       fut_row_pos - curr_row_pos == up_too_far\n            # the equation is equivalent to:\n            # ==> fut_row_pos == curr_row_pos + up_too_far.\n            # that means, the fut_row_pos, if exists, should be `curr_row_pos + up_too_far`.\n            # So, if that value do exist in the future row pos dictionary, the robot\n            # will go too far upward at that command id. (we discount the last command because it\'s not allowed.)\n            if curr_row_pos + up_too_far in fut_row_to_cmd_id:\n                maxstep = min(maxstep, fut_row_to_cmd_id[curr_row_pos + up_too_far] - i - 1)\n            # let\'s suppose there might be a future row pos `fut_row_pos` that make the robot goes too far downward,\n            # then we\'ll have: the delta in row pos (i.e. fut_row_pos - curr_row_pos) equals to `down_too_far`:\n            #       fut_row_pos - curr_row_pos == down_too_far\n            # the equation is equivalent to:\n            # ==> fut_row_pos == curr_row_pos + down_too_far.\n            # that means, the fut_row_pos, if exists, should be `curr_row_pos + down_too_far`.\n            # So, if that value do exist in the future row pos dictionary, the robot\n            # will go too far downward at that command id. (we discount the last command because it\'s not allowed.)\n            if curr_row_pos + down_too_far in fut_row_to_cmd_id:\n                maxstep = min(maxstep, fut_row_to_cmd_id[curr_row_pos + down_too_far] - i - 1)\n\n            # the reasoning here is the same as for `up_too_far`.\n            if curr_col_pos + left_too_far in fut_col_to_cmd_id:\n                maxstep = min(maxstep, fut_col_to_cmd_id[curr_col_pos + left_too_far] - i - 1)\n            # the reasoning here is the same as for `down_too_far`.\n            if curr_col_pos + right_too_far in fut_col_to_cmd_id:\n                maxstep = min(maxstep, fut_col_to_cmd_id[curr_col_pos + right_too_far] - i - 1)\n\n            ans.append(maxstep)\n\n            # If the robot go too far multiple times in the future, we care\n            # only about the occurrence that is closest to the scanline that is moving to the left.\n            # so we\'ll overwrite the entry in the future row pos dictionary if the entry already exists.\n            fut_row_to_cmd_id[curr_row_pos] = i\n            fut_col_to_cmd_id[curr_col_pos] = i\n\n        return ans[::-1]  # reverse the list\n\n```\n\n
['C', 'Python']