Watch 10 video solutions for Make a Square with the Same Color, a easy level problem involving Array, Matrix, Enumeration. This walkthrough by Ayush Rao has 540 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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'.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 | 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 |