782. Transform to Chessboard

HardBit ManipulationArrayMathMatrix

Problem Description

In this problem, we are given an `n x n` binary grid called `board`. The board consists only of `0`s and `1`s. We can make moves to transform this grid into a "chessboard" configuration. A "chessboard" configuration is defined as a board where no `0`s are adjacent to other `0`s and no `1`s are adjacent to other `1`s, in any of the four directions (up, down, left, right).

The allowed moves are to swap any two rows or any two columns. The objective is to find the minimum number of moves required to achieve the "chessboard" configuration. If it's impossible to achieve such a configuration, the answer should be `-1`.

Intuition

The solution approach involves understanding what constitutes a valid chessboard arrangement and then determining if it can be achieved through the allowed row and column swaps.

• Only two patterns of rows and two patterns of columns are allowed in a valid chessboard -- one row pattern is the inverse of the other, and the same goes for columns.
• Each move can swap two rows or two columns. This means you can only rearrange the order of rows and columns, not change their contents.
• The number of `1`s must be the same as the number of `0`s in each row and column, or at most one more (or one less) if the size of the board `n` is odd.
• Every row and column must match one of the two valid patterns for the board to potentially be transformed into a chessboard pattern.

Given these constraints, the solution checks the following:

1. Validate if the initial board could be transformed into a chessboard. This involves checking the counts of `0`s and `1`s in each row and column and ensuring they match the expected patterns.
2. If the board can potentially be transformed, we proceed to count the number of moves required. This is done by examining the binary representation of the row and column patterns to determine the minimum number of swaps needed.

By defining the problem in terms of binary patterns and bit manipulation, we can achieve an efficient and effective solution.

Solution Approach

The solution uses bit manipulation to effectively count and compare the 1s and 0s in the rows and columns, determining if the board can be converted into a chessboard configuration. Let's walk through the implementation of the solution:

1. Row and Column Masks: For a board of size `n`, a bitmask of `n` bits is created, where each bit can represent a cell in the board's row or column. Two masks are computed: `rowMask` for the first row and `colMask` for the first column, by setting bits to `1` whenever thereโs a `1` in the respective locations.

2. Checking for Impossible Cases: All other rows and columns must be identical to or the inverse of these masks. The function checks if each row and column is either the same as the `rowMask`/`colMask` or their bitwise NOT (`^ mask`). If a row or column does not match either pattern, the board cannot be transformed into a chessboard, so the function immediately returns `-1`.

3. Counting the Same Patterns: For each row and column that matches `rowMask`/`colMask`, counters named `sameRow` and `sameCol` are incremented. These keep track of how many rows and columns match the respective first row and column masks.

4. Counting Moves: A nested function `f(mask, cnt)` is defined to compute the number of swaps needed for either rows or columns.

• It first checks whether the counts of `1`s in `mask` and `cnt` are compatible with creating a chessboard pattern considering the board size `n` (even or odd).
• If compatible, it calculates the minimum number of swaps. For an even number of `n`, it compares the counts of swaps needed if the majority of elements are `0`s or `1`s (`cnt0` and `cnt1`). For an odd `n`, the function directly computes the count based on the majority of `1`s in `mask`.
5. Using the Helper Function: The movement counts for rows and columns are obtained by calling the helper function `f()` with `rowMask, sameRow` and `colMask, sameCol` respectively.

6. Result: Finally, if any of the movement counts are `-1`, indicating an impossible transformation, the function returns `-1`. Otherwise, it returns the sum of moves for rows and columns as the minimum number of moves required to transform the board.

This algorithm efficiently addresses the complexity of the problem through bit manipulation, providing an elegant solution.

๐ช
Level Up Your
Algo Skills

Example Walkthrough

Let's consider a small 3x3 binary grid example to illustrate the solution approach. Suppose we have the following grid:

``````1board = [
2    [0, 1, 0],
3    [1, 1, 1],
4    [0, 0, 0]
5]``````

Step-by-step, we will use the solution approach to try to transform this grid into a chessboard configuration.

• The `rowMask` is based on the first row, which would be `010` in binary, reflecting the configuration of `0`s and `1`s.
• The `colMask` is based on the first column, which would be `100` in binary.
2. Checking for Impossible Cases:

• The second row `111` is neither the same as the `rowMask` (`010`) nor its inverse (`101`). This means the configuration cannot be achieved, and we would return `-1`.
• However, for the sake of the example, let's assume the second row was `101` and the third row was `010`, which are the inverse of `rowMask` and match the chessboard configuration criteria.
• The second and third columns are `110` and `000`, respectively. Neither matches the `colMask` (`100`) nor its inverse (`011`), resulting in `-1`.
3. Counting the Same Patterns:

• If the rows and columns were valid, we would count how many match the `rowMask`/`colMask`. For this step, let's assume two rows and two columns match `rowMask`/`colMask`.
4. Counting Moves:

• The helper function `f(mask, cnt)` would calculate swaps for rows and columns. However, here we already concluded it's impossible due to step 2.
5. Using the Helper Function:

• The function `f()` is not used here because we know it's impossible to transform the board.
6. Result:

• Since there are impossible cases, the function would return `-1`. If it were possible, we would sum the row and column swap counts from `f()` to find the minimum number of moves.

In this example, the board cannot be transformed into a chessboard configuration due to inconsistencies with `rowMask` and `colMask`. This demonstrates how the algorithm quickly identifies whether a transformation is feasible before proceeding with more complex calculations.

Python Solution

``````1class Solution:
2    def movesToChessboard(self, board: List[List[int]]) -> int:
3        # Define a helper function to calculate the moves to arrange rows/columns
4        def calculate_moves(mask: int, count: int) -> int:
5            # Count the number of ones in the mask
7
8            # If the board size is odd
9            if n & 1:
10                # Check if the number of ones or the counts are valid
11                if abs(n - 2 * ones) != 1 or abs(n - 2 * count) != 1:
12                    return -1
13                # If there is a perfect split in ones, calculate the moves needed for arrangement
14                if ones == n // 2:
15                    return n // 2 - (mask & 0xAAAAAAAA).bit_count()
16                return (n + 1) // 2 - (mask & 0x55555555).bit_count()
17            else:
18                # If the board size is even and ones and count are not equal to half of the board size
19                if ones != n // 2 or count != n // 2:
20                    return -1
21                # Count the moves needed when ones are at even or odd positions
22                moves_even = n // 2 - (mask & 0xAAAAAAAA).bit_count()
23                moves_odd = n // 2 - (mask & 0x55555555).bit_count()
24                # Return the minimum of two move counts
25                return min(moves_even, moves_odd)
26
27        # Get the size of the board
28        n = len(board)
29        # Create a bitmask representing all possible positions for a size n board
30        mask = (1 << n) - 1
33        # Build the mask for the first row and column
34        for i in range(n):
35            row_mask |= board[0][i] << i
36            col_mask |= board[i][0] << i
37
38        # Bitwise NOT applied to get reverse masks
41        # Counters for rows and columns that match the first one
42        same_row_count = same_col_count = 0
43
44        # Traverse the board row and column wise
45        for i in range(n):
47            for j in range(n):
48                cur_row_mask |= board[i][j] << j
49                cur_col_mask |= board[j][i] << j
50            # If current masks do not match with the initial ones, the board is not a chessboard
52                return -1
53            # Increment count if the current row/column matches the respective masks
56
57        # Use the helper function to calculate total moves for rows and columns
60
61        # If one of them is -1, no solution exists, otherwise return the sum
62        return -1 if moves_row == -1 or moves_col == -1 else moves_row + moves_col
63``````

Java Solution

``````1class Solution {
2    private int size;
3
4    public int movesToChessboard(int[][] board) {
5        size = board.length; // Size of the chessboard
6        int mask = (1 << size) - 1; // A mask with 'size' ones, for bitwise operations
8
9        // Configure initial row and column masks from the first row and column
10        for (int i = 0; i < size; ++i) {
11            rowMask |= board[0][i] << i;
12            columnMask |= board[i][0] << i;
13        }
14
15        // Masks for opposite color configuration by bitwise XOR with full mask of ones
18
19        int sameRow = 0, sameColumn = 0;
20
21        // Check every row and column to count correct configuration match
22        for (int i = 0; i < size; ++i) {
24            for (int j = 0; j < size; ++j) {
25                currentRowMask |= board[i][j] << j;
26                currentColumnMask |= board[j][i] << j;
27            }
28
29            // If the current row or column does not match either possible configuration, return -1
31                return -1;
32            }
34                return -1;
35            }
36
37            // Count the number of rows and columns that match the first row/column
40        }
41
42        // Calculate the number of swaps required for rows and columns
43        int rowSwaps = calculateSwaps(rowMask, sameRow);
44        int columnSwaps = calculateSwaps(columnMask, sameColumn);
45
46        // If either row or column swaps are invalid, return -1, otherwise return the total swaps
47        return rowSwaps == -1 || columnSwaps == -1 ? -1 : rowSwaps + columnSwaps;
48    }
49
50    // Method that calculates the minimum number of swaps needed based on mask configuration
51    private int calculateSwaps(int mask, int count) {
53
54        // Handle odd board size
55        if (size % 2 == 1) {
56            if (Math.abs(size - onesCount * 2) != 1 || Math.abs(size - count * 2) != 1) {
57                return -1;
58            }
59            if (onesCount == size / 2) {
60                return size / 2 - Integer.bitCount(mask & 0xAAAAAAAA);
61            }
62            return (size / 2 + 1) - Integer.bitCount(mask & 0x55555555);
63        }
64        // Handle even board size
65        else {
66            if (onesCount != size / 2 || count != size / 2) {
67                return -1;
68            }
69            int countZero = size / 2 - Integer.bitCount(mask & 0xAAAAAAAA);
70            int countOne = size / 2 - Integer.bitCount(mask & 0x55555555);
71            return Math.min(countZero, countOne);
72        }
73    }
74}
75``````

C++ Solution

``````1class Solution {
2public:
3    int n;
4
5    // Main function to calculate the minimum number of swaps to convert the board into a valid chessboard
6    int movesToChessboard(vector<vector<int>>& board) {
7        n = board.size(); // size of the board (dimension)
8        int mask = (1 << n) - 1; // bitmask with 'n' 1s
10
11        // Create the bitmask for the first row and column
12        for (int i = 0; i < n; ++i) {
15        }
16
17        // Calculate the bitmasks of flipped rows and columns
20
21        int sameRow = 0, sameCol = 0; // counters for rows and columns matching the first row/col
22
23        // Check each row and column to ensure it is a valid chessboard line and count matches
24        for (int i = 0; i < n; ++i) {
26
27            // Create bitmasks for the current row and column
28            for (int j = 0; j < n; ++j) {
29                curRowMask |= board[i][j] << j;
30                curColMask |= board[j][i] << j;
31            }
32
33            // If current masks are neither identical to the first line masks nor their inverses, the board is invalid
36
37            // Increment the counters for rows and columns that match the first row/col
40        }
41
42        // Calculate minimum moves for rows and columns
43        int movesRow = calculateMoves(rowMask, sameRow);
44        int movesCol = calculateMoves(colMask, sameCol);
45
46        // If one of them is -1, the board cannot be transformed
47        return movesRow == -1 || movesCol == -1 ? -1 : movesRow + movesCol;
48    }
49
50    // Helper function to calculate minimum number of swaps to convert all rows or columns
51    int calculateMoves(int mask, int count) {
52        int ones = __builtin_popcount(mask); // count of 1s in the mask
53        // Handling the case when the board size is odd
54        if (n & 1) {
55            // Check if the number of ones does not differ by 1 and if the count of rows/columns is not half
56            if (abs(n - 2 * ones) != 1 || abs(n - 2 * count) != 1) return -1;
57
58            // Depending on the number of ones, calculate minimum swaps for the odd case
59            if (ones == n / 2) return n / 2 - __builtin_popcount(mask & 0xAAAAAAAA); // for even indexes
60            return (n + 1) / 2 - __builtin_popcount(mask & 0x55555555); // for odd indexes
61        } else {
62            // For even-sized board, check if ones and count are exactly half
63            if (ones != n / 2 || count != n / 2) return -1;
64
65            // Calculate minimum swaps for even case by considering parity of indexes
66            int movesEvenIndexes = n / 2 - __builtin_popcount(mask & 0xAAAAAAAA); // for even indexes
67            int movesOddIndexes = n / 2 - __builtin_popcount(mask & 0x55555555); // for odd indexes
68            return std::min(movesEvenIndexes, movesOddIndexes);
69        }
70    }
71};
72``````

Typescript Solution

``````1// Declare globals for size of the board
2let n: number;
3
4// Function to calculate the minimum number of swaps to convert the board into a valid chessboard
5function movesToChessboard(board: number[][]): number {
6    n = board.length; // size of the board (dimension)
7    const mask: number = (1 << n) - 1; // bitmask with 'n' 1s
9
10    // Create the bitmask for the first row and column
11    for (let i = 0; i < n; ++i) {
14    }
15
16    // Calculate the bitmasks of flipped rows and columns
19
20    let sameRow: number = 0, sameCol: number = 0; // counters for rows and columns matching the first row/col
21
22    // Check each row and column to ensure it is a valid chessboard line and count matches
23    for (let i = 0; i < n; ++i) {
25
26        // Create bitmasks for the current row and column
27        for (let j = 0; j < n; ++j) {
28            curRowMask |= board[i][j] << j;
29            curColMask |= board[j][i] << j;
30        }
31
32        // If current masks are neither identical to the first line masks nor their inverses, the board is invalid
34            return -1;
35        }
36
37        // Increment the counters for rows and columns that match the first row/col
40    }
41
42    // Calculate minimum moves for rows and columns
43    const movesRow: number = calculateMoves(rowMask, sameRow);
44    const movesCol: number = calculateMoves(colMask, sameCol);
45
46    // If one of them is -1, the board cannot be transformed
47    return (movesRow === -1 || movesCol === -1) ? -1 : movesRow + movesCol;
48}
49
50// Helper function to calculate minimum number of swaps to convert all rows or columns
51function calculateMoves(mask: number, count: number): number {
52    const ones: number = countOnes(mask); // count of 1s in the mask
53    // Handling the case when the board size is odd
54    if (n % 2 === 1) {
55        // Check if the number of ones does not differ by 1 and if the count of rows/columns is not half
56        if (Math.abs(n - 2 * ones) !== 1 || Math.abs(n - 2 * count) !== 1) return -1;
57
58        // Depending on the number of ones, calculate minimum swaps for the odd case
59        if (ones === Math.floor(n / 2)) {
60            return Math.floor(n / 2) - countOnes(mask & 0xAAAAAAAA); // for even indexes
61        } else {
62            return (Math.floor(n / 2) + 1) - countOnes(mask & 0x55555555); // for odd indexes
63        }
64    } else {
65        // For even-sized board, check if ones and count are exactly half
66        if (ones !== n / 2 || count !== n / 2) return -1;
67
68        // Calculate minimum swaps for even case by considering the parity of indexes
69        const movesEvenIndexes: number = n / 2 - countOnes(mask & 0xAAAAAAAA); // for even indexes
70        const movesOddIndexes: number = n / 2 - countOnes(mask & 0x55555555); // for odd indexes
71
72        return Math.min(movesEvenIndexes, movesOddIndexes);
73    }
74}
75
76// Utility function to count the number of 1s in the binary representation of the number (mask)
79}
80``````

Time and Space Complexity

The code before presents a function to calculate the number of moves required to rearrange a given `n x n` binary grid (chessboard) into a state where each row and each column has the same number of 1's as 0's.

Time Complexity

The time complexity of this function can be analyzed as follows:

• There is a loop that iterates `n` times to establish the `rowMask` and `colMask`. This loop has a complexity of `O(n)`.
• Another loop iterates `n` times where, for each iteration, there is another `n` iteration loop to create `curRowMask` and `curColMask`, which gives us `O(n^2)`.
• The operations inside the loops such as `|=` and checking membership in a tuple have a constant time complexity `O(1)`.
• The function `f(mask, cnt)` consists of bit count operations and basic arithmetic operations, which all assume a constant time complexity, `O(1)` because the size of an integer in Python is fixed and these operations run in constant time regardless of the size of the integer.
• The function `f(mask, cnt)` is called twice, which also contributes a constant `O(1)` to the time complexity since it does not depend on `n`.

Combining all the parts, we get that the dominant term is from the second loop, making the overall time complexity `O(n^2)`.

Space Complexity

The space complexity can be considered as follows:

• A few integer variables are used (`rowMask`, `colMask`, `revRowMask`, `revColMask`, `sameRow`, `sameCol`), which all contribute `O(1)` complexity.
• The `f(mask, cnt)` function uses a constant amount of additional space.

Thus, the space complexity is constant, `O(1)`. No additional space that depends on the input size `n` is being allocated, as we only use a fixed number of variables.

In conclusion, the function `movesToChessboard` has a time complexity of `O(n^2)` and a space complexity of `O(1)`.

๐
Become an
Algo Monster

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ
โTA ๐จโ๐ซ