Minimum Moves to Get a Peaceful Board - Solution & Explanation

Problem Overview: You are given positions of rooks on an n x n chessboard. The board is peaceful when no two rooks share the same row or column. Each move relocates a rook to another cell and costs the Manhattan distance between the old and new position. The goal is to compute the minimum total moves needed to reach a configuration where every row and every column contains exactly one rook.

Approach 1: Greedy with Sorting (O(n log n) time, O(n) space)

The key observation: row conflicts and column conflicts are independent. If you assign exactly one rook to each row and each column, the board automatically becomes peaceful. Extract all row indices and column indices from the rook positions. Sort both arrays. Then greedily match them to the target sequence 0..n-1. The minimal cost for rows is sum(|sortedRows[i] - i|), and the same logic applies to columns. Sorting ensures the smallest displacement pairing, a classic greedy trick used in sorting and median-alignment problems.

Approach 2: Greedy with Counting Sort Optimization (O(n) time, O(n) space)

The row and column values are bounded by the board size n, so you can avoid comparison sorting. Count how many rooks appear in each row and column using frequency arrays. Then simulate matching them with the target row indices 0..n-1. Track cumulative surplus or deficit while iterating through the rows and columns; each imbalance represents rooks that must move across indices. Summing these movements produces the same minimal cost as the sorted approach but runs in linear time. This relies on ideas from counting sort and greedy balancing.

Why the Greedy Pairing Works

Moving rooks across rows does not affect column conflicts and vice versa. By treating both dimensions independently, the problem reduces to aligning two sets of coordinates to consecutive indices. Sorting guarantees the minimal total absolute distance because pairing the smallest available value with the smallest target avoids cross movements. This property frequently appears in greedy algorithms that minimize total displacement.

Recommended for interviews: Start with the greedy insight that rows and columns can be optimized independently. Implement the sorting-based solution first because it is easy to reason about and runs in O(n log n). If the interviewer pushes for optimization, mention the counting-sort style linear solution that leverages the bounded index range.