Make a Square with the Same Color

• Define a helper function hasMonochromaticSquare(grid) that checks all four 2x2 subgrids for being monochromatic (all four cells having the same color).
• First, call hasMonochromaticSquare on the original grid. If it returns true, it means a valid square exists with zero changes, so we return true.
• If not, iterate through each cell (i, j) of the 3x3 grid.
• For each cell, temporarily flip its color (e.g., 'W' to 'B').
• Call hasMonochromaticSquare on the modified grid. If it returns true, it means we found a way to make a square with one change, so we return true.
• Crucially, revert the color flip to restore the grid's original state for the next iteration.
• If the loops complete without finding any solution, return false.

The core idea is to exhaustively check all possibilities allowed by the problem: making zero changes or making exactly one change.

First, we handle the 'zero changes' case. A helper function, hasMonochromaticSquare, is created to scan the four 2x2 subgrids of the input grid. If it finds a subgrid where all four cells are the same color, it returns true.

If the grid doesn't initially have a valid square, we explore the 'one change' case. We use nested loops to iterate through every cell (i, j) of the 3x3 grid. In each iteration, we perform the following steps:

• Flip the color of the cell grid[i][j]. For instance, 'W' becomes 'B' and 'B' becomes 'W'.
• Call the hasMonochromaticSquare helper function on the modified grid.
• If the helper function returns true, it means we've successfully formed a monochromatic square by changing just one cell, so we can immediately return true from the main function.
• It's crucial to revert the change made in step 1 before proceeding to the next iteration. This ensures that each simulation starts from the original grid state, modified by only a single flip.

If the loops complete without finding any successful single change, it implies that it's impossible to achieve the goal, and the function returns false.

1class Solution {2    public boolean canMakeSquare(char[][] grid) {3        // Case 0: No changes needed4        if (hasMonochromaticSquare(grid)) {5            return true;6        }7 8        // Case 1: One change allowed9        for (int i = 0; i < 3; i++) {10            for (int j = 0; j < 3; j++) {11                // Temporarily change the color12                char originalChar = grid[i][j];13                grid[i][j] = (originalChar == 'W') ? 'B' : 'W';14 15                // Check if a monochromatic square is formed16                if (hasMonochromaticSquare(grid)) {17                    return true;18                }19 20                // Change it back to restore the grid for the next iteration21                grid[i][j] = originalChar;22            }23        }24 25        return false;26    }27 28    private boolean hasMonochromaticSquare(char[][] grid) {29        for (int i = 0; i <= 1; i++) {30            for (int j = 0; j <= 1; j++) {31                // Check the 2x2 square starting at (i, j)32                char c = grid[i][j];33                if (grid[i+1][j] == c && grid[i][j+1] == c && grid[i+1][j+1] == c) {34                    return true;35                }36            }37        }38        return false;39    }40}

• Iterate through the potential top-left corners (i, j) of a 2x2 subgrid, where i and j range from 0 to 1.
• For each subgrid, initialize whiteCount and blackCount to 0.
• Count the number of 'W' and 'B' cells in the 2x2 subgrid defined by the top-left corner (i, j).
• Check if whiteCount >= 3 or blackCount >= 3.
• If the condition is met, it means the subgrid can be made monochromatic with at most one change, so return true.
• If the loops complete without finding such a subgrid, return false.

The logic hinges on a simple observation: a 2x2 square can be made monochromatic with at most one change if and only if it contains at least three cells of the same color.

• If it has four cells of the same color, 0 changes are needed.
• If it has three cells of one color and one of another, 1 change is needed.
• If it has two cells of each color, 2 changes are needed, which is not allowed.

Based on this, the algorithm iterates through the four possible 2x2 subgrids in the 3x3 matrix. The top-left corners of these subgrids are at indices (0,0), (0,1), (1,0), and (1,1).

For each subgrid, we do the following:

• Initialize counters for white ('W') and black ('B') cells to zero.
• Iterate through the four cells of the current 2x2 subgrid.
• Increment the respective counter (whiteCount or blackCount) for each cell.
• After counting, check if whiteCount >= 3 or blackCount >= 3.
• If this condition is true for any subgrid, it means we've found a square that can be made monochromatic. We can immediately return true.

If we check all four subgrids and none of them meet the condition, it's impossible to create the desired square, so we return false.

1class Solution {2    public boolean canMakeSquare(char[][] grid) {3        // Iterate through the top-left corners of all four 2x2 subgrids.4        for (int i = 0; i <= 1; i++) {5            for (int j = 0; j <= 1; j++) {6                int whiteCount = 0;7                int blackCount = 0;8 9                // Count the colors in the 2x2 subgrid starting at (i, j).10                if (grid[i][j] == 'W') whiteCount++; else blackCount++;11                if (grid[i][j + 1] == 'W') whiteCount++; else blackCount++;12                if (grid[i + 1][j] == 'W') whiteCount++; else blackCount++;13                if (grid[i + 1][j + 1] == 'W') whiteCount++; else blackCount++;14 15                // If there are 3 or 4 cells of the same color, we can make a square.16                if (whiteCount >= 3 || blackCount >= 3) {17                    return true;18                }19            }20        }21 22        return false;23    }24}