Problem Description

You are given a 3×3 grid filled with characters 'B' (representing black color) and 'W' (representing white color).

Your goal is to determine if you can create a 2×2 square where all four cells have the same color by changing the color of at most one cell in the grid.

The task asks you to:

• Look at the given 3×3 grid
• Check if there exists any 2×2 square within this grid that either:
  • Already has all four cells of the same color, OR
  • Can have all four cells of the same color after changing at most one cell

Return true if such a 2×2 square of uniform color can be created, otherwise return false.

For example, in a 3×3 grid, there are four possible 2×2 squares:

• Top-left corner (cells at positions [0,0], [0,1], [1,0], [1,1])
• Top-right corner (cells at positions [0,1], [0,2], [1,1], [1,2])
• Bottom-left corner (cells at positions [1,0], [1,1], [2,0], [2,1])
• Bottom-right corner (cells at positions [1,1], [1,2], [2,1], [2,2])

If any of these 2×2 squares has at least 3 cells of the same color (meaning you'd need to change at most 1 cell to make all 4 uniform), then the answer is true.

Intuition

The key insight is that we only need to check each possible 2×2 square within the 3×3 grid. Since we can change at most one cell, a 2×2 square can be made uniform if it has at least 3 cells of the same color.

Think about it this way: in any 2×2 square (which has 4 cells total), the possible distributions of colors are:

• 4 cells of one color, 0 of the other → already uniform
• 3 cells of one color, 1 of the other → can change the 1 different cell to make it uniform
• 2 cells of each color → would need to change 2 cells to make it uniform (not allowed)

So the question becomes: does any 2×2 square in our grid have an unequal distribution of 'B' and 'W'?

If we count the number of 'B' cells and 'W' cells in a 2×2 square:

• If count('B') ≠ count('W'), then one color appears more than the other, meaning we have either a 3-1 or 4-0 distribution, both of which work
• If count('B') = count('W'), then we have a 2-2 distribution, which doesn't work

Therefore, we can iterate through all four possible 2×2 squares in the 3×3 grid, count the occurrences of each color, and if any square has unequal counts, we return true. If all squares have equal counts (2-2 distribution), we return false.

The solution cleverly uses pairwise to iterate through the four corners of each 2×2 square in a circular manner, counting both colors and checking if their counts differ.

Solution Approach

The solution uses a nested loop to check all possible 2×2 squares within the 3×3 grid.

Step 1: Iterate through starting positions

for i in range(0, 2):
    for j in range(0, 2):

We only need i and j to go from 0 to 1 (not 2) because these represent the top-left corner of each 2×2 square. Starting from position (i, j), we can form a 2×2 square with corners at (i, j), (i, j+1), (i+1, j), and (i+1, j+1).

Step 2: Count colors in each 2×2 square For each starting position, we need to visit the four cells of the 2×2 square. The solution uses a clever technique with pairwise:

for a, b in pairwise((0, 0, 1, 1, 0)):
    x, y = i + a, j + b

The pairwise((0, 0, 1, 1, 0)) generates pairs: (0,0), (0,1), (1,1), (1,0). When added to the base position (i, j), these offsets give us the four corners of the 2×2 square in a circular order:

• (i+0, j+0) → top-left
• (i+0, j+1) → top-right
• (i+1, j+1) → bottom-right
• (i+1, j+0) → bottom-left

Step 3: Count occurrences of each color

cnt1 += grid[x][y] == "W"
cnt2 += grid[x][y] == "B"

For each cell in the 2×2 square, we increment cnt1 if it's white and cnt2 if it's black.

Step 4: Check if the square can be made uniform

if cnt1 != cnt2:
    return True

If the counts are not equal, it means we have either:

• 3 whites and 1 black (can change the black to white)
• 1 white and 3 blacks (can change the white to black)
• 4 of the same color (already uniform)

Any of these cases allows us to create a uniform 2×2 square with at most one change.

Step 5: Return false if no valid square found If we've checked all four possible 2×2 squares and none had unequal color counts (all were 2-2 splits), then it's impossible to create a uniform square with at most one change.

Example Walkthrough

Let's walk through an example with the following 3×3 grid:

W B W
B W B
W B W

Step 1: Check the top-left 2×2 square (i=0, j=0)

• Cells: [0,0]='W', [0,1]='B', [1,0]='B', [1,1]='W'
• Count: 2 whites, 2 blacks
• Since cnt1 == cnt2 (both are 2), we cannot make this uniform with ≤1 change

Step 2: Check the top-right 2×2 square (i=0, j=1)

• Cells: [0,1]='B', [0,2]='W', [1,1]='W', [1,2]='B'
• Count: 2 whites, 2 blacks
• Since cnt1 == cnt2 (both are 2), we cannot make this uniform with ≤1 change

Step 3: Check the bottom-left 2×2 square (i=1, j=0)

• Cells: [1,0]='B', [1,1]='W', [2,0]='W', [2,1]='B'
• Count: 2 whites, 2 blacks
• Since cnt1 == cnt2 (both are 2), we cannot make this uniform with ≤1 change

Step 4: Check the bottom-right 2×2 square (i=1, j=1)

• Cells: [1,1]='W', [1,2]='B', [2,1]='B', [2,2]='W'
• Count: 2 whites, 2 blacks
• Since cnt1 == cnt2 (both are 2), we cannot make this uniform with ≤1 change

Result: Return false - no 2×2 square can be made uniform with at most one change.

Now let's try a different example where the answer is true:

W B W
B B B
W B W

Step 1: Check the top-left 2×2 square (i=0, j=0)

• Cells: [0,0]='W', [0,1]='B', [1,0]='B', [1,1]='B'
• Count: 1 white, 3 blacks
• Since cnt1 ≠ cnt2 (1 ≠ 3), we can make this uniform by changing the one 'W' to 'B'

Result: Return true immediately - we found a valid 2×2 square!

The key insight is that we only need to find ONE 2×2 square with unequal color distribution to return true. In this case, changing cell [0,0] from 'W' to 'B' would create an all-black 2×2 square in the top-left corner.

Solution Implementation

Time and Space Complexity

The time complexity is O(1). The code uses two nested loops that iterate from 0 to 1 (2 iterations each), creating a total of 4 iterations for the outer loops. For each of these 4 positions, it checks a 2×2 subgrid by iterating through 4 cells using the pairwise function on the tuple (0, 0, 1, 1, 0), which generates 4 pairs: (0,0), (0,1), (1,1), (1,0). Therefore, the total number of operations is 4 × 4 = 16, which is a constant number regardless of input size.

The space complexity is O(1). The algorithm only uses a constant amount of extra space for variables i, j, cnt1, cnt2, a, b, x, and y. The pairwise function creates an iterator that generates pairs on-the-fly without storing all pairs in memory, so it doesn't contribute to additional space complexity. No data structures that grow with input size are created.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Loop Bounds for Starting Positions

A common mistake is using range(3) instead of range(2) for the outer loops. This would attempt to create 2×2 squares starting from position (2,2), which would go out of bounds when trying to access cells at (3,3).

Incorrect:

for row in range(3):  # Wrong! This tries to access grid[3][x]
    for col in range(3):  # Wrong! This tries to access grid[x][3]

Correct:

for row in range(2):  # Correct - ensures 2x2 square stays within bounds
    for col in range(2):

2. Misunderstanding the Problem - Checking Individual Cells Instead of 2×2 Squares

Some might interpret the problem as checking if any single cell can be changed to create some pattern, rather than specifically checking 2×2 squares.

Incorrect Approach:

# Wrong - just counting total colors in entire grid
total_white = sum(row.count('W') for row in grid)
total_black = sum(row.count('B') for row in grid)

Correct Approach: Check each of the four possible 2×2 squares individually.

3. Incorrect Color Counting Logic

Using the wrong condition to determine if a square can be made uniform. Remember that we need at least 3 cells of the same color (or all 4).

Incorrect:

if white_count >= 2 or black_count >= 2:  # Wrong! A 2-2 split needs 2 changes
    return True

Correct:

if white_count != black_count:  # This means 3-1 or 4-0, which is valid
    return True

4. Over-complicating the Traversal Pattern

While the pairwise approach is elegant, it might be confusing. A simpler alternative that avoids this pitfall:

Alternative Clear Solution:

def canMakeSquare(self, grid: List[List[str]]) -> bool:
    for row in range(2):
        for col in range(2):
            # Explicitly check all 4 cells in the 2x2 square
            cells = [
                grid[row][col],     # top-left
                grid[row][col+1],   # top-right
                grid[row+1][col],   # bottom-left
                grid[row+1][col+1]  # bottom-right
            ]
          
            white_count = cells.count('W')
            black_count = cells.count('B')
          
            # If we have 3 or 4 of the same color, we can make it uniform
            if white_count >= 3 or black_count >= 3:
                return True
  
    return False

5. Forgetting Edge Cases

Not considering that a 2×2 square might already be uniform (all 4 cells same color), which requires zero changes and should return True.

Solution: The condition white_count != black_count correctly handles all cases:

• 4-0 or 0-4: Already uniform (0 changes needed)
• 3-1 or 1-3: Can be made uniform (1 change needed)
• 2-2: Cannot be made uniform with at most 1 change