Problem Description

Given a 2D array rooks of length n, where rooks[i] = [x_i, y_i] indicates the position of a rook on an n x n chess board. Your task is to move the rooks 1 cell at a time vertically or horizontally (to an adjacent cell) such that the board becomes peaceful.

A board is considered peaceful if there is exactly one rook in each row and each column.

Return the minimum number of moves required to achieve a peaceful board.

Note that at no point can there be two rooks in the same cell.

Intuition

The problem can be solved efficiently using a greedy approach. The key insight is that by arranging rooks in increasing order of their coordinates, we can minimize the total distance traveled to reach a peaceful arrangement.

1. Sorting by X-coordinates: First, sort all the rooks based on their x-coordinates. This allows us to iterate over them and align them with their respective row indices (0 through n-1). By computing the sum of the absolute differences between each rook’s x-coordinate and its target x-coordinate (the index), we determine the total moves needed just to position them correctly in rows.

2. Sorting by Y-coordinates: Perform a similar process for y-coordinates. After sorting rooks by the y-coordinate, align them with their column indices, and compute the moves required to achieve this alignment.

The final result is the sum of moves required for both x and y alignments. This ensures a peaceful board with one rook per row and one per column while achieving it in the minimum number of moves.

Learn more about Greedy and Sorting patterns.

Solution Approach

In the given solution, the problem is tackled using a greedy algorithm. The implementation involves the following steps:

1. Sorting by X-coordinates:

   • First, sort the list of rooks based on their x-coordinates.
   • Iterate over each rook and compute the difference between its current x-coordinate and its target x-coordinate (which corresponds to its index in the sorted list).
   • This difference is calculated using the formula abs(x - i), where x is the current x-coordinate of the rook and i is its index in the list.
   • Sum these absolute differences to get the total number of moves required to properly align the rooks in their respective rows.

   rooks.sort()
   ans = sum(abs(x - i) for i, (x, _) in enumerate(rooks))

2. Sorting by Y-coordinates:

   • Sort the list of rooks based on their y-coordinates.
   • Similar to the x-coordinate alignment, calculate the difference between the current y-coordinate and the target y-coordinate for each rook.
   • This is done using abs(y - j) where y is the current y-coordinate and j is its index in the sorted list.
   • Add these differences to the previously calculated total to account for column alignment moves.

   rooks.sort(key=lambda x: x[1])
   ans += sum(abs(y - j) for j, (_, y) in enumerate(rooks))

3. Return the Result: The variable ans now contains the total minimum number of moves required to make the board peaceful.

   return ans

Overall, this approach efficiently ensures that each rook is moved to a position where there is exactly one rook per row and per column, minimizing the move count.

Example Walkthrough

Let's consider a small example to illustrate the solution approach.

Example Input:

• Rooks positions: rooks = [[0, 2], [1, 0], [2, 1]]
• Board size: 3 x 3

In this example, we have rooks at three positions: (0, 2), (1, 0), and (2, 1).

Step 1: Sorting by X-coordinates

Initially, the rooks are sorted by their x-coordinates:

• [0, 2] (Rook at (0, 2))
• [1, 0] (Rook at (1, 0))
• [2, 1] (Rook at (2, 1))

Since they are already in increasing order of their x-coordinates, the target x-coordinates simply match their indices:

• Rook at position (0, 2) aligns with row 0, needing abs(0 - 0) = 0 moves.
• Rook at position (1, 0) aligns with row 1, needing abs(1 - 1) = 0 moves.
• Rook at position (2, 1) aligns with row 2, needing abs(2 - 2) = 0 moves.

Total x-coordinate alignment moves: 0 + 0 + 0 = 0.

Step 2: Sorting by Y-coordinates

Next, sort the rooks by their y-coordinates:

• [1, 0] (Rook at (1, 0))
• [2, 1] (Rook at (2, 1))
• [0, 2] (Rook at (0, 2))

Align them with their column indices:

• Rook moves to (1, 0) for column 0, needing abs(0 - 0) = 0 additional moves.
• Rook moves to (2, 1) for column 1, needing abs(1 - 1) = 0 additional moves.
• Rook moves to (0, 2) for column 2, needing abs(2 - 2) = 0 additional moves.

Total y-coordinate alignment moves: 0 + 0 + 0 = 0.

Step 3: Return the Result

The total minimum number of moves required:

• Total moves = X-alignment moves + Y-alignment moves = 0 + 0 = 0.

Thus, the peaceful arrangement is already achieved with 0 moves.

def min_rook_moves(rooks):
    rooks.sort()
    ans = sum(abs(x - i) for i, (x, _) in enumerate(rooks))

    rooks.sort(key=lambda x: x[1])
    ans += sum(abs(y - j) for j, (_, y) in enumerate(rooks))

    return ans

rooks = [[0, 2], [1, 0], [2, 1]]
print(min_rook_moves(rooks))  # Output: 0

This walkthrough demonstrates how the given solution efficiently finds the minimal number of moves required to achieve a peaceful board configuration.

Solution Implementation

Time and Space Complexity

The time complexity of the code is O(n * log n) due to the sorting operations on the list of rooks based on their x and y coordinates separately. Since sorting a list of length n takes O(n * log n), and we perform sorting twice, the complexity remains O(n * log n).

The space complexity of the code is O(log n) which comes from the space used by the sorting algorithm. This is typical for sorting algorithms like Timsort, used in Python, which operates in place but requires O(log n) space for recursive calls or temporary storage.

Learn more about how to find time and space complexity quickly.