# Make a Square with the Same Color
**Difficulty:** EASY
[External](https://leetcode.com/problems/make-a-square-with-the-same-color)
Canonical: https://scaleengineer.com/dsa/problems/make-a-square-with-the-same-color
**Patterns:** [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Array, Matrix
---
## Problem
You are given a 2D matrix `grid` of size `3 x 3` consisting only of characters `'B'` and `'W'`. Character `'W'` represents the white color, and character `'B'` represents the black color.

Your task is to change the color of **at most one** cell so that the matrix has a `2 x 2` square where all cells are of the same color.

Return `true` if it is possible to create a `2 x 2` square of the same color, otherwise, return `false`.

**Example 1:**

**Input:** grid = \[\["B","W","B"\],\["B","W","W"\],\["B","W","B"\]\]

**Output:** true

**Explanation:**

It can be done by changing the color of the `grid[0][2]`.

**Example 2:**

**Input:** grid = \[\["B","W","B"\],\["W","B","W"\],\["B","W","B"\]\]

**Output:** false

**Explanation:**

It cannot be done by changing at most one cell.

**Example 3:**

**Input:** grid = \[\["B","W","B"\],\["B","W","W"\],\["B","W","W"\]\]

**Output:** true

**Explanation:**

The `grid` already contains a `2 x 2` square of the same color.

**Constraints:**

* `grid.length == 3`
* `grid[i].length == 3`
* `grid[i][j]` is either `'W'` or `'B'`.

# Approaches
## Brute-Force Simulation by Changing Each Cell
This approach directly simulates the problem statement. It first checks if the grid already contains a monochromatic 2x2 square. If not, it proceeds to try every possible single-cell change. It iterates through all 9 cells of the grid, flips the color of one cell at a time, and then checks if this change results in a monochromatic 2x2 square. If such a change is found, it returns `true`. If all 9 possible changes are tried without success, it returns `false`.
**Time:** O(1) - The grid size is fixed at 3x3. The algorithm performs a constant number of operations (iterating 9 cells, and for each, checking 4 subgrids). The total work is constant regardless of the input values. · **Space:** O(1) - The algorithm uses a constant amount of extra space for loop variables and storing the original character. No data structures that scale with input size are used.
**Pros:** Conceptually straightforward as it directly models the problem's conditions.; Easy to implement and understand for beginners.
**Cons:** Less efficient in terms of constant factors due to redundant computations. Changing one cell only affects at most one 2x2 subgrid, but this approach re-checks all four subgrids after every single change.; Involves modifying the input array, which requires careful handling to restore its state after each check.
### Explanation
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`.

```java
class Solution {
    public boolean canMakeSquare(char[][] grid) {
        // Case 0: No changes needed
        if (hasMonochromaticSquare(grid)) {
            return true;
        }

        // Case 1: One change allowed
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                // Temporarily change the color
                char originalChar = grid[i][j];
                grid[i][j] = (originalChar == 'W') ? 'B' : 'W';

                // Check if a monochromatic square is formed
                if (hasMonochromaticSquare(grid)) {
                    return true;
                }

                // Change it back to restore the grid for the next iteration
                grid[i][j] = originalChar;
            }
        }

        return false;
    }

    private boolean hasMonochromaticSquare(char[][] grid) {
        for (int i = 0; i <= 1; i++) {
            for (int j = 0; j <= 1; j++) {
                // Check the 2x2 square starting at (i, j)
                char c = grid[i][j];
                if (grid[i+1][j] == c && grid[i][j+1] == c && grid[i+1][j+1] == c) {
                    return true;
                }
            }
        }
        return false;
    }
}
```
### Algorithm
*   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`.

## Optimized Direct Subgrid Analysis
This approach is more efficient because it avoids simulation. Instead of changing cells, it directly analyzes each of the four possible 2x2 subgrids. For a 2x2 subgrid to be transformable into a monochromatic square with at most one change, it must either already be monochromatic (0 changes) or have three cells of one color and one of another (1 change). This is equivalent to checking if the count of either 'W' or 'B' is 3 or 4.
**Time:** O(1) - The algorithm iterates a fixed number of times (4 subgrids) and performs a constant number of operations for each. The total runtime is constant and very low. · **Space:** O(1) - Only a few variables are used for counters and loop indices, resulting in constant extra space.
**Pros:** Highly efficient with a minimal number of operations.; More elegant and direct, as it checks the necessary condition without simulating changes.; Does not modify the input grid, avoiding potential side effects and the need to restore state.
**Cons:** For this specific problem with a tiny, fixed-size grid, the performance difference from the brute-force approach is negligible in practice, though it is theoretically superior.
### Explanation
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`.

```java
class Solution {
    public boolean canMakeSquare(char[][] grid) {
        // Iterate through the top-left corners of all four 2x2 subgrids.
        for (int i = 0; i <= 1; i++) {
            for (int j = 0; j <= 1; j++) {
                int whiteCount = 0;
                int blackCount = 0;

                // Count the colors in the 2x2 subgrid starting at (i, j).
                if (grid[i][j] == 'W') whiteCount++; else blackCount++;
                if (grid[i][j + 1] == 'W') whiteCount++; else blackCount++;
                if (grid[i + 1][j] == 'W') whiteCount++; else blackCount++;
                if (grid[i + 1][j + 1] == 'W') whiteCount++; else blackCount++;

                // If there are 3 or 4 cells of the same color, we can make a square.
                if (whiteCount >= 3 || blackCount >= 3) {
                    return true;
                }
            }
        }

        return false;
    }
}
```
### Algorithm
*   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`.

# Solutions
### Java

```java
class Solution {
public
  boolean canMakeSquare(char[][] grid) {
    final int[] dirs = {0, 0, 1, 1, 0};
    for (int i = 0; i < 2; ++i) {
      for (int j = 0; j < 2; ++j) {
        int cnt1 = 0, cnt2 = 0;
        for (int k = 0; k < 4; ++k) {
          int x = i + dirs[k], y = j + dirs[k + 1];
          cnt1 += grid[x][y] == 'W' ? 1 : 0;
          cnt2 += grid[x][y] == 'B' ? 1 : 0;
        }
        if (cnt1 != cnt2) {
          return true;
        }
      }
    }
    return false;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool canMakeSquare(vector<vector<char>> &grid) {
    int dirs[5] = {0, 0, 1, 1, 0};
    for (int i = 0; i < 2; ++i) {
      for (int j = 0; j < 2; ++j) {
        int cnt1 = 0, cnt2 = 0;
        for (int k = 0; k < 4; ++k) {
          int x = i + dirs[k], y = j + dirs[k + 1];
          cnt1 += grid[x][y] == 'W';
          cnt2 += grid[x][y] == 'B';
        }
        if (cnt1 != cnt2) {
          return true;
        }
      }
    }
    return false;
  }
};

```

### Python

```python
class Solution:
    def canMakeSquare(self, grid: List[List[str]]) -> bool: for i in range(0, 2): for j in range(0, 2): cnt1 = cnt2 = 0 for a, b in pairwise((0, 0, 1, 1, 0)): x, y = i + a, j + b cnt1 += grid[x][y] == "W" cnt2 += grid[x][y] == "B" if cnt1 != cnt2: return True return False

```