Skip to content

2120. Execution of All Suffix Instructions Staying in a Grid 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
 public:
  vector<int> executeInstructions(int n, vector<int>& startPos, string s) {
    const int m = s.length();
    const int uMost = startPos[0] + 1;
    const int dMost = n - startPos[0];
    const int lMost = startPos[1] + 1;
    const int rMost = n - startPos[1];
    const unordered_map<char, pair<int, int>> moves{
        {'L', {0, -1}},
        {'R', {0, 1}},
        {'U', {-1, 0}},
        {'D', {1, 0}},
    };

    vector<int> ans(m);
    unordered_map<int, int> reachX{{0, m}};
    unordered_map<int, int> reachY{{0, m}};
    int x = 0;
    int y = 0;

    for (int i = m - 1; i >= 0; --i) {
      const auto& [dx, dy] = moves.at(s[i]);
      x -= dx;
      y -= dy;
      reachX[x] = i;
      reachY[y] = i;
      int out = INT_MAX;
      if (const auto it = reachX.find(x - uMost); it != reachX.cend())
        out = min(out, it->second);
      if (const auto it = reachX.find(x + dMost); it != reachX.cend())
        out = min(out, it->second);
      if (const auto it = reachY.find(y - lMost); it != reachY.cend())
        out = min(out, it->second);
      if (const auto it = reachY.find(y + rMost); it != reachY.cend())
        out = min(out, it->second);
      ans[i] = out == INT_MAX ? m - i : out - i - 1;
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
  public int[] executeInstructions(int n, int[] startPos, String s) {
    final int m = s.length();
    final int uMost = startPos[0] + 1;
    final int dMost = n - startPos[0];
    final int lMost = startPos[1] + 1;
    final int rMost = n - startPos[1];
    Map<Character, Pair<Integer, Integer>> moves = new HashMap<>();
    moves.put('L', new Pair<>(0, -1));
    moves.put('R', new Pair<>(0, 1));
    moves.put('U', new Pair<>(-1, 0));
    moves.put('D', new Pair<>(1, 0));

    int[] ans = new int[m];
    Map<Integer, Integer> reachX = new HashMap<>();
    Map<Integer, Integer> reachY = new HashMap<>();
    reachX.put(0, m);
    reachY.put(0, m);
    int x = 0;
    int y = 0;

    for (int i = m - 1; i >= 0; --i) {
      Pair<Integer, Integer> pair = moves.get(s.charAt(i));
      final int dx = pair.getKey();
      final int dy = pair.getValue();
      x -= dx;
      y -= dy;
      reachX.put(x, i);
      reachY.put(y, i);
      final int out = Math.min(Math.min(reachX.getOrDefault(x - uMost, Integer.MAX_VALUE),
                                        reachX.getOrDefault(x + dMost, Integer.MAX_VALUE)),
                               Math.min(reachY.getOrDefault(y - lMost, Integer.MAX_VALUE),
                                        reachY.getOrDefault(y + rMost, Integer.MAX_VALUE)));
      ans[i] = out == Integer.MAX_VALUE ? m - i : out - i - 1;
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
  def executeInstructions(
      self,
      n: int,
      startPos: list[int],
      s: str,
  ) -> list[int]:
    moves = {'L': (0, -1), 'R': (0, 1), 'U': (-1, 0), 'D': (1, 0)}
    m = len(s)
    uMost = startPos[0] + 1
    dMost = n - startPos[0]
    lMost = startPos[1] + 1
    rMost = n - startPos[1]

    ans = [0] * m
    reach = {(0, None): m, (None, 0): m}
    x = 0
    y = 0

    for i in reversed(range(m)):
      dx, dy = moves[s[i]]
      x -= dx
      y -= dy
      reach[(x, None)] = i
      reach[(None, y)] = i
      out = min(reach.get((x - uMost, None), math.inf),
                reach.get((x + dMost, None), math.inf),
                reach.get((None, y - lMost), math.inf),
                reach.get((None, y + rMost), math.inf))
      ans[i] = m - i if out == math.inf else out - i - 1

    return ans