Is Minimum Moves to Get a Peaceful Board easy or hard?

Minimum Moves to Get a Peaceful Board is generally classified as Medium difficulty. The tricky part is recognizing that row and column adjustments are independent and that sorting coordinates minimizes total movement. Once that insight is clear, the implementation is straightforward.

Minimum Moves to Get a Peaceful Board Python/Java solution

Most implementations extract row and column coordinates, sort them, and compute the sum of absolute differences from 0..n-1. The same greedy logic works across Python, Java, C++, Go, and TypeScript. The algorithm is short and typically fits within 10–20 lines of code.

How to solve Minimum Moves to Get a Peaceful Board in O(n)?

Use frequency arrays for rows and columns instead of sorting. Count how many rooks appear in each index, then iterate from 0 to n-1 while tracking surplus or deficit of rooks that must shift positions. The accumulated movement equals the minimal number of moves. Because the indices are bounded by n, this approach runs in linear time.

What is the best approach for Minimum Moves to Get a Peaceful Board?

The optimal strategy uses a greedy observation: rows and columns can be optimized independently. Collect all rook row indices and column indices, sort them, and match them with target positions 0..n-1. The total minimum moves equal the sum of absolute differences between the sorted coordinates and their target indices. This runs in O(n log n) time and O(n) space.

Is Minimum Moves to Get a Peaceful Board asked at Google/Amazon/Meta?

Greedy alignment and coordinate pairing problems frequently appear in interviews at companies like Google, Amazon, and Meta. While the exact problem ID may vary, the underlying idea—sorting coordinates and minimizing total absolute displacement—is a common interview pattern.

What data structure is used in Minimum Moves to Get a Peaceful Board?

The solution mainly uses arrays or lists to store row and column indices. Sorting or counting-frequency arrays are applied to align these indices with target positions. No complex structures like trees or graphs are required.

What is the time complexity of Minimum Moves to Get a Peaceful Board?

The standard solution runs in O(n log n) time because it sorts the row and column arrays. Space complexity is O(n) for storing the coordinates. With a counting-sort style frequency approach, the complexity can be improved to O(n) time while keeping O(n) space.

Description Hints 5 Solution Video 19:05

3189. Minimum Moves to Get a Peaceful Board

Medium75.9% acceptancePremium elsewhere, free here

Given a 2D array rooks of length n, where rooks[i] = [x_i, y_i] 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 <= 500
0 <= x_i, y_i <= n - 1
The input is generated such that there are no 2 rooks in the same cell.

Topics

Hints open one at a time

Hint 1

Think of a greedy method.

Hint 2

First, distribute the rooks in individual rows.

Hint 3

You can do this by sorting all rooks by their rows. Then assign the first one to the first row, the second one to the second row, and so on.

Hint 4

After you've distributed rooks across all rows, now do the same for columns.

Hint 5

Sort rooks by their columns and then assign the first one to the first column and so on.

19:05

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

3189. Minimum Moves to Get a Peaceful Board

Topics

Hints open one at a time

Similar problems