Make a Square with the Same Color - Solution & Explanation
Problem Statement
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 == 3grid[i].length == 3grid[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.
In C, the solution iterates over all possible 2x2 subgrids within the 3x3 grid. For each subgrid, it counts the number of 'B' and 'W'. If either count is 3 or more, it means at most one cell change can make the subgrid uniform, and it can return true.
Complexity
Time Complexity: O(1) - The operation is constant as it consists of checking a fixed number of 2x2 subgrids.
Space Complexity: O(1) - No additional space is used apart from the input grid.
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.
The Java solution builds on the known fact that for any 2x2 subgrid, if at least three cells are the same, the subgrid becomes uniform with only one change. By forming a string pattern of all cells within the subgrid, it's quick to identify potential transformations to a flat color.
Complexity
Time Complexity: O(1).
Space Complexity: O(1).
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).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Check 2x2 Subgrids Directly | Time Complexity: O(1) - The operation is constant as it consists of checking a fixed number of 2x2 subgrids. |
| Approach 2: Optimized Check by Pattern Recognition | Time Complexity: O(1). |
| Enumeration | — |
Detailed 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 |
Video Solution
3127 Make a Square with the Same Color || Interview Approach ✅ || Brute Force Solution 🔥 • Ayush Rao • 543 views views
Watch 7 more video solutions →Frequently Asked Questions
Is Make a Square with the Same Color easy or hard?
Make a Square with the Same Color Python/Java solution
How to solve Make a Square with the Same Color in O(n)?
What is the best approach for Make a Square with the Same Color?
Is Make a Square with the Same Color asked at Google/Amazon/Meta?
What data structure is used in Make a Square with the Same Color?
What is the time complexity of Make a Square with the Same Color?
Ready to solve this problem?
Practice Make a Square with the Same Color with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor