782. Transform to Chessboard

HardBit ManipulationArrayMathMatrix
Leetcode Link

Problem Description

In this problem, we are given an n x n binary grid called board. The board consists only of 0s and 1s. We can make moves to transform this grid into a "chessboard" configuration. A "chessboard" configuration is defined as a board where no 0s are adjacent to other 0s and no 1s are adjacent to other 1s, 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 1s must be the same as the number of 0s 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 0s and 1s 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.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

How many times is a tree node visited in a depth first search?

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 1s 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 0s or 1s (cnt0 and cnt1). For an odd n, the function directly computes the count based on the majority of 1s 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

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.

  1. Row and Column Masks:

    • The rowMask is based on the first row, which would be 010 in binary, reflecting the configuration of 0s and 1s.
    • 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.

Solution Implementation

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
6            ones = mask.bit_count()
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
31        # Initialize masks
32        row_mask = col_mask = 0
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
39        rev_row_mask = mask ^ row_mask
40        rev_col_mask = mask ^ col_mask
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):
46            cur_row_mask = cur_col_mask = 0
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
51            if cur_row_mask not in (row_mask, rev_row_mask) or cur_col_mask not in (col_mask, rev_col_mask):
52                return -1
53            # Increment count if the current row/column matches the respective masks
54            same_row_count += cur_row_mask == row_mask
55            same_col_count += cur_col_mask == col_mask
56      
57        # Use the helper function to calculate total moves for rows and columns
58        moves_row = calculate_moves(row_mask, same_row_count)
59        moves_col = calculate_moves(col_mask, same_col_count)
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
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
7        int rowMask = 0, columnMask = 0;
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
16        int reverseRowMask = mask ^ rowMask;
17        int reverseColumnMask = mask ^ columnMask;
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) {
23            int currentRowMask = 0, currentColumnMask = 0;
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
30            if (currentRowMask != rowMask && currentRowMask != reverseRowMask) {
31                return -1;
32            }
33            if (currentColumnMask != columnMask && currentColumnMask != reverseColumnMask) {
34                return -1;
35            }
36
37            // Count the number of rows and columns that match the first row/column
38            sameRow += currentRowMask == rowMask ? 1 : 0;
39            sameColumn += currentColumnMask == columnMask ? 1 : 0;
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) {
52        int onesCount = Integer.bitCount(mask);
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
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
9        int rowMask = 0, colMask = 0; // initialize row and column bitmasks
10      
11        // Create the bitmask for the first row and column
12        for (int i = 0; i < n; ++i) {
13            rowMask |= board[0][i] << i; // first row bitmask
14            colMask |= board[i][0] << i; // first column bitmask
15        }
16
17        // Calculate the bitmasks of flipped rows and columns
18        int revRowMask = mask ^ rowMask; // reversed row bitmask
19        int revColMask = mask ^ colMask; // reversed column bitmask
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) {
25            int curRowMask = 0, curColMask = 0; // current row and column bitmasks
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
34            if (curRowMask != rowMask && curRowMask != revRowMask) return -1;
35            if (curColMask != colMask && curColMask != revColMask) return -1;
36
37            // Increment the counters for rows and columns that match the first row/col
38            sameRow += curRowMask == rowMask;
39            sameCol += curColMask == colMask;
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
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
8    let rowMask: number = 0, colMask: number = 0; // initialize row and column bitmasks
9  
10    // Create the bitmask for the first row and column
11    for (let i = 0; i < n; ++i) {
12        rowMask |= board[0][i] << i; // first row bitmask
13        colMask |= board[i][0] << i; // first column bitmask
14    }
15
16    // Calculate the bitmasks of flipped rows and columns
17    const revRowMask: number = mask ^ rowMask; // reversed row bitmask
18    const revColMask: number = mask ^ colMask; // reversed column bitmask
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) {
24        let curRowMask: number = 0, curColMask: number = 0; // current row and column bitmasks
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
33        if ((curRowMask !== rowMask && curRowMask !== revRowMask) || (curColMask !== colMask && curColMask !== revColMask)) {
34            return -1;
35        }
36
37        // Increment the counters for rows and columns that match the first row/col
38        sameRow += (curRowMask === rowMask) ? 1 : 0;
39        sameCol += (curColMask === colMask) ? 1 : 0;
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)
77function countOnes(mask: number): number {
78    return mask.toString(2).split('0').join('').length;
79}
80
Not Sure What to Study? Take the 2-min Quiz：

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

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).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

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 👨‍🏫