Problem Description

You are given a 2D array rooks of length n, where rooks[i] = [xi, yi] represents the position of a rook on an n x n chess board. Your goal is to create a peaceful board configuration.

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

You can move rooks one cell at a time either vertically or horizontally (to an adjacent cell). The task is to find the minimum number of moves required to achieve a peaceful board configuration.

An important constraint is that at no point during the moves can two rooks occupy the same cell.

For example, if you have a 3x3 board with 3 rooks, you need to rearrange them so that each of the 3 rows contains exactly one rook, and each of the 3 columns contains exactly one rook. The answer would be the total number of single-cell moves needed to achieve this arrangement.

The solution approach uses a greedy strategy: it independently optimizes the row positions and column positions. First, it sorts the rooks by their x-coordinates and assigns them to rows 0, 1, 2, ..., n-1 in order, calculating the distance each rook needs to move. Then it does the same for columns by sorting by y-coordinates. The sum of these distances gives the minimum total moves needed.

Intuition

The key insight is that we can treat the row and column assignments as two independent problems. Why? Because each rook needs to end up in a unique row AND a unique column, and the movements in the x-direction (changing rows) don't interfere with movements in the y-direction (changing columns).

Think of it this way: if we have n rooks on an n x n board, and we want exactly one rook per row and one per column, we're essentially trying to create a permutation - assigning each rook to a unique row number (0 through n-1) and a unique column number (0 through n-1).

The clever observation is that the order matters. If we sort the rooks by their x-coordinates first, the optimal assignment is to give the leftmost rook to row 0, the second leftmost to row 1, and so on. Why? Because any other assignment would create unnecessary "crossings" where rooks would have to move past each other, increasing the total distance.

For example, if we have rooks at rows [2, 0, 3] and we want them at rows [0, 1, 2], the sorted order tells us:

• The rook at row 0 should go to row 0 (distance = 0)
• The rook at row 2 should go to row 1 (distance = 1)
• The rook at row 3 should go to row 2 (distance = 1) Total distance = 2

Any other assignment would result in a larger total distance. The same logic applies independently to the column assignments.

Since horizontal and vertical movements are independent, we can calculate the minimum moves for rows and columns separately, then add them together for the total minimum moves. This greedy approach guarantees the optimal solution because it minimizes the sum of distances in each dimension independently.

Learn more about Greedy and Sorting patterns.

Solution Approach

The implementation follows a greedy algorithm that handles row and column assignments independently:

Step 1: Handle Row Assignments

• First, we sort the rooks array by x-coordinates: rooks.sort()
• This sorting ensures that the rook with the smallest x-coordinate gets assigned to row 0, the next smallest to row 1, and so on
• We calculate the distance each rook needs to move: sum(abs(x - i) for i, (x, _) in enumerate(rooks))
  • Here, i represents the target row (0, 1, 2, ..., n-1)
  • x is the current row position of the rook
  • abs(x - i) gives the distance the rook needs to move to reach its target row

Step 2: Handle Column Assignments

• Next, we sort the same rooks array by y-coordinates: rooks.sort(key=lambda x: x[1])
• Using the same logic, the rook with the smallest y-coordinate gets assigned to column 0, the next to column 1, and so on
• We calculate the column movement distance: sum(abs(y - j) for j, (_, y) in enumerate(rooks))
  • j represents the target column (0, 1, 2, ..., n-1)
  • y is the current column position of the rook
  • abs(y - j) gives the distance needed to reach the target column

Step 3: Combine Results

• The total minimum moves is the sum of row movements and column movements
• Return ans which contains the total distance

Why This Works: The algorithm works because:

1. Sorting ensures optimal assignment without "crossings" - if rook A is to the left of rook B, assigning A to a row number smaller than B's minimizes total movement
2. Row and column movements are independent - moving a rook horizontally doesn't affect its vertical position and vice versa
3. The greedy choice (assigning sorted positions to sequential indices) is globally optimal for this problem

Time Complexity: O(n log n) due to sorting Space Complexity: O(1) if we don't count the input array modification

Example Walkthrough

Let's walk through a concrete example with a 3×3 board and 3 rooks positioned at: [[0,1], [2,2], [1,0]]

Initial Board State:

  0 1 2
0 . R .
1 R . .
2 . . R

Step 1: Handle Row Assignments

First, sort rooks by x-coordinate (row position):

• Original: [[0,1], [2,2], [1,0]]
• After sorting: [[0,1], [1,0], [2,2]]

Now assign sorted rooks to target rows 0, 1, 2:

• Rook at row 0 → target row 0: distance = |0-0| = 0
• Rook at row 1 → target row 1: distance = |1-1| = 0
• Rook at row 2 → target row 2: distance = |2-2| = 0

Total row movements = 0

Step 2: Handle Column Assignments

Sort the same rooks by y-coordinate (column position):

• Before: [[0,1], [1,0], [2,2]]
• After sorting by y: [[1,0], [0,1], [2,2]]

Now assign sorted rooks to target columns 0, 1, 2:

• Rook at column 0 → target column 0: distance = |0-0| = 0
• Rook at column 1 → target column 1: distance = |1-1| = 0
• Rook at column 2 → target column 2: distance = |2-2| = 0

Total column movements = 0

Step 3: Calculate Total Total minimum moves = row movements + column movements = 0 + 0 = 0

The board is already peaceful! Each row and column has exactly one rook.

Let's try a more interesting example: [[1,1], [2,0], [0,2]]

Initial Board State:

  0 1 2
0 . . R
1 . R .
2 R . .

Step 1: Row Assignments

Sort by x-coordinate: [[0,2], [1,1], [2,0]]

Assign to rows 0, 1, 2:

• Rook at row 0 → row 0: distance = |0-0| = 0
• Rook at row 1 → row 1: distance = |1-1| = 0
• Rook at row 2 → row 2: distance = |2-2| = 0

Row movements = 0

Step 2: Column Assignments

Sort by y-coordinate: [[2,0], [1,1], [0,2]]

Assign to columns 0, 1, 2:

• Rook at column 0 → column 0: distance = |0-0| = 0
• Rook at column 1 → column 1: distance = |1-1| = 0
• Rook at column 2 → column 2: distance = |2-2| = 0

Column movements = 0

Total = 0 (This board is also already peaceful!)

Example with actual movements needed: [[0,0], [0,1], [0,2]]

Initial Board State:

  0 1 2
0 R R R
1 . . .
2 . . .

Step 1: Row Assignments

Already sorted by x: [[0,0], [0,1], [0,2]]

Assign to rows 0, 1, 2:

• Rook at row 0 → row 0: distance = |0-0| = 0
• Rook at row 0 → row 1: distance = |0-1| = 1
• Rook at row 0 → row 2: distance = |0-2| = 2

Row movements = 0 + 1 + 2 = 3

Step 2: Column Assignments

Sort by y: [[0,0], [0,1], [0,2]] (already sorted)

Assign to columns 0, 1, 2:

• Rook at column 0 → column 0: distance = |0-0| = 0
• Rook at column 1 → column 1: distance = |1-1| = 0
• Rook at column 2 → column 2: distance = |2-2| = 0

Column movements = 0

Total minimum moves = 3 + 0 = 3

The final peaceful configuration would have one rook in each row and column, achieved by moving two rooks down a total of 3 cells.

Solution Implementation

Time and Space Complexity

The time complexity is O(n × log n), where n is the number of rooks. This is because:

• The first sort() operation takes O(n × log n) time
• The first list comprehension iterates through n elements, taking O(n) time
• The second sort() operation with a key function takes O(n × log n) time
• The second list comprehension iterates through n elements, taking O(n) time
• Overall: O(n × log n) + O(n) + O(n × log n) + O(n) = O(n × log n)

The space complexity is O(log n). This is because:

• The sorting algorithm (typically Timsort in Python) uses O(log n) space for its recursion stack
• The list comprehensions create generator expressions that are consumed immediately by sum(), not creating additional lists
• No additional data structures proportional to input size are created
• Overall: O(log n) space for the sorting operations

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

Common Pitfalls

Pitfall 1: Misunderstanding the Independence of Row and Column Movements

The Mistake: A common misconception is thinking that moving a rook diagonally (changing both row and column simultaneously) counts as a single move, or that we need to track the actual path each rook takes to avoid collisions.

Why It Happens: The problem states rooks can only move horizontally or vertically one cell at a time, which might lead to overthinking about optimal paths or trying to minimize diagonal distances.

The Reality:

• Row and column movements are completely independent
• A rook moving from position (2, 3) to (0, 1) requires |2-0| + |3-1| = 4 moves total
• The actual path taken doesn't matter for counting moves

Solution: Trust the greedy approach - calculate row distances and column distances separately and sum them. The minimum number of moves is always the Manhattan distance.

Pitfall 2: Attempting to Track Collision Avoidance

The Mistake: Trying to implement logic to ensure rooks don't collide during movement, such as maintaining a board state or planning specific movement sequences.

Why It Happens: The problem mentions "at no point during the moves can two rooks occupy the same cell," which seems like a constraint we need to actively handle.

The Reality:

• With n rooks on an n×n board moving to a peaceful configuration, collisions can always be avoided
• The constraint doesn't affect the minimum number of moves needed
• We can always find a valid sequence of moves that achieves the minimum

Solution: Focus only on calculating the total distance. The actual movement sequence that avoids collisions exists but doesn't need to be explicitly constructed.

Pitfall 3: Incorrect Sorting or Assignment Logic

The Mistake: Using complex assignment strategies like Hungarian algorithm or trying to minimize the maximum distance any single rook travels.

Why It Happens: The problem seems like a complex assignment problem that might require sophisticated matching algorithms.

The Reality:

• The greedy approach of sorting and assigning to consecutive indices is optimal
• Any other assignment would create "crossings" that increase total distance

Solution: Stick to the simple sorting approach:

# Correct: Sort and assign to indices 0, 1, 2, ...
rooks.sort()  # for rows
rooks.sort(key=lambda x: x[1])  # for columns

Pitfall 4: Modifying the Original Array Unintentionally

The Mistake: Not realizing that sorting the input array modifies it in place, which could cause issues if the array is needed elsewhere or in subsequent test cases.

Solution: If preserving the original array is important, create a copy first:

def minMoves(self, rooks: List[List[int]]) -> int:
    rooks_copy = rooks.copy()  # Work with a copy
    rooks_copy.sort()
    # ... rest of the solution