#782

Hard

LeetCode Problem Workspace

Transform to Chessboard

Determine the minimum swaps of rows or columns to convert an n x n binary board into a valid chessboard configuration.

Problem Statement

Given an n x n binary grid where each element is 0 or 1, you may swap any two rows or any two columns in one move. Your goal is to rearrange the board so that it forms a chessboard pattern, where no two identical numbers are adjacent horizontally or vertically.

Return the minimum number of moves needed to transform the grid into a valid chessboard. If it is impossible to achieve a chessboard through any sequence of row or column swaps, return -1.

Examples

Example 1

Input: board = [[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]]

Output: 2

One potential sequence of moves is shown. The first move swaps the first and second column. The second move swaps the second and third row.

Example 2

Input: board = [[0,1],[1,0]]

Output: 0

Also note that the board with 0 in the top left corner, is also a valid chessboard.

Example 3

Input: board = [[1,0],[1,0]]

Output: -1

No matter what sequence of moves you make, you cannot end with a valid chessboard.

Constraints

n == board.length
n == board[i].length
2 <= n <= 30
board[i][j] is either 0 or 1.

Solution Approach

Validate Row and Column Patterns

Check that all rows and all columns occur in exactly two patterns differing only in inversion. Count occurrences to ensure the board can be rearranged into a chessboard without violating adjacency rules.

Calculate Minimum Swaps for Rows and Columns

Determine the number of swaps needed to align rows and columns to the chessboard pattern using bitwise operations. Count mismatches against an ideal alternating sequence and compute swaps using integer division and parity checks.

Return Result or Detect Impossibility

Sum the calculated row and column swaps. If any validation step fails due to uneven counts or impossible pattern combinations, immediately return -1; otherwise, return the total number of swaps required.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on iterating through the n x n board for pattern counting and swap calculations, yielding O(n^2). Space complexity is O(n) for storing row and column pattern counts and intermediate computations.

What Interviewers Usually Probe

Check for equal counts of rows and columns with each pattern before attempting swaps.
Use bit manipulation to efficiently compare row and column patterns for mismatches.
Watch for parity issues: a chessboard requires even distribution or one-off differences depending on n being even or odd.

Common Pitfalls or Variants

Common pitfalls

Failing to validate that only two unique row and column patterns exist can lead to incorrect swap counts.
Ignoring parity constraints may suggest an achievable solution when it is impossible.
Counting swaps incorrectly without considering alternating sequence alignment often results in overestimating moves.

Follow-up variants

Compute swaps when only row swaps are allowed, ignoring column swaps.
Transform a non-square m x n binary board into a partial chessboard pattern under swap constraints.
Determine minimum swaps when initial board has more than two repeating row patterns and some cannot align.

FAQ

What is the main pattern recognition in Transform to Chessboard?

The core pattern involves ensuring exactly two unique row and column patterns exist, differing only by inversion, which aligns with the chessboard requirement.

Can I only swap rows or only swap columns to solve this problem?

Yes, but the minimum swaps must be calculated separately for rows and columns; some configurations may become impossible if restricted.

How do I detect if a board cannot become a chessboard?

Validate that each row and column occurs in exactly two patterns and satisfies parity constraints; any violation indicates impossibility.

What role does bit manipulation play in this solution?

Bit manipulation efficiently counts mismatches and aligns rows or columns with the ideal alternating sequence for calculating swaps.

Does board size affect the solution approach?

Yes, odd or even n changes parity checks and swap calculations, impacting whether a board configuration can reach a chessboard.

terminal

Solution

Solution 1: Pattern Observation + State Compression

In a valid chessboard, there are exactly two types of "rows".

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

class Solution:
    def movesToChessboard(self, board: List[List[int]]) -> int:
        def f(mask, cnt):
            ones = mask.bit_count()
            if n & 1:
                if abs(n - 2 * ones) != 1 or abs(n - 2 * cnt) != 1:
                    return -1
                if ones == n // 2:
                    return n // 2 - (mask & 0xAAAAAAAA).bit_count()
                return (n + 1) // 2 - (mask & 0x55555555).bit_count()
            else:
                if ones != n // 2 or cnt != n // 2:
                    return -1
                cnt0 = n // 2 - (mask & 0xAAAAAAAA).bit_count()
                cnt1 = n // 2 - (mask & 0x55555555).bit_count()
                return min(cnt0, cnt1)

        n = len(board)
        mask = (1 << n) - 1
        rowMask = colMask = 0
        for i in range(n):
            rowMask |= board[0][i] << i
            colMask |= board[i][0] << i
        revRowMask = mask ^ rowMask
        revColMask = mask ^ colMask
        sameRow = sameCol = 0
        for i in range(n):
            curRowMask = curColMask = 0
            for j in range(n):
                curRowMask |= board[i][j] << j
                curColMask |= board[j][i] << j
            if curRowMask not in (rowMask, revRowMask) or curColMask not in (
                colMask,
                revColMask,
            ):
                return -1
            sameRow += curRowMask == rowMask
            sameCol += curColMask == colMask
        t1 = f(rowMask, sameRow)
        t2 = f(colMask, sameCol)
        return -1 if t1 == -1 or t2 == -1 else t1 + t2

Continue Practicing

#805 split array with same average #810 chalkboard xor game #832 flipping an image