We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Transform to Chessboard

Number: 798

Difficulty: Hard

Paid? No

Companies: Citadel, Google

Problem Description

Given an n x n binary board, you can swap any two rows or any two columns. The goal is to transform the board into a chessboard configuration (i.e. no two adjacent cells in the 4 directions are the same) using the minimum number of swaps. If it is impossible to do so, return -1.

Key Insights

  • A valid chessboard must have exactly two types of rows (or columns): one pattern and its bitwise complement.
  • The first row (and similarly the first column) fully determines the structure; all other rows must equal this or its inverse.
  • The number of 1’s in any valid row (or column) must be either n/2 (if n is even) or (n±1)/2 (if n is odd).
  • Only row swaps and column swaps are allowed; therefore, reordering rows and columns independently is possible.
  • The minimum swaps for rows (or columns) can be determined by comparing the current order against an “ideal” alternating pattern (either starting with 0 or 1) and counting mismatches.
  • Bit manipulation can be used to represent rows/columns as integers (or bitmasks), which simplifies the checking of complements and mismatch counts.

Space and Time Complexity

Time Complexity: O(n^2) – we scan each row and column multiple times. Space Complexity: O(n) – extra space is used to store bit masks and count arrays (independent of n^2 board size).

Solution

We first check if the board can be transformed into a chessboard. For this, we verify that every row is either identical to the first row or its complement. Similarly, we check columns. Next, we convert the first row and first column into bit masks. There are expected “ideal” alternating bit masks for rows and columns (e.g., 0101… and 1010…). For both rows and columns, a helper routine computes the number of swaps required to convert the current bitmask into the ideal one while considering whether n is odd or even. In the even case, we choose the pattern which minimizes the number of swaps. In the odd case, one of the alternating patterns is forced by the count of ones. Finally, the result is the sum of row swaps and column swaps. If any validation fails, the board cannot be turned into a chessboard and we return -1.

We use bit manipulation to quickly count the mismatches and compute the swap count (note that one swap fixes two positions so we divide the number of mismatches by 2).

Code Solutions

# Python solution for Transform to Chessboard

class Solution:
    def movesToChessboard(self, board: list[list[int]]) -> int:
        n = len(board)
        
        # Check if board is transformable:
        for i in range(n):
            for j in range(n):
                # For a valid chessboard, the following must hold:
                # board[i][j] ^ board[0][j] ^ board[i][0] ^ board[0][0] == 0
                if board[i][j] ^ board[0][j] ^ board[i][0] ^ board[0][0]:
                    return -1
        
        # Function to compute the minimum swaps for rows or columns
        def getSwaps(mask: int) -> int:
            ones = bin(mask).count("1")
            # Create an alternating bit mask based on starting with 0 (pattern: 0101...)
            alt0 = int("".join("0" if i % 2 else "1" for i in range(n)), 2)
            alt1 = int("".join("1" if i % 2 else "0" for i in range(n)), 2)
            
            # If n is even, choose the pattern that minimizes the number of mismatches:
            if n % 2 == 0:
                swaps0 = bin(mask ^ alt0).count("1")
                swaps1 = bin(mask ^ alt1).count("1")
                return min(swaps0, swaps1) // 2
            # If n is odd, the number of ones is forced. Only one of the patterns is valid.
            else:
                if ones * 2 < n:  # Means ones is n//2, so pattern must start with 1 at index 0
                    return bin(mask ^ alt1).count("1") // 2
                else:
                    return bin(mask ^ alt0).count("1") // 2
        
        # Construct the bit mask for the first row and first column
        rowMask = 0
        colMask = 0
        for i in range(n):
            rowMask = (rowMask << 1) | board[0][i]
            colMask = (colMask << 1) | board[i][0]
        
        rowSwaps = getSwaps(rowMask)
        colSwaps = getSwaps(colMask)
        return rowSwaps + colSwaps


# Example usage:
# sol = Solution()
# print(sol.movesToChessboard([[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]]))
← Back to All Questions