We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Moves to Get a Peaceful Board

Number: 3504

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

Given an n x n chessboard with n rooks placed such that each rook's location is given by rooks[i] = [x_i, y_i] (with no two rooks at the same cell), the goal is to move the rooks one cell at a time (vertically or horizontally) so that the board becomes peaceful. A peaceful board means that every row and every column contains exactly one rook. Moves must be planned so that at no point do two rooks share the same cell. Return the minimum number of moves needed to achieve a peaceful configuration.

Key Insights

  • The problem can be separated into two independent tasks: assigning unique rows and unique columns to the rooks.
  • Since rooks move one cell at a time, the cost to move a rook from row x to row r is |x - r|, and similarly for columns.
  • To minimize the total moves, sort the list of current row indices and match them to the target rows (0 to n-1). Repeat the process for column indices.
  • The sum of the absolute differences for rows plus the sum for columns gives the minimum number of moves.
  • Sorting naturally aligns the positions in an optimal manner due to the properties of the absolute difference metric.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting of the rows and columns. Space Complexity: O(n) for storing the sorted row and column lists.

Solution

We start by extracting the row and column coordinates of the rooks. Since each move cost is the absolute difference in positions and the moves in rows and columns are independent, we solve the row moves and column moves individually. Sort the list of current row coordinates and assign them optimally to target rows 0, 1, ..., n-1. Similarly, sort the column coordinates and assign them to target columns. The sum of these differences is the answer.

This approach uses sorting (for optimal pairing) and simply iterates the lists to compute the absolute differences, achieving both clarity and efficiency.

Code Solutions

# Python solution
def minMovesToPeacefulBoard(rooks):
    # Number of rooks equals board size n
    n = len(rooks)
    
    # Extract row and column indices
    row_positions = [rook[0] for rook in rooks]
    col_positions = [rook[1] for rook in rooks]
    
    # Sort the positions for optimal pairing with target indices
    row_positions.sort()
    col_positions.sort()
    
    total_moves = 0
    # Calculate total moves for rows and columns separately
    for i in range(n):
        # For rows, assign target row i and compute move cost
        total_moves += abs(row_positions[i] - i)
        # For columns, assign target column i and compute move cost
        total_moves += abs(col_positions[i] - i)
    
    return total_moves

# Example test
print(minMovesToPeacefulBoard([[0,0],[1,0],[1,1]]))  # Expected output: 3
← Back to All Questions