Difficulty: 🔴 Hard
Topics: Array, Math, Bit Manipulation, Matrix

Solution

LeetCode 782 - Transform to Chessboard

Problem Understanding

This problem gives us an n x n binary matrix called board, where every cell contains either 0 or 1. In one operation, we are allowed to swap any two rows or swap any two columns. The goal is to determine the minimum number of swaps required to transform the board into a valid chessboard pattern.

A chessboard pattern means that no two adjacent cells, either horizontally or vertically, contain the same value. In other words:

Every row must alternate between 0 and 1
Every column must alternate between 0 and 1

For example:

and

are both valid chessboards.

The important detail is that we cannot flip bits. We are only allowed to reorder rows and reorder columns. This means the structure already present in the board determines whether a solution is possible.

The constraints are relatively small, with n <= 30, but brute force permutation approaches are still infeasible because there are n! possible row arrangements and n! possible column arrangements.

Several edge cases are important:

Boards that already satisfy the chessboard property should return 0
Boards where rows are not compatible complements of each other must return -1
Boards with incorrect counts of 0s and 1s in rows or columns are impossible
Odd-sized boards require stricter parity handling because one value must appear one more time than the other
Even-sized boards allow two valid alternating starting patterns

The challenge is recognizing the mathematical structure that valid chessboards must satisfy.

Approaches

Brute Force Approach

A brute force solution would try every possible permutation of rows and columns.

The idea would be:

Generate all row permutations
Generate all column permutations
Apply them to the board
Check whether the resulting board is a valid chessboard
Track the minimum number of swaps

This approach is correct because it explores every possible arrangement reachable through swaps.

However, it is computationally impossible for the given constraints. Even for n = 10, there are:

10! × 10! ≈ 1.3 × 10^13

possible configurations.

Therefore, brute force is far too slow.

Key Insight

A valid chessboard has an extremely rigid structure.

If one row is:

0 1 0 1

then every other row must be either:

0 1 0 1

or its complement:

1 0 1 0

No other row pattern is allowed.

The same property holds for columns.

This observation drastically reduces the problem. Instead of exploring permutations, we only need to verify:

Every row is either equal to the first row or its complement
Every column is either equal to the first column or its complement
The counts of the two patterns are valid
Compute the minimum swaps needed to place rows and columns into alternating order

A famous invariant for this problem is:

board[0][0] ^ board[i][0] ^ board[0][j] ^ board[i][j] == 0

for every cell (i, j).

If this condition fails anywhere, the board can never become a chessboard.

Why does this work?

In a valid chessboard:

Any row is either identical to the first row or its inverse
Any column is either identical to the first column or its inverse

The XOR condition precisely captures that relationship.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O((n!)² × n²)	O(n²)	Tries all row and column permutations
Optimal	O(n²)	O(1)	Uses structural properties of chessboards

Algorithm Walkthrough

Step 1: Validate the Board Structure

For every cell (i, j), check:

board[0][0] ^ board[i][0] ^ board[0][j] ^ board[i][j]

If this expression equals 1, the board is invalid.

This guarantees that every row and column is either identical to the first pattern or its complement.

Step 2: Count Row and Column Sums

Compute:

Number of 1s in the first row
Number of 1s in the first column

For a valid chessboard:

If n is even, both counts must equal n / 2
If n is odd, counts must be either n // 2 or n // 2 + 1

Otherwise, return -1.

Step 3: Count Misplaced Rows and Columns

We now determine how many rows and columns are out of position.

For rows:

At index i, the expected value is i % 2
Count how many positions already match alternating parity

Similarly for columns.

Example:

Expected pattern: 0 1 0 1
Actual pattern:   1 1 0 0

We count mismatches against alternating positions.

Step 4: Handle Even and Odd Board Sizes

If n is even:

Either alternating pattern is valid
Choose the smaller number of swaps

If n is odd:

Only one alternating pattern is possible because counts differ by one
We must choose the valid parity configuration

Step 5: Compute Final Answer

Each swap fixes two misplaced positions.

Therefore:

moves = row_swaps / 2 + col_swaps / 2

Return the total.

Why it works

The core invariant is that every row and column in a valid chessboard must be either identical to a base pattern or its complement. The XOR validation guarantees this structural property.

Once validity is established, the only remaining task is rearranging rows and columns into alternating order. Since swaps can reorder arbitrary rows and columns, the minimum number of swaps equals half the number of misplaced positions.

Because the algorithm checks all necessary structural constraints and computes the optimal rearrangement cost, it always produces the correct answer.

Python Solution

from typing import List

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

        # Step 1: Validate structure
        for i in range(n):
            for j in range(n):
                if board[0][0] ^ board[i][0] ^ board[0][j] ^ board[i][j]:
                    return -1

        row_sum = sum(board[0])
        col_sum = sum(board[i][0] for i in range(n))

        # Step 2: Validate counts
        if not (n // 2 <= row_sum <= (n + 1) // 2):
            return -1

        if not (n // 2 <= col_sum <= (n + 1) // 2):
            return -1

        row_swaps = 0
        col_swaps = 0

        # Step 3: Count matches with alternating pattern
        for i in range(n):
            if board[i][0] == i % 2:
                row_swaps += 1

            if board[0][i] == i % 2:
                col_swaps += 1

        # Step 4: Handle parity cases
        if n % 2:
            if row_swaps % 2:
                row_swaps = n - row_swaps

            if col_swaps % 2:
                col_swaps = n - col_swaps
        else:
            row_swaps = min(row_swaps, n - row_swaps)
            col_swaps = min(col_swaps, n - col_swaps)

        # Step 5: Each swap fixes two positions
        return (row_swaps + col_swaps) // 2

The implementation begins by validating the structural invariant using the XOR condition. This is the most important correctness check because it guarantees that all rows and columns belong to exactly two complementary patterns.

Next, the code counts the number of 1s in the first row and first column. Valid chessboards must have balanced counts, so any violation immediately returns -1.

The algorithm then computes how many rows and columns already align with an alternating parity pattern. These counts represent how close the board already is to the target arrangement.

The parity logic differs depending on whether n is even or odd. Even-sized boards allow two possible alternating layouts, while odd-sized boards only allow one valid orientation.

Finally, the number of swaps is computed by dividing misplaced counts by two because each swap corrects two positions simultaneously.

Go Solution

func movesToChessboard(board [][]int) int {
	n := len(board)

	// Step 1: Validate structure
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if board[0][0]^board[i][0]^board[0][j]^board[i][j] == 1 {
				return -1
			}
		}
	}

	rowSum := 0
	colSum := 0

	for i := 0; i < n; i++ {
		rowSum += board[0][i]
		colSum += board[i][0]
	}

	// Step 2: Validate counts
	if rowSum < n/2 || rowSum > (n+1)/2 {
		return -1
	}

	if colSum < n/2 || colSum > (n+1)/2 {
		return -1
	}

	rowSwaps := 0
	colSwaps := 0

	// Step 3: Count matching parity positions
	for i := 0; i < n; i++ {
		if board[i][0] == i%2 {
			rowSwaps++
		}

		if board[0][i] == i%2 {
			colSwaps++
		}
	}

	// Step 4: Handle parity
	if n%2 == 1 {
		if rowSwaps%2 == 1 {
			rowSwaps = n - rowSwaps
		}

		if colSwaps%2 == 1 {
			colSwaps = n - colSwaps
		}
	} else {
		if n-rowSwaps < rowSwaps {
			rowSwaps = n - rowSwaps
		}

		if n-colSwaps < colSwaps {
			colSwaps = n - colSwaps
		}
	}

	// Step 5: Each swap fixes two positions
	return (rowSwaps + colSwaps) / 2
}

The Go implementation follows the same logic as the Python version. Since Go does not provide Python's min function for integers directly, comparisons are performed manually.

Slices are used naturally for the matrix representation, and integer overflow is not a concern because n <= 30.

Worked Examples

Example 1

board =
[
  [0,1,1,0],
  [0,1,1,0],
  [1,0,0,1],
  [1,0,0,1]
]

Step 1: XOR Validation

Check:

board[0][0] ^ board[i][0] ^ board[0][j] ^ board[i][j]

All cells satisfy the condition, so transformation is possible.

Step 2: Count Sums

Value	Count
row_sum	2
col_sum	2

Since n = 4, both counts are valid.

Step 3: Count Matching Positions

First column:

[0,0,1,1]

Expected parity:

[0,1,0,1]

Matches occur at indices:

Index	Value	Expected	Match
0	0	0	Yes
1	0	1	No
2	1	0	No
3	1	1	Yes

So:

row_swaps = 2

First row:

[0,1,1,0]

Expected parity:

[0,1,0,1]

Matches at indices 0 and 1.

So:

col_swaps = 2

Step 4: Final Answer

Since n is even:

moves = (2 + 2) / 2 = 2

Answer:

Example 2

board =
[
  [0,1],
  [1,0]
]

XOR Validation

All cells satisfy the invariant.

Counts

Value	Count
row_sum	1
col_sum	1

Valid for n = 2.

Swap Counts

Rows and columns already alternate correctly.

row_swaps = 0
col_swaps = 0

Final answer:

Example 3

board =
[
  [1,0],
  [1,0]
]

XOR Validation

At position (1,1):

1 ^ 1 ^ 0 ^ 0 = 0

Structure still passes.

Counts

First column:

[1,1]

Count of 1s:

But for n = 2, valid count must be exactly 1.

Therefore:

return -1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Every cell is visited a constant number of times
Space	O(1)	Only a few counters and variables are used

The algorithm performs several passes over the matrix. The dominant cost comes from validating the XOR invariant across all n² cells. No auxiliary data structures proportional to input size are allocated, so the space usage remains constant.

Test Cases

from typing import List

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

        for i in range(n):
            for j in range(n):
                if board[0][0] ^ board[i][0] ^ board[0][j] ^ board[i][j]:
                    return -1

        row_sum = sum(board[0])
        col_sum = sum(board[i][0] for i in range(n))

        if not (n // 2 <= row_sum <= (n + 1) // 2):
            return -1

        if not (n // 2 <= col_sum <= (n + 1) // 2):
            return -1

        row_swaps = 0
        col_swaps = 0

        for i in range(n):
            if board[i][0] == i % 2:
                row_swaps += 1

            if board[0][i] == i % 2:
                col_swaps += 1

        if n % 2:
            if row_swaps % 2:
                row_swaps = n - row_swaps

            if col_swaps % 2:
                col_swaps = n - col_swaps
        else:
            row_swaps = min(row_swaps, n - row_swaps)
            col_swaps = min(col_swaps, n - col_swaps)

        return (row_swaps + col_swaps) // 2

sol = Solution()

assert sol.movesToChessboard([
    [0,1,1,0],
    [0,1,1,0],
    [1,0,0,1],
    [1,0,0,1]
]) == 2  # Provided example with two swaps

assert sol.movesToChessboard([
    [0,1],
    [1,0]
]) == 0  # Already a valid chessboard

assert sol.movesToChessboard([
    [1,0],
    [1,0]
]) == -1  # Impossible because column counts invalid

assert sol.movesToChessboard([
    [1,0,1],
    [0,1,0],
    [1,0,1]
]) == 0  # Valid odd-sized chessboard

assert sol.movesToChessboard([
    [0,0],
    [1,1]
]) == -1  # Rows are not complements

assert sol.movesToChessboard([
    [0,1,0],
    [1,0,1],
    [0,1,0]
]) == 0  # Perfect alternating pattern

assert sol.movesToChessboard([
    [1,1,0,0],
    [1,1,0,0],
    [0,0,1,1],
    [0,0,1,1]
]) == 2  # Requires row and column rearrangement

assert sol.movesToChessboard([
    [0,1],
    [0,1]
]) == -1  # Invalid because rows identical

assert sol.movesToChessboard([
    [0,1,1],
    [1,0,0],
    [1,0,0]
]) == 1  # Single row swap needed

Test	Why
`[[0,1,1,0], ...]`	Standard transformation example
`[[0,1],[1,0]]`	Already valid board
`[[1,0],[1,0]]`	Impossible due to invalid counts
`3x3 alternating board`	Odd-sized valid board
`[[0,0],[1,1]]`	Invalid row structure
Perfect alternating matrix	Confirms zero swaps
Symmetric 4x4 board	Tests swap counting
Duplicate rows	Tests impossibility detection
Single-swap odd case	Tests minimal rearrangement

Edge Cases

One important edge case occurs when the board already forms a valid chessboard. A careless implementation might still attempt swaps and overcount operations. The current solution correctly identifies this case because the parity matching counts already align with the expected alternating pattern, resulting in zero required swaps.

Another tricky case involves odd-sized boards. In an odd-sized chessboard, one bit value must appear exactly one more time than the other. For example, a 3 x 3 board must contain either two 0s and one 1, or two 1s and one 0 in each row and column pattern. The implementation handles this carefully by forcing the parity configuration that matches the required counts.

A third important edge case is when rows are not complements of each other. For example:

0 1 1
1 0 1

These rows are neither identical nor inverse patterns. Such boards can never become chessboards regardless of swaps. The XOR invariant immediately detects these invalid structures and returns -1.

Another subtle case is when the XOR structure passes but the counts are invalid. Example:

1 0
1 0

The rows satisfy the complement relation structurally, but the column counts are impossible for a chessboard. The separate row and column sum validation correctly catches this situation.