LeetCode 3127 - Make a Square with the Same Color

This problem gives us a fixed 3 x 3 grid containing only two possible characters, 'B' for black and 'W' for white. We are allowed to change the color of at most one cell.

leetcodeeasyarraymatrixenumeration

LeetCode Problem 3127

Difficulty: 🟢 Easy
Topics: Array, Matrix, Enumeration

Solution

Problem Understanding

This problem gives us a fixed 3 x 3 grid containing only two possible characters, 'B' for black and 'W' for white. We are allowed to change the color of at most one cell. The goal is to determine whether, after performing zero or one modification, the grid can contain at least one 2 x 2 subgrid where all four cells have the same color.

A 3 x 3 matrix contains exactly four possible 2 x 2 subgrids:

  • Top-left square
  • Top-right square
  • Bottom-left square
  • Bottom-right square

For any one of these squares, we need all four cells to become identical. Since we may modify at most one cell, a square is valid if:

  • All four cells already match, or
  • Exactly one cell differs from the other three

In other words, a 2 x 2 square is achievable if it contains at least three cells of the same color.

The input size is extremely small. The matrix is always 3 x 3, which means the total number of possible subgrids is constant. This tells us that efficiency is not a concern here, and we can directly inspect every possible square without worrying about scalability.

An important edge case is when the grid already contains a monochromatic 2 x 2 square. In that situation, we do not need to make any change. Another important case is when every 2 x 2 square contains exactly two black and two white cells. In that configuration, changing a single cell can never make all four equal, because at least two cells would need modification.

Approaches

Brute Force Approach

A straightforward solution is to try every possible single-cell modification. For each cell, we can:

  1. Leave it unchanged
  2. Flip 'B' to 'W'
  3. Flip 'W' to 'B'

After each attempt, we scan all four 2 x 2 subgrids and check whether any square contains four identical colors.

This approach is guaranteed to work because it explicitly simulates every allowed operation. Since the grid is tiny, even this exhaustive search runs quickly in practice.

However, the brute-force method performs unnecessary work. We do not actually need to simulate modifications. Instead, we can directly reason about whether a square can become monochromatic using at most one change.

Optimal Approach

The key observation is that a 2 x 2 square can be made uniform with at most one modification if and only if at least three of its cells already share the same color.

For each 2 x 2 square:

  • Count how many cells are black
  • Count how many cells are white

If either count is at least 3, then we can make all four cells identical by changing at most one cell.

This removes the need for simulation entirely. We simply inspect each square once and return true immediately if any square satisfies the condition.

Because there are only four possible 2 x 2 squares, the algorithm is extremely small and efficient.

Approach Time Complexity Space Complexity Notes
Brute Force O(1) O(1) Tries every possible cell modification explicitly
Optimal O(1) O(1) Checks whether any 2 x 2 square already has at least three matching cells

Algorithm Walkthrough

  1. Iterate through every possible 2 x 2 subgrid.

Since the matrix size is fixed at 3 x 3, the top-left corner of a 2 x 2 square can only be:

  • (0,0)
  • (0,1)
  • (1,0)
  • (1,1)
  1. Extract the four cells belonging to the current square.

For a square starting at (r,c), the four cells are:

  • grid[r][c]
  • grid[r][c+1]
  • grid[r+1][c]
  • grid[r+1][c+1]
  1. Count how many cells are black.

Since there are only two colors, counting black cells is enough. The number of white cells is simply 4 - black_count. 4. Check whether the square can become monochromatic.

If:

  • black_count >= 3, or
  • white_count >= 3

then at most one modification is needed to make all four cells equal. 5. Return true immediately if such a square exists.

We only need one valid square anywhere in the grid. 6. If all four squares fail the condition, return false.

Why it works

A 2 x 2 square contains exactly four cells. To make all four equal using at most one modification, at least three cells must already match. If only two cells match, then at least two modifications would be required. Therefore, checking whether any square contains at least three identical cells is both necessary and sufficient.

Python Solution

from typing import List

class Solution:
    def canMakeSquare(self, grid: List[List[str]]) -> bool:
        for row in range(2):
            for col in range(2):
                cells = [
                    grid[row][col],
                    grid[row][col + 1],
                    grid[row + 1][col],
                    grid[row + 1][col + 1]
                ]

                black_count = cells.count('B')
                white_count = 4 - black_count

                if black_count >= 3 or white_count >= 3:
                    return True

        return False

The implementation directly follows the algorithm described earlier.

The outer two loops iterate through the four possible 2 x 2 subgrids. For each position, we collect the four cells into a temporary list called cells.

Next, we count how many black cells appear using cells.count('B'). Since every cell is either black or white, the white count can be computed as 4 - black_count.

The critical condition checks whether either color appears at least three times. If so, we immediately return True because one modification is sufficient.

If none of the four subgrids satisfy the condition, the function returns False.

Go Solution

func canMakeSquare(grid [][]byte) bool {
    for row := 0; row < 2; row++ {
        for col := 0; col < 2; col++ {
            blackCount := 0

            if grid[row][col] == 'B' {
                blackCount++
            }
            if grid[row][col+1] == 'B' {
                blackCount++
            }
            if grid[row+1][col] == 'B' {
                blackCount++
            }
            if grid[row+1][col+1] == 'B' {
                blackCount++
            }

            whiteCount := 4 - blackCount

            if blackCount >= 3 || whiteCount >= 3 {
                return true
            }
        }
    }

    return false
}

The Go implementation mirrors the Python solution closely. Since Go does not provide a built-in list counting method like Python's count, we manually increment blackCount while inspecting the four cells.

The grid uses [][]byte instead of strings because the LeetCode Go stub represents characters as bytes.

No additional memory structures are required, so the implementation remains constant-space.

Worked Examples

Example 1

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

We examine each 2 x 2 square.

Square Position Cells Black Count White Count Valid
Top-left B W B W 2 2 No
Top-right W B W W 1 3 Yes

The top-right square already contains three white cells. By changing the remaining black cell to white, we obtain a uniform 2 x 2 square.

The algorithm returns true.

Example 2

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

Checking all four squares:

Square Position Cells Black Count White Count Valid
Top-left B W W B 2 2 No
Top-right W B B W 2 2 No
Bottom-left W B B W 2 2 No
Bottom-right B W W B 2 2 No

Every square contains exactly two black and two white cells. Any monochromatic square would require changing two cells, which exceeds the allowed limit.

The algorithm returns false.

Example 3

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

Checking the squares:

Square Position Cells Black Count White Count Valid
Top-left B W B W 2 2 No
Top-right W B W W 1 3 Yes

The top-right square already contains three white cells. In fact, the bottom-right square is already entirely white.

The algorithm returns true.

Complexity Analysis

Measure Complexity Explanation
Time O(1) The grid size is fixed at 3 x 3, so only four subgrids are checked
Space O(1) Only a few variables are used

Although the algorithm uses nested loops, the matrix dimensions are constant and never grow with input size. Therefore, both time and space usage remain constant.

Test Cases

from typing import List

class Solution:
    def canMakeSquare(self, grid: List[List[str]]) -> bool:
        for row in range(2):
            for col in range(2):
                cells = [
                    grid[row][col],
                    grid[row][col + 1],
                    grid[row + 1][col],
                    grid[row + 1][col + 1]
                ]

                black_count = cells.count('B')
                white_count = 4 - black_count

                if black_count >= 3 or white_count >= 3:
                    return True

        return False

solution = Solution()

assert solution.canMakeSquare([
    ["B", "W", "B"],
    ["B", "W", "W"],
    ["B", "W", "B"]
]) is True  # Example 1

assert solution.canMakeSquare([
    ["B", "W", "B"],
    ["W", "B", "W"],
    ["B", "W", "B"]
]) is False  # Example 2

assert solution.canMakeSquare([
    ["B", "W", "B"],
    ["B", "W", "W"],
    ["B", "W", "W"]
]) is True  # Example 3

assert solution.canMakeSquare([
    ["B", "B", "B"],
    ["B", "B", "B"],
    ["B", "B", "B"]
]) is True  # Entire grid already same color

assert solution.canMakeSquare([
    ["W", "W", "W"],
    ["W", "B", "W"],
    ["W", "W", "W"]
]) is True  # One change creates multiple valid squares

assert solution.canMakeSquare([
    ["B", "W", "B"],
    ["W", "B", "W"],
    ["W", "B", "W"]
]) is True  # Bottom-left square has three whites

assert solution.canMakeSquare([
    ["B", "W", "W"],
    ["W", "B", "B"],
    ["B", "W", "W"]
]) is False  # No square has three matching cells
Test Why
Example 1 Validates one-change conversion
Example 2 Validates impossible configuration
Example 3 Validates already-valid square
All black grid Confirms zero modifications needed
Mostly white grid Tests multiple possible valid squares
Three matching whites Verifies threshold condition
Balanced squares Ensures two-two splits return false

Edge Cases

Grid Already Contains a Valid Square

One important edge case occurs when a 2 x 2 square already consists entirely of one color. A careless implementation might incorrectly assume exactly one modification must occur. The problem allows changing at most one cell, which includes zero changes. The implementation handles this naturally because a square with four matching cells satisfies the condition count >= 3.

Every Square Has Two Black and Two White Cells

This configuration is the only truly impossible scenario. When every 2 x 2 square contains exactly two black and two white cells, no single modification can make all four cells equal. A naive implementation might incorrectly assume any square can always be fixed with one change. The algorithm correctly rejects these cases because neither color count reaches three.

Multiple Valid Squares

Another subtle case happens when several 2 x 2 squares satisfy the condition simultaneously. The algorithm must stop as soon as one valid square is found. The implementation immediately returns True upon discovering the first qualifying square, which avoids unnecessary work while still remaining correct.