LeetCode 3189 - Minimum Moves to Get a Peaceful Board

LeetCode Problem 3189

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting, Counting Sort

Solution

Problem Understanding

In this problem, we are given the positions of n rooks placed on an n x n chessboard. Each rook is represented as a pair [xi, yi], where xi is the row index and yi is the column index.

A peaceful board is defined as a board where:

• Every row contains exactly one rook
• Every column contains exactly one rook

This means the final arrangement must form a perfect permutation of rows and columns. No two rooks can share the same row or the same column.

We are allowed to move a rook one cell at a time, either vertically or horizontally. Every single-cell movement counts as one move. While moving rooks, we must also respect the constraint that two rooks can never occupy the same cell simultaneously.

The goal is to compute the minimum total number of moves needed to transform the initial configuration into a peaceful board.

The constraints are important:

• n <= 500
• There are exactly n rooks
• No two rooks initially occupy the same cell

Since n is only 500, an O(n log n) solution is easily acceptable, while anything exponential or factorial is impossible.

The key observation is that rows and columns can be handled independently. Horizontal moves only affect columns, and vertical moves only affect rows. This separability is what makes the problem manageable.

Some important edge cases include:

• The board may already be peaceful, requiring zero moves.
• Multiple rooks may initially share the same row or same column.
• All rooks could be stacked into a single row or single column.
• The optimal arrangement is not predetermined, we must discover which rook should end up in which row and column.

The problem guarantees that no two rooks start in the same cell, which avoids collision ambiguity at the beginning.

Approaches

Brute Force Approach

A brute force solution would attempt every possible peaceful configuration of rooks.

A peaceful board corresponds to assigning each rook to a unique row and unique column. Since there are n! possible row permutations and n! possible column permutations, the total search space becomes enormous.

For each possible final configuration, we could compute:

total cost = Σ |current_row - target_row| + |current_col - target_col|

Then we would select the minimum.

This approach is correct because it explicitly checks every valid final arrangement. However, it is computationally infeasible.

Even for n = 10, the number of permutations is already too large. With n = 500, this approach is completely impossible.

Optimal Approach

The key insight is that rows and columns are independent.

Suppose we only focus on rows first. We want exactly one rook in every row from 0 to n - 1.

If we sort the current rook row positions, then the optimal assignment is:

• Smallest row position goes to row 0
• Second smallest goes to row 1
• Third smallest goes to row 2
• And so on

This is a classic greedy matching argument.

Why does this work?

Because minimizing the sum of absolute differences is achieved by matching sorted values to sorted targets.

The same logic independently applies to columns.

Therefore:

1. Extract all row coordinates
2. Sort them
3. Match them against [0, 1, 2, ..., n - 1]
4. Sum absolute differences

Then repeat for columns.

The total answer is:

row movement cost + column movement cost

This gives the minimum number of moves.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n! × n) or worse	O(n)	Tries every peaceful configuration
Optimal	O(n log n)	O(n)	Uses sorting and greedy matching

Algorithm Walkthrough

1. Create two arrays:

• One containing all rook row positions
• One containing all rook column positions

We separate rows and columns because vertical and horizontal movement costs are independent. 2. Sort both arrays.

After sorting:

• rows[i] represents the i-th smallest row position
• cols[i] represents the i-th smallest column position

3. Assign rows greedily.

Since the final peaceful board must contain exactly one rook in every row from 0 to n - 1, the optimal assignment is:

• Smallest rook row goes to row 0
• Next smallest goes to row 1
• And so forth

Add:

abs(rows[i] - i)

to the answer for every i. 4. Assign columns greedily.

Apply the same logic to columns:

abs(cols[i] - i)

5. Return the total movement cost.

Why it works

The correctness comes from a standard property of minimizing absolute differences.

When minimizing:

Σ |a[i] - b[i]|

the optimal strategy is to sort both arrays and match corresponding elements.

The target rows are fixed as:

[0, 1, 2, ..., n - 1]

and similarly for columns.

Therefore, sorting the rook coordinates and matching them in order guarantees the minimum total Manhattan movement.

Since vertical and horizontal moves are independent, solving them separately and adding the results produces the global optimum.

Python Solution

from typing import List

class Solution:
    def minMoves(self, rooks: List[List[int]]) -> int:
        n = len(rooks)

        rows = sorted(r for r, _ in rooks)
        cols = sorted(c for _, c in rooks)

        moves = 0

        for i in range(n):
            moves += abs(rows[i] - i)
            moves += abs(cols[i] - i)

        return moves

The implementation starts by extracting all row coordinates and all column coordinates into separate arrays.

Both arrays are sorted because the optimal assignment pairs the smallest coordinate with the smallest target index, the second smallest with the second target index, and so on.

The loop iterates through every target row and column index from 0 to n - 1.

For each position:

• abs(rows[i] - i) computes the vertical movement needed
• abs(cols[i] - i) computes the horizontal movement needed

These values are accumulated into the final answer.

The implementation is compact because the greedy insight eliminates the need for simulation, BFS, or explicit rook movement tracking.

Go Solution

package main

import (
	"sort"
)

func minMoves(rooks [][]int) int {
	n := len(rooks)

	rows := make([]int, n)
	cols := make([]int, n)

	for i, rook := range rooks {
		rows[i] = rook[0]
		cols[i] = rook[1]
	}

	sort.Ints(rows)
	sort.Ints(cols)

	moves := 0

	for i := 0; i < n; i++ {
		moves += abs(rows[i] - i)
		moves += abs(cols[i] - i)
	}

	return moves
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

The Go implementation follows the same logic as the Python version.

Since Go does not provide a built-in absolute value function for integers, we define a helper abs function.

Slices are used to store row and column coordinates separately, and sort.Ints efficiently sorts them in ascending order.

Integer overflow is not a concern because the maximum possible answer is small relative to Go's integer range.

Worked Examples

Example 1

Input:

rooks = [[0,0],[1,0],[1,1]]

Step 1: Extract coordinates

Rook	Row	Column
[0,0]	0	0
[1,0]	1	0
[1,1]	1	1

Rows:

[0, 1, 1]

Columns:

[0, 0, 1]

Step 2: Sort

Rows:

[0, 1, 1]

Columns:

[0, 0, 1]

Step 3: Match against target indices

Target rows:

[0, 1, 2]

Target columns:

[0, 1, 2]

Row cost

i	rows[i]	target	cost
0	0	0	0
1	1	1	0
2	1	2	1

Row total:

1

Column cost

i	cols[i]	target	cost
0	0	0	0
1	0	1	1
2	1	2	1

Column total:

2

Final answer:

1 + 2 = 3

Example 2

Input:

rooks = [[0,0],[0,1],[0,2],[0,3]]

Step 1: Extract coordinates

Rows:

[0, 0, 0, 0]

Columns:

[0, 1, 2, 3]

Step 2: Sort

Already sorted.

Step 3: Compute row cost

Target rows:

[0, 1, 2, 3]

i	rows[i]	target	cost
0	0	0	0
1	0	1	1
2	0	2	2
3	0	3	3

Row total:

6

Step 4: Compute column cost

Columns already match perfectly.

i	cols[i]	target	cost
0	0	0	0
1	1	1	0
2	2	2	0
3	3	3	0

Column total:

0

Final answer:

6

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(n)	Arrays for rows and columns

The sorting operations are the most expensive part of the algorithm.

Extracting coordinates and computing the final sum both take linear time.

The additional space comes from storing separate row and column arrays.

Test Cases

from typing import List

class Solution:
    def minMoves(self, rooks: List[List[int]]) -> int:
        n = len(rooks)

        rows = sorted(r for r, _ in rooks)
        cols = sorted(c for _, c in rooks)

        moves = 0

        for i in range(n):
            moves += abs(rows[i] - i)
            moves += abs(cols[i] - i)

        return moves

sol = Solution()

assert sol.minMoves([[0,0],[1,0],[1,1]]) == 3  # example 1
assert sol.minMoves([[0,0],[0,1],[0,2],[0,3]]) == 6  # example 2

assert sol.minMoves([[0,0]]) == 0  # single rook already peaceful

assert sol.minMoves([[0,0],[1,1]]) == 0  # already peaceful board

assert sol.minMoves([[0,1],[1,1]]) == 1  # duplicate column

assert sol.minMoves([[1,0],[1,1]]) == 1  # duplicate row

assert sol.minMoves([[2,2],[2,0],[0,2]]) == 2  # both row and column conflicts

assert sol.minMoves([[3,3],[3,2],[3,1],[3,0]]) == 6  # all rooks in one row

assert sol.minMoves([[0,0],[2,2],[1,1]]) == 0  # diagonal already peaceful

assert sol.minMoves([[0,2],[2,0],[1,1]]) == 0  # permutation already peaceful

Test	Why
[[0,0],[1,0],[1,1]]	Validates sample case with row and column conflicts
[[0,0],[0,1],[0,2],[0,3]]	Validates all rooks stacked in one row
[[0,0]]	Smallest possible input
[[0,0],[1,1]]	Already peaceful board
[[0,1],[1,1]]	Duplicate column handling
[[1,0],[1,1]]	Duplicate row handling
[[2,2],[2,0],[0,2]]	Simultaneous row and column adjustment
[[3,3],[3,2],[3,1],[3,0]]	Large movement accumulation
[[0,0],[2,2],[1,1]]	Sorted coordinates already optimal
[[0,2],[2,0],[1,1]]	Peaceful permutation ordering

Edge Cases

One important edge case occurs when the board is already peaceful. In this scenario, every row and every column already contains exactly one rook. A buggy implementation might still attempt unnecessary reassignment or movement. This implementation handles the case naturally because each sorted coordinate already matches its target index, producing a movement cost of zero.

Another important case occurs when many rooks occupy the same row or same column. For example, all rooks might start in row 0. A naive greedy movement simulation could accidentally create collisions or perform non-optimal moves. This solution avoids explicit simulation entirely and instead computes the mathematical minimum directly through sorted matching.

A third edge case involves unordered peaceful configurations. For instance:

[[0,2],[2,0],[1,1]]

The board is already peaceful even though the rooks are not arranged diagonally. An incorrect implementation might mistakenly try to move rooks into a specific canonical pattern. This algorithm correctly recognizes that any permutation with unique rows and columns is valid, so the computed answer remains zero.