LeetCode 3127: Make a Square with the Same Color (Check All 2x2 Windows)
LeetCode 3127MatrixCountingToday we solve LeetCode 3127 - Make a Square with the Same Color.
Source: https://leetcode.com/problems/make-a-square-with-the-same-color/
English
Problem Summary
Given a 3 x 3 grid of 'B' and 'W', determine whether we can make at least one 2 x 2 square have the same color by changing at most one cell.
Key Insight
In any 2 x 2 block, if one color appears at least 3 times, then with at most one change that block can become all same color. So we only need to test each 2 x 2 block and check whether countB != 2.
Brute Force and Limitations
Brute force over all one-cell edits is possible, but unnecessary. Because the grid is fixed 3 x 3, directly checking the four 2 x 2 blocks is cleaner and constant time.
Optimal Algorithm Steps
1) Enumerate top-left corners (i, j) of each 2 x 2 block, where i, j in {0,1}.
2) Count black cells in that block.
3) If black count is not exactly 2, return true immediately.
4) If all four blocks have exactly two black cells, return false.
Complexity Analysis
Time: O(1), because we inspect only 4 blocks with 4 cells each.
Space: O(1).
Common Pitfalls
- Forgetting there are exactly four 2 x 2 windows in a 3 x 3 grid.
- Using wrong condition, the correct quick check is countB != 2.
- Overcomplicating with simulation of all edits.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public boolean canMakeSquare(char[][] grid) {
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
int black = 0;
if (grid[i][j] == 'B') black++;
if (grid[i + 1][j] == 'B') black++;
if (grid[i][j + 1] == 'B') black++;
if (grid[i + 1][j + 1] == 'B') black++;
if (black != 2) return true;
}
}
return false;
}
}func canMakeSquare(grid [][]byte) bool {
for i := 0; i < 2; i++ {
for j := 0; j < 2; j++ {
black := 0
if grid[i][j] == 'B' {
black++
}
if grid[i+1][j] == 'B' {
black++
}
if grid[i][j+1] == 'B' {
black++
}
if grid[i+1][j+1] == 'B' {
black++
}
if black != 2 {
return true
}
}
}
return false
}class Solution {
public:
bool canMakeSquare(vector<vector<char>>& grid) {
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
int black = 0;
if (grid[i][j] == 'B') ++black;
if (grid[i + 1][j] == 'B') ++black;
if (grid[i][j + 1] == 'B') ++black;
if (grid[i + 1][j + 1] == 'B') ++black;
if (black != 2) return true;
}
}
return false;
}
};class Solution:
def canMakeSquare(self, grid: list[list[str]]) -> bool:
for i in range(2):
for j in range(2):
black = 0
black += grid[i][j] == 'B'
black += grid[i + 1][j] == 'B'
black += grid[i][j + 1] == 'B'
black += grid[i + 1][j + 1] == 'B'
if black != 2:
return True
return Falsevar canMakeSquare = function(grid) {
for (let i = 0; i < 2; i++) {
for (let j = 0; j < 2; j++) {
let black = 0;
if (grid[i][j] === 'B') black++;
if (grid[i + 1][j] === 'B') black++;
if (grid[i][j + 1] === 'B') black++;
if (grid[i + 1][j + 1] === 'B') black++;
if (black !== 2) return true;
}
}
return false;
};中文
题目概述
给定一个只包含 'B' 和 'W' 的 3 x 3 网格，判断是否可以通过最多修改一个格子，使得某个 2 x 2 子方块四个格子颜色相同。
核心思路
对于任意 2 x 2 子方块，只要黑色数量至少为 3 或至多为 1，就可以通过最多一次修改变成同色。因此只需检查黑色数是否满足 black != 2。
暴力解法与不足
可以枚举修改哪个格子、改成什么颜色，但这会让思路变复杂。由于输入固定是 3 x 3，直接检查四个 2 x 2 子块更直接。
最优算法步骤
1）枚举四个 2 x 2 子块的左上角坐标。
2）统计该子块中黑色格子的数量。
3）若 black != 2，立刻返回 true。
4）四个子块都检查完仍不满足，则返回 false。
复杂度分析
时间复杂度：O(1)（固定检查 4 个子块，每个 4 个格子）。
空间复杂度：O(1)。
常见陷阱
- 忽略了总共只有 4 个 2 x 2 子块。
- 条件写反，正确判断是 black != 2。
- 过度设计成完整模拟所有修改。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public boolean canMakeSquare(char[][] grid) {
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
int black = 0;
if (grid[i][j] == 'B') black++;
if (grid[i + 1][j] == 'B') black++;
if (grid[i][j + 1] == 'B') black++;
if (grid[i + 1][j + 1] == 'B') black++;
if (black != 2) return true;
}
}
return false;
}
}func canMakeSquare(grid [][]byte) bool {
for i := 0; i < 2; i++ {
for j := 0; j < 2; j++ {
black := 0
if grid[i][j] == 'B' {
black++
}
if grid[i+1][j] == 'B' {
black++
}
if grid[i][j+1] == 'B' {
black++
}
if grid[i+1][j+1] == 'B' {
black++
}
if black != 2 {
return true
}
}
}
return false
}class Solution {
public:
bool canMakeSquare(vector<vector<char>>& grid) {
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
int black = 0;
if (grid[i][j] == 'B') ++black;
if (grid[i + 1][j] == 'B') ++black;
if (grid[i][j + 1] == 'B') ++black;
if (grid[i + 1][j + 1] == 'B') ++black;
if (black != 2) return true;
}
}
return false;
}
};class Solution:
def canMakeSquare(self, grid: list[list[str]]) -> bool:
for i in range(2):
for j in range(2):
black = 0
black += grid[i][j] == 'B'
black += grid[i + 1][j] == 'B'
black += grid[i][j + 1] == 'B'
black += grid[i + 1][j + 1] == 'B'
if black != 2:
return True
return Falsevar canMakeSquare = function(grid) {
for (let i = 0; i < 2; i++) {
for (let j = 0; j < 2; j++) {
let black = 0;
if (grid[i][j] === 'B') black++;
if (grid[i + 1][j] === 'B') black++;
if (grid[i][j + 1] === 'B') black++;
if (grid[i + 1][j + 1] === 'B') black++;
if (black !== 2) return true;
}
}
return false;
};
Comments