Skip to content

3189. Minimum Moves to Get a Peaceful Board 👍

  • Time: $O(\texttt{sort})$
  • 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
class Solution {
 public:
  int minMoves(vector<vector<int>>& rooks) {
    const int n = rooks.size();
    int ans = 0;
    vector<vector<int>> sortedByRow(rooks);
    vector<vector<int>> sortedByCol(rooks);

    ranges::sort(sortedByRow, ranges::less{},
                 [](const vector<int>& rook) { return rook[0]; });

    ranges::sort(sortedByCol, ranges::less{},
                 [](const vector<int>& rook) { return rook[1]; });

    for (int i = 0; i < n; ++i) {
      ans += abs(sortedByRow[i][0] - /*targetRow=*/i);
      ans += abs(sortedByCol[i][1] - /*targetCol=*/i);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
  public int minMoves(int[][] rooks) {
    final int n = rooks.length;
    int ans = 0;
    int[][] sortedByRow = rooks.clone();
    int[][] sortedByCol = rooks.clone();

    Arrays.sort(sortedByRow, (a, b) -> Integer.compare(a[0], b[0]));
    Arrays.sort(sortedByCol, (a, b) -> Integer.compare(a[1], b[1]));

    for (int i = 0; i < n; ++i) {
      ans += Math.abs(sortedByRow[i][0] - /*targetRow=*/i);
      ans += Math.abs(sortedByCol[i][1] - /*targetCol=*/i);
    }

    return ans;
  }
}

1
2
3
4
5
6
7
class Solution:
  def minMoves(self, rooks: list[list[int]]) -> int:
    n = len(rooks)
    sortedByRow = sorted(rooks, key=lambda x: x[0])
    sortedByCol = sorted(rooks, key=lambda x: x[1])
    return (sum(abs(i - row) for (i, _), row in zip(sortedByRow, range(n))) +
            sum(abs(j - col) for (_, j), col in zip(sortedByCol, range(n))))