Practice/Amazon/Leetcode 782. Transform to Chessboard

Leetcode 782. Transform to Chessboard

CodingMust

Problem

You are given an n × n binary grid containing only 0s and 1s. Your task is to determine if you can transform this grid into a valid chessboard pattern by swapping entire rows or entire columns (you can perform any number of swaps). A valid chessboard pattern alternates between 0 and 1 in both horizontal and vertical directions.

If transformation is possible, return the minimum number of swaps required. If it's impossible to create a chessboard pattern, return -1.

For example, these are valid chessboard patterns:

• [[0,1],[1,0]]
• [[1,0],[0,1]]
• [[0,1,0],[1,0,1],[0,1,0]]

Requirements

1. Determine if the given board can be transformed into a chessboard pattern
2. If possible, calculate the minimum number of row and column swaps needed
3. Return the total minimum swaps, or -1 if transformation is impossible
4. A valid chessboard must alternate values in every row and column

Constraints

• n == board.length
• n == board[i].length
• 2 ≤ n ≤ 30
• board[i][j] is either 0 or 1
• Time complexity should be O(n²) or better
• Space complexity should be O(n) or better

Examples

Example 1:

` Input: board = [[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]] Output: 2 Explanation: One way to transform the board is:

• Swap rows 0 and 1 to get [[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]]
• Then swap columns 1 and 2 to achieve a chessboard pattern Total swaps = 2 `

Example 2:

Input: board = [[0,1],[1,0]] Output: 0 Explanation: The board is already a valid chessboard pattern

Example 3:

Input: board = [[1,0],[1,0]] Output: -1 Explanation: No matter how we swap rows or columns, we cannot create a chessboard pattern