3127. Make a Square with the Same Color Solution

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

Approach overview

Problem Overview: You get a 3 x 3 grid containing characters 'B' and 'W'. The goal is to determine whether any 2 x 2 subgrid can be made entirely one color after changing at most one cell.

The key observation: a 2 x 2 square has four cells. If at least three cells already share the same color, flipping the remaining one makes the entire square uniform.

Approach 1: Check 2x2 Subgrids Directly (Enumeration) (Time: O(mn), Space: O(1))

Iterate over every possible 2 x 2 subgrid in the matrix. For each position (i, j), examine the four cells (i,j), (i+1,j), (i,j+1), and (i+1,j+1). Count how many are 'B' and how many are 'W'. If either count is at least 3, a single change can make all four cells identical, so the answer is true. If none of the subgrids satisfy this condition, return false. Although the grid size is fixed at 3x3, the algorithm generalizes to any matrix with complexity O(mn) where m and n are grid dimensions. This approach relies on simple iteration over a matrix and basic counting.

Approach 2: Optimized Check by Pattern Recognition (Time: O(mn), Space: O(1))

Instead of counting both colors explicitly, treat the condition as a pattern check. For each 2 x 2 region, compute the number of cells that match the top-left cell's color. If three or four cells match, the square can already be uniform or requires one change. Otherwise, check the opposite color count implicitly. This slightly reduces branching and keeps the logic compact. The algorithm still scans each possible subgrid once, so the complexity remains O(mn) time and O(1) space. This method demonstrates practical enumeration over small patterns in a grid and fits well with problems involving small array structures.

Recommended for interviews: The direct enumeration approach. Interviewers expect you to notice the 2x2 constraint and check all subgrids with a simple count. It shows you can translate a grid condition into deterministic iteration. Pattern recognition is slightly cleaner but relies on the same insight: any 2x2 square with at least three matching colors can be fixed with one change.

Approach 1: Approach 1: Check 2x2 Subgrids Directly

This approach involves iterating over all possible 2x2 subgrids in the 3x3 matrix and checking if any such subgrid is either already uniform or can be made uniform by changing one cell.

C++

#include <vector>
using namespace std;

bool isSquarePossible(vector<vector<char>>& grid) {
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            int bCount = 0, wCount = 0;
            for (int x = 0; x < 2; ++x) {
                for (int y = 0; y < 2; ++y) {
                    if (grid[i + x][j + y] == 'B') bCount++;
                    else wCount++;
                }
            }
            if (bCount >= 3 || wCount >= 3) {
                return true;
            }
        }
    }
    return false;
}

#include <stdbool.h>

bool isSquarePossible(char grid[3][3]) {
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            int blackCount = 0, whiteCount = 0;
            for (int x = 0; x < 2; x++) {
                for (int y = 0; y < 2; y++) {
                    if (grid[i + x][j + y] == 'B') blackCount++;
                    else whiteCount++;
                }
            }
            if (blackCount >= 3 || whiteCount >= 3) return true;
        }
    }
    return false;
}

The C++ solution adopts a similar approach as the C solution. It uses vectors and iterates through every possible 2x2 subgrid. By counting occurrences of 'B' and 'W', the solution checks if any subgrid can be transformed into a uniform color by changing only one cell.

Complexity

Time Complexity: O(1).
Space Complexity: O(1).

Try this approach in the editor

Approach 2: Approach 2: Optimized Check by Pattern Recognition

This approach recognizes specific patterns within the 2x2 subgrid that can benefit from altering a single cell to achieve uniformity.

Python

def isSquarePossible(grid):
    for i in range(2):
        for j in range(2):
            pattern = [grid[i][j], grid[i][j+1], grid[i+1][j], grid[i+1][j+1]]
            if pattern.count('B') >= 3 or pattern.count('W') >= 3:
                return True
    return False

Java

public class Solution {
    public boolean isSquarePossible(char[][] grid) {
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                String pattern = "" + grid[i][j] + grid[i][j+1] + grid[i+1][j] + grid[i+1][j+1];
                if (pattern.equals("BBB") || pattern.equals("WWW")) {
                    return true;
                }
            }
        }
        return false;
    }
}

In Python, the strategy checks each 2x2 subgrid using a list structure and the count method to determine how many 'B' or 'W' are present. If the count of either color is 3 or greater, one change can unify the color of the square, thus returning true.

Complexity

Time Complexity: O(1).
Space Complexity: O(1).

Try this approach in the editor

Approach 3: 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.

Otherwise, return false after the traversal.

The time complexity is O(1), and the space complexity is O(1).

TypeScript

function canMakeSquare(grid: string[][]): boolean {
    const dirs: number[] = [0, 0, 1, 1, 0];
    for (let i = 0; i < 2; ++i) {
        for (let j = 0; j < 2; ++j) {
            let [cnt1, cnt2] = [0, 0];
            for (let k = 0; k < 4; ++k) {
                const [x, y] = [i + dirs[k], j + dirs[k + 1]];
                if (grid[x][y] === 'W') {
                    ++cnt1;
                } else {
                    ++cnt2;
                }
            }
            if (cnt1 !== cnt2) {
                return true;
            }
        }
    }
    return false;
}

func canMakeSquare(grid [][]byte) bool {
	dirs := [5]int{0, 0, 1, 1, 0}
	for i := 0; i < 2; i++ {
		for j := 0; j < 2; j++ {
			cnt1, cnt2 := 0, 0
			for k := 0; k < 4; k++ {
				x, y := i+dirs[k], j+dirs[k+1]
				if grid[x][y] == 'W' {
					cnt1++
				} else {
					cnt2++
				}
			}
			if cnt1 != cnt2 {
				return true
			}
		}
	}
	return false
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Check 2x2 Subgrids Directly	Time Complexity: O(1). Space Complexity: O(1).
Approach 2: Optimized Check by Pattern Recognition	Time Complexity: O(1). Space Complexity: O(1).
Enumeration	–

Complexity analysis

Approach	Time	Space	When to Use
Check 2x2 Subgrids Directly	O(mn)	O(1)	General solution for any grid size when verifying small subgrid patterns
Optimized Pattern Recognition	O(mn)	O(1)	Cleaner implementation when reducing repeated color counting

Frequently asked questions

Is Make a Square with the Same Color easy or hard?

LeetCode classifies this problem as Easy with an acceptance rate around 53%. The challenge mainly tests basic matrix traversal and recognizing that a 2x2 square becomes uniform if three cells already share the same color.

Make a Square with the Same Color Python/Java solution

A typical Python or Java solution iterates through the grid indices and checks every 2x2 block. For each block, count how many cells are 'B' or 'W'. If either count is at least three, return true immediately; otherwise continue scanning until all subgrids are checked.

How to solve Make a Square with the Same Color in O(n)?

Treat the grid as a matrix and scan each 2x2 subgrid while counting how many cells share the same color. If three or more cells match, one flip makes the entire square uniform. Because each cell participates in a constant number of checks, the algorithm effectively runs in linear time relative to the grid size, O(mn).

What is the best approach for Make a Square with the Same Color?

The most practical approach is enumerating every 2x2 subgrid and counting the number of 'B' and 'W' cells. If either color appears at least three times, a single modification can make the entire square the same color. This approach runs in O(mn) time and O(1) space and is straightforward to implement.

Is Make a Square with the Same Color asked at Google/Amazon/Meta?

This problem is categorized as an easy grid enumeration question similar to screening tasks used by large companies. Variations of matrix pattern checks and small subgrid validation frequently appear in interviews at companies like Amazon and Google for early technical rounds.

What data structure is used in Make a Square with the Same Color?

The problem primarily uses a 2D array or matrix to represent the grid. The algorithm relies on simple iteration and counting within small 2x2 regions, so no advanced data structures are required.

What is the time complexity of Make a Square with the Same Color?

The time complexity is O(mn) where m and n are the grid dimensions, because each possible 2x2 subgrid is checked once. Since the problem uses a fixed 3x3 grid on LeetCode, the actual runtime is constant. Space complexity is O(1) because only a few counters are used.

Make a Square with the Same Color solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Check 2x2 Subgrids Directly

Approach 2: Approach 2: Optimized Check by Pattern Recognition

Approach 3: Enumeration

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Make a Square with the Same Color solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Check 2x2 Subgrids Directly

Approach 2: Approach 2: Optimized Check by Pattern Recognition

Approach 3: Enumeration

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems