O(m) solution using prefix sum and hashmap
First, consider a 1D version of the problem, where we can only have L/R motion. So we have a list of cells from 0 to n-1 where we start from cell p.\n\nThe main
First, consider a 1D version of the problem, where we can only have L/R motion. So we have a list of cells from 0 to n-1 where we start from cell p.\n\nThe main observation is that the moment we go out of the grid is when we "reach" cell -1 or cell n. So if we can efficiently find for each starting point the number of moves to reach one of these two cells, we are done.\n\nWe do this by taking the prefix sum of the array. Treat L in the string as -1 and R as +1, and take the prefix sum, call it S. Then if we start at cell p and evaluate the commands from i to j, we will end at position p + S[j] - S[i-1].\n\nThis means that for each i, we want to answer the following question efficiently: Find the smallest j\u2265i (if it exists) such that p + S[j] - S[i-1] is n or -1\n\nWe can do this by scanning from right to left and storing positions in a hashmap. Essentially:\n\n* Loop from i = m-1 to 0\n   * Set hashmap[S[i]] = i\n   * Initialise answer[i] to m-i\n   * for b = n and -1:\n     * If b-p+S[i-1] exists in the hashmap, set answer[i] = min(answer[i], hashmap[b-p+S[i-1]] - i)\n\nModifying this code for dealing with both x and y coordinates is not too difficult. Here is my C++ code that got accepted.\n\n```\nvector<int> executeInstructions(int n, vector<int>& startPos, string s) {\n  int m = s.size(), p1s = startPos[0], p2s = startPos[1];\n  vector<int> p1vec(m + 1), p2vec(m + 1);\n  for (int i = 0, curp1 = 0, curp2 = 0; i < m; ++i) {\n    if (s[i] == \'L\')\n      --curp2;\n    else if (s[i] == \'R\')\n      ++curp2;\n    else if (s[i] == \'U\')\n      --curp1;\n    else\n      ++curp1;\n    p1vec[i + 1] = curp1;\n    p2vec[i + 1] = curp2;\n  }\n\n  unordered_map<int, int> p1seen, p2seen;\n  vector<int> ret(m);\n  for (int i = m - 1; i >= 0; --i) {\n    int& cur = ret[i];\n    cur = m - i;\n\n    p1seen[p1vec[i + 1]] = i;\n    p2seen[p2vec[i + 1]] = i;\n\n    if (p1seen.count(n - p1s + p1vec[i]))\n      cur = min(cur, p1seen[n - p1s + p1vec[i]] - i);\n    if (p1seen.count(-1 - p1s + p1vec[i]))\n      cur = min(cur, p1seen[-1 - p1s + p1vec[i]] - i);\n    if (p2seen.count(n - p2s + p2vec[i]))\n      cur = min(cur, p2seen[n - p2s + p2vec[i]] - i);\n    if (p2seen.count(-1 - p2s + p2vec[i]))\n      cur = min(cur, p2seen[-1 - p2s + p2vec[i]] - i);\n  }\n\n  return ret;\n}\n```
['C', 'Prefix Sum']