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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Transform to Chessboard

Difficulty: Hard

Problem Description

You are given an n x n binary grid board. In each move, you can swap any two rows with each other, or any two columns with each other. Return the minimum number of moves to transform the board into a chessboard board. If the task is impossible, return -1. A chessboard board is a board where no 0's and no 1's are 4-directionally adjacent.

Key Insights

  • A valid chessboard must have alternating 0's and 1's such that no two adjacent cells are the same.
  • The first row and the first column can dictate the pattern of the chessboard.
  • The number of 1's in each row and column should conform to the expected counts based on the chessboard pattern.
  • Swaps can be used to rearrange rows and columns, so we can only focus on the number of mismatches compared to the ideal chessboard pattern.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we can follow these steps:

  1. Check if the board can be transformed into a chessboard by ensuring that:
    • The count of 1's in each row and column matches the expected counts based on the chessboard pattern.
    • The first row and first column define the expected pattern for the rest of the rows and columns.
  2. Calculate the number of mismatches for both possible chessboard patterns (starting with 0 or 1).
  3. The minimum number of swaps needed will be the smaller of the two counts derived from the mismatches.
  4. If the board cannot be rearranged into a valid chessboard, return -1.

Code Solutions

def movesToChessboard(board):
    n = len(board)
    
    # Count the number of 1's in the first row and first column
    row_count = sum(board[0])
    col_count = sum(board[i][0] for i in range(n))
    
    # Check for the validity of the counts
    if row_count != n // 2 and row_count != (n + 1) // 2:
        return -1
    if col_count != n // 2 and col_count != (n + 1) // 2:
        return -1
    
    # Function to count the number of swaps required
    def count_swaps(arr, expected):
        count = 0
        for i in range(n):
            if arr[i] != expected[i % 2]:
                count += 1
        return count // 2
    
    # Calculate the expected patterns
    expected_row_pattern = [i % 2 for i in range(n)]
    expected_col_pattern = [i % 2 for i in range(n)]
    
    row_swaps = count_swaps(board, expected_row_pattern)
    col_swaps = count_swaps(list(zip(*board)), expected_col_pattern)
    
    return row_swaps + col_swaps
← Back to All Questions