Jobs

Interviews

Discussions

Transform to Chessboard

Hard

Asked by:

16 views

Topics:

Arrays

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.

Example 1:

Input: board = [[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]]
Output: 2
Explanation: 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
Explanation: 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
Explanation: 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.

Try coding it in LeetCode

Transform to Chessboard

Hard

Asked by:

16 views

Topics:

Arrays

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.

Example 1:

Input: board = [[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]]
Output: 2
Explanation: 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
Explanation: 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
Explanation: 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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions (rows and columns) of the board, and can I assume it's always a square matrix?
What values can the elements of the board contain? Can I assume it's only 0 and 1?
If it is impossible to transform the board into a valid chessboard, what should the function return?
By 'moves', do you specifically mean swapping two adjacent rows or two adjacent columns, and is each swap considered one move?
If multiple valid chessboard configurations are possible, should I return the minimum number of moves required to reach *any* of them?

Brute Force Solution

Approach

The brute force approach to creating a chessboard involves checking every single possible arrangement of rows and columns. We will explore each possibility, checking if it can be transformed into a valid chessboard, and if so, counting the number of moves needed. Ultimately, we aim to identify the chessboard arrangement requiring the fewest moves.

Here's how the algorithm would work step-by-step:

Consider all possible row arrangements. For example, swap the first and second row, then the first and third row, and so on. Try every possible combination of row swaps.
For each row arrangement, check all possible column arrangements. Similar to rows, try all possible combinations of column swaps.
For each combination of row and column arrangement, check if it forms a valid chessboard.
If it's a valid chessboard, count how many row swaps and column swaps were needed to reach that arrangement.
Keep track of the arrangement that requires the minimum number of swaps across all arrangements explored.
After exploring every possible combination of row and column swaps, the arrangement with the fewest swaps represents the solution, and the number of swaps is the answer.

Code Implementation

import itertools

def transform_to_chessboard_brute_force(board):
    board_size = len(board)
    minimum_swaps = float('inf')

    rows = list(range(board_size))
    columns = list(range(board_size))

    for row_permutation in itertools.permutations(rows):
        for column_permutation in itertools.permutations(columns):
            
            arranged_board = []
            for row_index in row_permutation:
                new_row = []
                for column_index in column_permutation:
                    new_row.append(board[row_index][column_index])
                arranged_board.append(new_row)

            is_valid = True
            for row_index in range(board_size):
                for column_index in range(board_size):
                    if (row_index + column_index) % 2 == 0:
                        if arranged_board[row_index][column_index] != arranged_board[0][0]:
                            is_valid = False
                            break
                    else:
                        if arranged_board[row_index][column_index] == arranged_board[0][0]:
                            is_valid = False
                            break
                if not is_valid:
                    break
            
            if is_valid:
                row_swaps = 0
                for index in range(board_size):
                    if row_permutation[index] != index:
                        row_swaps += 1
                row_swaps = row_swaps // 2

                column_swaps = 0
                for index in range(board_size):
                    if column_permutation[index] != index:
                        column_swaps += 1
                column_swaps = column_swaps // 2
                
                total_swaps = row_swaps + column_swaps
                minimum_swaps = min(minimum_swaps, total_swaps)
    
    if minimum_swaps == float('inf'):
        return -1
    else:
        return minimum_swaps

# The brute force method exhaustively tries all possibilities
# and will return a correct result, but is extremely slow
def is_valid_chessboard(board):
    board_size = len(board)
    for row_index in range(board_size):
        for column_index in range(board_size):
            if (row_index + column_index) % 2 == 0:
                if board[row_index][column_index] != board[0][0]:
                    return False
            else:
                if board[row_index][column_index] == board[0][0]:
                    return False
    return True

# Calculate swaps required to achieve current arrangement
def calculate_swaps(permutation):
    swaps = 0
    for index in range(len(permutation)):
        if permutation[index] != index:
            swaps += 1
    return swaps // 2

# Checks all possible arrangements to find the min swaps
# Returns the minimum swaps or -1 if it is not possible
def transform_to_chessboard_brute_force_corrected(board):
    board_size = len(board)
    minimum_swaps = float('inf')

    rows = list(range(board_size))
    columns = list(range(board_size))

    # Iterate through all possible row permutations
    for row_permutation in itertools.permutations(rows):
        # Iterate through all possible column permutations
        for column_permutation in itertools.permutations(columns):
            
            arranged_board = []
            for row_index in row_permutation:
                new_row = []
                for column_index in column_permutation:
                    new_row.append(board[row_index][column_index])
                arranged_board.append(new_row)

            # Checks if arrangement creates valid chessboard
            if is_valid_chessboard(arranged_board):
                # Calculates the number of swaps required
                row_swaps = calculate_swaps(row_permutation)
                column_swaps = calculate_swaps(column_permutation)
                total_swaps = row_swaps + column_swaps

                minimum_swaps = min(minimum_swaps, total_swaps)

    if minimum_swaps == float('inf'):
        return -1
    else:
        return minimum_swaps

Big(O) Analysis

Time Complexity

O(n! * n!) – The algorithm explores all possible row arrangements and column arrangements, each of which involves calculating permutations. There are n! (n factorial) possible row arrangements and n! possible column arrangements. For each combination of row and column arrangement, checking if it's a valid chessboard involves iterating through all the elements, which takes O(n*n) time, but is dominated by the arrangement generation. Thus, the overall time complexity is O(n! * n!).

Space Complexity

O(N^2 * N!) – The algorithm explores all possible row and column arrangements. Generating each permutation of rows requires O(N) space, and since there are N rows, storing all possible row arrangements implicitly utilizes space proportional to N!. Similarly, the column arrangements also require O(N!) space. For each row and column arrangement, a copy of the original N x N board might be created to check if it is a valid chessboard, incurring O(N^2) space. The overall space complexity is therefore O(N^2 * N!).

Optimal Solution

Approach

The goal is to rearrange rows and columns of a square grid to resemble a chessboard pattern. The optimal strategy involves verifying if a chessboard arrangement is even possible, and then counting the minimum number of row and column swaps to achieve it.

Here's how the algorithm would work step-by-step:

First, check if a valid chessboard pattern is even possible. This means ensuring that there are only two distinct rows and two distinct columns.
Count how many rows start with a '0'. The ideal number for a chessboard is either half the size of the board or half the size minus one (in case the size is odd).
If the count of rows starting with '0' doesn't match the ideal count, calculate the number of swaps needed to fix the rows. These swaps involve flipping some rows completely (0 becomes 1 and vice-versa).
Do the same as above for the columns. Figure out the ideal number of columns starting with '0', and if it doesn't match, calculate the minimum column swaps required.
There are potentially two ways to arrange the rows and two ways to arrange the columns. Choose the arrangement (either '0101...' or '1010...') that requires fewer swaps, and perform those swaps.
Finally, return the total number of row swaps plus the total number of column swaps to get the minimum number of moves.

Code Implementation

def transform_to_chessboard(board):
    board_size = len(board)

    def calculate_moves(array_to_arrange):
        ones_count = sum(array_to_arrange)
        if board_size % 2 == 0:
            if ones_count != board_size // 2:
                return float('inf')
        else:
            if ones_count != board_size // 2 and ones_count != (board_size + 1) // 2:
                return float('inf')

        zeros_at_even_index = 0
        for i in range(0, board_size, 2):
            if array_to_arrange[i] == 0:
                zeros_at_even_index += 1

        if board_size % 2 == 0:
            return min(zeros_at_even_index, board_size // 2 - zeros_at_even_index)
        else:
            return zeros_at_even_index

    # Verify if the board can be transformed into a chessboard.
    for i in range(board_size):
        for j in range(board_size):
            if board[0][0] ^ board[i][0] != board[0][j] ^ board[i][j]:
                return -1

    row_swaps = calculate_moves(board[0])
    col_swaps = calculate_moves([board[i][0] for i in range(board_size)])

    # Return -1 if either the rows or columns cannot be arranged.
    if row_swaps == float('inf') or col_swaps == float('inf'):
        return -1

    # Total moves required: row swaps + column swaps.
    return row_swaps + col_swaps

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through the n rows and n columns of the chessboard once to validate the board and count the number of rows and columns starting with '0'. Checking if a valid chessboard pattern is possible requires comparing each row and column with others which takes O(n^2) time. Calculating the number of row and column swaps involves iterating through each row and column once, taking O(n) time each. However, the dominant operation is the initial validation step, where each row/column may be compared to every other row/column. Therefore, the overall time complexity is O(n²).

Space Complexity

O(1) – The algorithm's space complexity is O(1) because it primarily uses a few integer variables to store counts and intermediate results during row and column swaps. There are no auxiliary data structures like lists or hash maps that scale with the input size, N, which represents the dimension of the square grid. The row and column swap operations are performed in-place, further minimizing the usage of extra space. Therefore, the space required remains constant regardless of the size of the chessboard.

Edge Cases

Case	How to Handle
Null or empty input array	Return -1 immediately as a chessboard cannot be formed from an empty board.
Non-square matrix (rows != columns)	Return -1 since a chessboard must be square.
Matrix with only one row/column	Check if the single row/column is alternating; if not, no valid transformation is possible, return -1, otherwise 0 moves.
A row is not a valid chessboard row (e.g., not alternating or more than half of its entries are the same value)	If any row violates chessboard properties, then no transformation is possible, return -1.
Two rows are identical when they shouldn't be (after flipping)	Rows can either be identical or the complement of each other; check row compatibility or return -1.
More than n/2 rows starting with 0 or 1 (n is dimension of the board)	Correct the imbalance by flipping to ensure valid chessboard properties are met.
Input array contains values other than 0 and 1	Return -1, as the problem definition specifies a binary board of 0s and 1s.
No transformation is needed (already a chessboard)	The algorithm should still correctly determine the number of moves (0 in this case).

Null or empty input array

How to Handle:

Return -1 immediately as a chessboard cannot be formed from an empty board.

Non-square matrix (rows != columns)

How to Handle:

Return -1 since a chessboard must be square.

Matrix with only one row/column

How to Handle:

Check if the single row/column is alternating; if not, no valid transformation is possible, return -1, otherwise 0 moves.

A row is not a valid chessboard row (e.g., not alternating or more than half of its entries are the same value)

How to Handle:

If any row violates chessboard properties, then no transformation is possible, return -1.

Two rows are identical when they shouldn't be (after flipping)

How to Handle:

Rows can either be identical or the complement of each other; check row compatibility or return -1.

More than n/2 rows starting with 0 or 1 (n is dimension of the board)

How to Handle:

Correct the imbalance by flipping to ensure valid chessboard properties are met.

Input array contains values other than 0 and 1

How to Handle:

Return -1, as the problem definition specifies a binary board of 0s and 1s.

No transformation is needed (already a chessboard)

How to Handle:

The algorithm should still correctly determine the number of moves (0 in this case).

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions (rows and columns) of the board, and can I assume it's always a square matrix?
What values can the elements of the board contain? Can I assume it's only 0 and 1?
If it is impossible to transform the board into a valid chessboard, what should the function return?
By 'moves', do you specifically mean swapping two adjacent rows or two adjacent columns, and is each swap considered one move?
If multiple valid chessboard configurations are possible, should I return the minimum number of moves required to reach *any* of them?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Consider all possible row arrangements. For example, swap the first and second row, then the first and third row, and so on. Try every possible combination of row swaps.
For each row arrangement, check all possible column arrangements. Similar to rows, try all possible combinations of column swaps.
For each combination of row and column arrangement, check if it forms a valid chessboard.
If it's a valid chessboard, count how many row swaps and column swaps were needed to reach that arrangement.
Keep track of the arrangement that requires the minimum number of swaps across all arrangements explored.
After exploring every possible combination of row and column swaps, the arrangement with the fewest swaps represents the solution, and the number of swaps is the answer.

Code Implementation

import itertools

def transform_to_chessboard_brute_force(board):
    board_size = len(board)
    minimum_swaps = float('inf')

    rows = list(range(board_size))
    columns = list(range(board_size))

    for row_permutation in itertools.permutations(rows):
        for column_permutation in itertools.permutations(columns):
            
            arranged_board = []
            for row_index in row_permutation:
                new_row = []
                for column_index in column_permutation:
                    new_row.append(board[row_index][column_index])
                arranged_board.append(new_row)

            is_valid = True
            for row_index in range(board_size):
                for column_index in range(board_size):
                    if (row_index + column_index) % 2 == 0:
                        if arranged_board[row_index][column_index] != arranged_board[0][0]:
                            is_valid = False
                            break
                    else:
                        if arranged_board[row_index][column_index] == arranged_board[0][0]:
                            is_valid = False
                            break
                if not is_valid:
                    break
            
            if is_valid:
                row_swaps = 0
                for index in range(board_size):
                    if row_permutation[index] != index:
                        row_swaps += 1
                row_swaps = row_swaps // 2

                column_swaps = 0
                for index in range(board_size):
                    if column_permutation[index] != index:
                        column_swaps += 1
                column_swaps = column_swaps // 2
                
                total_swaps = row_swaps + column_swaps
                minimum_swaps = min(minimum_swaps, total_swaps)
    
    if minimum_swaps == float('inf'):
        return -1
    else:
        return minimum_swaps

# The brute force method exhaustively tries all possibilities
# and will return a correct result, but is extremely slow
def is_valid_chessboard(board):
    board_size = len(board)
    for row_index in range(board_size):
        for column_index in range(board_size):
            if (row_index + column_index) % 2 == 0:
                if board[row_index][column_index] != board[0][0]:
                    return False
            else:
                if board[row_index][column_index] == board[0][0]:
                    return False
    return True

# Calculate swaps required to achieve current arrangement
def calculate_swaps(permutation):
    swaps = 0
    for index in range(len(permutation)):
        if permutation[index] != index:
            swaps += 1
    return swaps // 2

# Checks all possible arrangements to find the min swaps
# Returns the minimum swaps or -1 if it is not possible
def transform_to_chessboard_brute_force_corrected(board):
    board_size = len(board)
    minimum_swaps = float('inf')

    rows = list(range(board_size))
    columns = list(range(board_size))

    # Iterate through all possible row permutations
    for row_permutation in itertools.permutations(rows):
        # Iterate through all possible column permutations
        for column_permutation in itertools.permutations(columns):
            
            arranged_board = []
            for row_index in row_permutation:
                new_row = []
                for column_index in column_permutation:
                    new_row.append(board[row_index][column_index])
                arranged_board.append(new_row)

            # Checks if arrangement creates valid chessboard
            if is_valid_chessboard(arranged_board):
                # Calculates the number of swaps required
                row_swaps = calculate_swaps(row_permutation)
                column_swaps = calculate_swaps(column_permutation)
                total_swaps = row_swaps + column_swaps

                minimum_swaps = min(minimum_swaps, total_swaps)

    if minimum_swaps == float('inf'):
        return -1
    else:
        return minimum_swaps

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, check if a valid chessboard pattern is even possible. This means ensuring that there are only two distinct rows and two distinct columns.
Count how many rows start with a '0'. The ideal number for a chessboard is either half the size of the board or half the size minus one (in case the size is odd).
If the count of rows starting with '0' doesn't match the ideal count, calculate the number of swaps needed to fix the rows. These swaps involve flipping some rows completely (0 becomes 1 and vice-versa).
Do the same as above for the columns. Figure out the ideal number of columns starting with '0', and if it doesn't match, calculate the minimum column swaps required.
There are potentially two ways to arrange the rows and two ways to arrange the columns. Choose the arrangement (either '0101...' or '1010...') that requires fewer swaps, and perform those swaps.
Finally, return the total number of row swaps plus the total number of column swaps to get the minimum number of moves.

Code Implementation

def transform_to_chessboard(board):
    board_size = len(board)

    def calculate_moves(array_to_arrange):
        ones_count = sum(array_to_arrange)
        if board_size % 2 == 0:
            if ones_count != board_size // 2:
                return float('inf')
        else:
            if ones_count != board_size // 2 and ones_count != (board_size + 1) // 2:
                return float('inf')

        zeros_at_even_index = 0
        for i in range(0, board_size, 2):
            if array_to_arrange[i] == 0:
                zeros_at_even_index += 1

        if board_size % 2 == 0:
            return min(zeros_at_even_index, board_size // 2 - zeros_at_even_index)
        else:
            return zeros_at_even_index

    # Verify if the board can be transformed into a chessboard.
    for i in range(board_size):
        for j in range(board_size):
            if board[0][0] ^ board[i][0] != board[0][j] ^ board[i][j]:
                return -1

    row_swaps = calculate_moves(board[0])
    col_swaps = calculate_moves([board[i][0] for i in range(board_size)])

    # Return -1 if either the rows or columns cannot be arranged.
    if row_swaps == float('inf') or col_swaps == float('inf'):
        return -1

    # Total moves required: row swaps + column swaps.
    return row_swaps + col_swaps

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return -1 immediately as a chessboard cannot be formed from an empty board.
Non-square matrix (rows != columns)	Return -1 since a chessboard must be square.
Matrix with only one row/column	Check if the single row/column is alternating; if not, no valid transformation is possible, return -1, otherwise 0 moves.
A row is not a valid chessboard row (e.g., not alternating or more than half of its entries are the same value)	If any row violates chessboard properties, then no transformation is possible, return -1.
Two rows are identical when they shouldn't be (after flipping)	Rows can either be identical or the complement of each other; check row compatibility or return -1.
More than n/2 rows starting with 0 or 1 (n is dimension of the board)	Correct the imbalance by flipping to ensure valid chessboard properties are met.
Input array contains values other than 0 and 1	Return -1, as the problem definition specifies a binary board of 0s and 1s.
No transformation is needed (already a chessboard)	The algorithm should still correctly determine the number of moves (0 in this case).

Null or empty input array

How to Handle:

Return -1 immediately as a chessboard cannot be formed from an empty board.

Non-square matrix (rows != columns)

How to Handle:

Return -1 since a chessboard must be square.

Matrix with only one row/column

How to Handle:

Check if the single row/column is alternating; if not, no valid transformation is possible, return -1, otherwise 0 moves.

A row is not a valid chessboard row (e.g., not alternating or more than half of its entries are the same value)

How to Handle:

If any row violates chessboard properties, then no transformation is possible, return -1.

Two rows are identical when they shouldn't be (after flipping)

How to Handle:

Rows can either be identical or the complement of each other; check row compatibility or return -1.

More than n/2 rows starting with 0 or 1 (n is dimension of the board)

How to Handle:

Correct the imbalance by flipping to ensure valid chessboard properties are met.

Input array contains values other than 0 and 1

How to Handle:

Return -1, as the problem definition specifies a binary board of 0s and 1s.

No transformation is needed (already a chessboard)

How to Handle:

The algorithm should still correctly determine the number of moves (0 in this case).