#3127

Easy

LeetCode Problem Workspace

Make a Square with the Same Color

Determine if a 3x3 grid can form a 2x2 square of the same color by changing at most one cell efficiently.

Problem Statement

You are given a 3x3 matrix called grid consisting only of characters 'B' for black and 'W' for white. Each cell represents a color in the grid.

Your task is to determine if you can make a 2x2 square where all cells have the same color by changing the color of at most one cell. Return true if possible, otherwise return false.

Examples

Example 1

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

Output: true

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

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

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

Solution Approach

Brute Force Check of All 2x2 Squares

Iterate through all four possible 2x2 squares within the 3x3 grid. For each square, count the number of cells that are different from the top-left cell of that square. If at most one cell differs, you can change it to match the others and form a uniform square.

Early Exit Optimization

As soon as you find a 2x2 square with zero or one differing cell, return true immediately. This reduces unnecessary computation for remaining squares once a solution is found.

Handle Impossible Cases

If all 2x2 squares have two or more cells with different colors, return false. This handles the failure mode where even changing one cell cannot create a uniform 2x2 square.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(1) because the grid is always 3x3 and only four 2x2 squares exist. Space complexity is O(1) since no extra data structures proportional to input size are used.

What Interviewers Usually Probe

Checks your ability to enumerate submatrices efficiently.
Tests pattern recognition in small fixed-size matrices.
Looks for handling edge cases where a single change is insufficient.

Common Pitfalls or Variants

Common pitfalls

Forgetting to check all four 2x2 submatrices in the 3x3 grid.
Failing to count differing cells correctly within each square.
Returning true when two or more cells differ in a 2x2 square.

Follow-up variants

Consider larger NxN grids where you want to form KxK squares of the same color.
Allow changing more than one cell and check minimal changes required to form a uniform square.
Modify the problem to count how many distinct 2x2 uniform squares can be formed after at most one change.

FAQ

What is the fastest way to check a 3x3 grid for a 2x2 uniform square?

Scan all four 2x2 submatrices and count cells differing from the top-left cell, returning true if at most one differs.

Can this problem be extended to larger grids?

Yes, you can generalize to NxN grids, but you must enumerate all possible KxK submatrices for a solution.

Does changing a cell outside of a 2x2 square help?

No, only cells within a 2x2 square can contribute to forming a uniform square for this problem.

What is the main pattern in Make a Square with the Same Color?

It is an Array plus Matrix pattern focusing on checking small submatrices for color uniformity after at most one change.

How do I handle grids where no 2x2 square can be uniform with one change?

Recognize the failure mode by counting differing cells in all 2x2 squares; if each has two or more differences, return false.

terminal

Solution

Solution 1: Enumeration

We can enumerate each $2 \times 2$ square, count the number of black and white cells. If the counts are not equal, then we can construct a square of the same color, and return `true`.

1

2

3

4

5

6

7

8

9

10

11

12

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

Continue Practicing

#3197 find the minimum area to cover all ones ii #3044 most frequent prime #3256 maximum value sum by placing three rooks i