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.lengthn == board[i].length2 <= n <= 30board[i][j] is either 0 or 1.Problem Overview: You are given an n x n binary matrix. The task is to transform it into a valid chessboard pattern (alternating 0s and 1s in rows and columns) using the minimum number of row or column swaps. If the transformation is impossible, return -1.
Approach 1: Pattern Matching and Position Swapping (O(n^2) time, O(1) space)
A valid chessboard has exactly two types of rows and two types of columns, and they must be bitwise inverses of each other. Start by comparing every row with the first row and every column with the first column. Any row must either match the first row or be its inverse; otherwise the configuration cannot become a chessboard. After validating this constraint, count how many rows and columns are misplaced relative to the expected alternating pattern. The minimum swaps are determined by comparing the matrix with two possible chessboard patterns (starting with 0 or starting with 1). Implementation often uses bit masks or parity checks to count mismatches efficiently. This approach works directly on the array representation of the matrix and runs in O(n^2) because every cell is inspected once.
Approach 2: Recursive Approach with Memoization (O(n^2) time, O(n^2) space)
This approach treats the board transformation as a recursive state exploration problem. At each step, you attempt swapping rows or columns that violate the chessboard pattern. The recursion evaluates whether the current configuration can reach a valid state with minimal operations. Memoization stores previously computed board states (often serialized as bit patterns) to avoid recomputation. Although recursion introduces overhead, caching ensures the algorithm does not repeatedly explore identical states. This strategy highlights the structural constraints of alternating patterns and demonstrates how bit manipulation can encode rows and columns compactly for memo keys.
Approach 3: Iterative Approach with Tabulation (O(n^2) time, O(n) space)
The tabulation method computes valid row and column placements iteratively. Instead of recursion, it counts the number of 1s in rows and columns and verifies that counts differ by at most one, which is required for alternating patterns. Then it iterates through indices and calculates how many positions violate the expected parity pattern ((i + j) % 2). Using these mismatch counts, the algorithm derives the minimal swaps required for rows and columns separately. This method avoids recursion overhead and keeps memory usage small while still leveraging the structure of alternating grids. It is easier to implement in iterative languages and works well when you want deterministic state progression.
Recommended for interviews: The pattern matching and position swapping approach is the standard solution interviewers expect. It shows you understand the mathematical constraints of chessboard patterns and can derive swap counts using parity checks. Recursive exploration demonstrates reasoning about state transitions, but the optimal solution proves stronger algorithmic insight and runs with minimal space.
This approach involves matching the row and column patterns against a valid chessboard configuration and calculating the minimum number of swaps needed. The idea is to compare the current board's rows and columns to the two possible valid chessboard row and column patterns.
The function movesToChessboard attempts to transform the given board into a chessboard. It determines if the transformation is possible by verifying the row and column patterns. The pattern matching checks if the lines have the correct number of 1s or 0s to resemble a chessboard line pattern. movesToTransform calculates the minimum swaps needed to align each row and column pattern to either of two potential chessboard patterns.
Time Complexity: O(n2) due to examining each cell multiple times for pattern matching.
Space Complexity: O(n) for storing intermediate lists.
Recursive Approach with Memoization:
This approach involves breaking the problem down into smaller subproblems, solving each using recursion, and storing the results of these subproblems to avoid redundant calculations. This is a classic dynamic programming approach that trades time complexity for space complexity by using a cache to remember previously computed results.
Memoization helps in optimizing the recursive calls by saving the results of subproblems, making future calls faster and reducing time complexity significantly.
This Python solution makes use of a dictionary, memo, to store computed Fibonacci numbers. The base cases are n = 0 and n = 1 where the function returns the number itself. For other cases, the result is calculated recursively and stored in the memo dictionary.
Time Complexity: O(n)
Space Complexity: O(n) due to the recursion call stack and memoization dictionary.
Iterative Approach with Tabulation:
This approach uses an iterative method to fill up a table (array), which stores previously computed values of the subproblems (in this case, Fibonacci numbers). Tabulation is another form of dynamic programming where you solve the problem iteratively and build the solution bottom-up.
This approach optimizes space usage by using only an array of size n or even reducing it to constant space by utilizing only the last two computed values.
This JavaScript solution calculates Fibonacci numbers iteratively, keeping only the last two values at any given time (fib1 and fib2), thus optimizing space usage significantly, achieving O(1) space complexity while maintaining O(n) time complexity.
JavaScript
Java
Time Complexity: O(n)
Space Complexity: O(1)
In a valid chessboard, there are exactly two types of "rows".
For example, if one row on the chessboard is "01010011", then any other row can only be "01010011" or "10101100". Columns also satisfy this property.
Additionally, each row and each column has half 0s and half 1s. Suppose the chessboard is n times n:
n = 2 times k, then each row and each column has k 1s and k 0s.n = 2 times k + 1, then each row has k 1s and k + 1 0s, or k + 1 1s and k 0s.Based on the above conclusions, we can determine whether a chessboard is valid. If valid, we can calculate the minimum number of moves required.
If n is even, there are two possible valid chessboards, where the first row is either "010101..." or "101010...". We calculate the minimum number of swaps required for these two possibilities and take the smaller value as the answer.
If n is odd, there is only one possible valid chessboard. If the number of 0s in the first row is greater than the number of 1s, then the first row of the final chessboard must be "01010..."; otherwise, it must be "10101...". We calculate the number of swaps required and use it as the answer.
The time complexity is O(n^2), where n is the size of the chessboard. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Pattern Matching and Position Swapping | Time Complexity: O(n2) due to examining each cell multiple times for pattern matching. |
| Recursive Approach with Memoization | Time Complexity: O(n) |
| Iterative Approach with Tabulation | Time Complexity: O(n) |
| Pattern Observation + State Compression | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Pattern Matching and Position Swapping | O(n^2) | O(1) | Best general solution. Efficiently validates row/column patterns and computes minimal swaps. |
| Recursive Approach with Memoization | O(n^2) | O(n^2) | Useful for understanding state transitions and exploring swap combinations. |
| Iterative Approach with Tabulation | O(n^2) | O(n) | Preferred when avoiding recursion and computing mismatch counts iteratively. |
Transform to Chessboard | Leetcode 782 | Live coding session 🔥🔥🔥 • Coding Decoded • 3,028 views views
Watch 9 more video solutions →Practice Transform to Chessboard with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor