Minimum Moves to Get a Peaceful Board
AdobeThe problem
Given a 2D array rooks of length n, where rooks[i] = [xi, yi] represents the position of a rook on an n x n chessboard. The task is to move the rooks 1 cell at a time vertically or horizontally (to an adjacent cell) such that the board becomes peaceful. Determine the minimum number of moves required to make the board peaceful.
A peaceful board is one where each row and each column contains exactly one rook. A rook can move one cell at a time in a horizontal or vertical direction. At no point can two rooks occupy the same cell.
Input: rooks = [[0,2],[2,2],[2,1]] Output: 3 Explanation: The rooks are initially positioned incorrectly. The optimal moves are: Move the rook at (0,2) to (0,1). Move the rook at (2,2) to (1,2). Move the rook at (2,1) to (2,0). Now, the board is peaceful, and the total moves = 3.
Input: rooks = [[1,1],[1,3],[2,3],[3,2]] Output: 4 Explanation: An optimal way to make the board peaceful takes 4 moves.
Input: rooks = [[0,0],[0,1],[0,2],[0,3]]
- 1 <= n == rooks.length <= 500
- 0 <= xi, yi <= n - 1
- No two rooks start in the same cell.
cpp
class Solution {
public:
int minMoves(vector<vector<int>>& rooks) {
}
};java
class Solution {
public int minMoves(List<int[]> rooks) {
}
}python
class Solution:
def minMoves(self, rooks):javascript
class Solution {
static minMoves(rooks) {
}
}csharp
public class Solution {
public long minMoves(List<int[]> rooks) {
}
}go
func minMoves(rooks [][]int) int {
// Your code goes here
}Stuck? Show a way to structure it+
- 01Represent each conflicting piece by its coordinate.
- 02Sort coordinates in the relevant dimension.
- 03Pair or assign greedily in sorted order.
- 04Sum movement costs.
- 05Justify why crossing assignments are never better.
Reference answer
Then expect these follow-ups
When would a bipartite matching be necessary?
Tests: model boundaries
How do obstacles change the problem?
Tests: graph modeling
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question