Watch 2 video solutions for Minimum Moves to Get a Peaceful Board, a medium level problem involving Array, Greedy, Sorting. This walkthrough by Programming Live with Larry has 412 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given a 2D array rooks of length n, where rooks[i] = [xi, yi] 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 peaceful if there is exactly one rook in each row and each column.
Return the minimum number of moves required to get a peaceful board.
Note that at no point can there be two rooks in the same cell.
Example 1:
Input: rooks = [[0,0],[1,0],[1,1]]
Output: 3
Explanation:
Example 2:
Input: rooks = [[0,0],[0,1],[0,2],[0,3]]
Output: 6
Explanation:
Constraints:
1 <= n == rooks.length <= 5000 <= xi, yi <= n - 1Problem 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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Sorting | O(n log n) | O(n) | General solution; easiest to implement and explain in interviews |
| Greedy with Counting Sort | O(n) | O(n) | When row/column indices are bounded by n and you want a linear-time optimization |