Make a Square with the Same Color

Difficulty: Easy | Acceptance: 53.20% | Paid: No Topics: Array, Matrix, Enumeration

You are given a 3x3 grid, represented as a 2D array of characters. Each cell in the grid contains either ‘B’ (Black) or ‘W’ (White).

In one operation, you can change the color of any cell to either ‘B’ or ‘W’.

Return true if it is possible to make a 2x2 square within the grid where all 4 cells have the same color. Otherwise, return false.

• Examples
• Constraints
• Direct Enumeration
• 2D Prefix Sum

Examples

Example 1:

Input: grid = [["B","W","B"],["B","W","B"],["B","W","B"]]
Output: true
Explanation: We can change the color of the cell at (1, 1) to 'B' to make the top-left 2x2 square all 'B's.

Example 2:

Input: grid = [["B","W","B"],["W","B","W"],["B","W","B"]]
Output: false
Explanation: No matter which cell we change, we cannot form a 2x2 square with all cells having the same color.

Example 3:

Input: grid = [["B","B","B"],["B","B","B"],["B","B","B"]]
Output: true
Explanation: The grid is already all 'B's, so any 2x2 square is valid.

Constraints

grid.length == 3
grid[i].length == 3
grid[i][j] is either 'W' or 'B'.

Direct Enumeration

Intuition Since the grid is fixed at 3x3, there are only 4 possible 2x2 squares (top-left, top-right, bottom-left, bottom-right). We can simply check each of these 4 squares. If any square contains at least 3 cells of the same color, we can change the remaining cell to match, making a valid square.

Steps

• Iterate through the top-left corners of the 4 possible 2x2 squares (i from 0 to 1, j from 0 to 1).
• For each square, count the number of ‘B’ and ‘W’ cells.
• If the count of ‘B’ is 3 or more, or the count of ‘W’ is 3 or more, return true.
• If none of the squares satisfy the condition after checking all, return false.

class Solution:
    def canMakeSquare(self, grid: List[List[str]]) -> bool:
        for i in range(2):
            for j in range(2):
                b = 0
                w = 0
                for x in range(2):
                    for y in range(2):
                        if grid[i+x][j+y] == 'B':
                            b += 1
                        else:
                            w += 1
                if b >= 3 or w >= 3:
                    return True
        return False

Complexity

• Time: O(1) - The grid size is constant (3x3), so we perform a constant number of operations.
• Space: O(1) - We only use a few integer variables for counting.
• Notes: This is the most optimal approach for the given constraints.

2D Prefix Sum

Intuition We can use a 2D prefix sum array to efficiently calculate the sum of values in any sub-rectangle. Here, we can map ‘B’ to 1 and ‘W’ to 0. By building a prefix sum array, we can query the number of ‘B’s in any 2x2 square in O(1) time. This approach is overkill for a 3x3 grid but demonstrates a scalable technique for larger matrices.

Steps

• Initialize a 4x4 prefix sum array with zeros.
• Iterate through the 3x3 grid to populate the prefix sum array. prefix[i+1][j+1] stores the sum of the rectangle from (0,0) to (i,j).
• Iterate through the 4 possible 2x2 squares. For each square defined by top-left corner (i, j), calculate the sum of ‘B’s using the inclusion-exclusion principle on the prefix sum array.
• If the count of ‘B’s is >= 3 or the count of ‘W’s (which is 4 - count of ‘B’s) is >= 3, return true.
• If no square satisfies the condition, return false.

class Solution:
    def canMakeSquare(self, grid: List[List[str]]) -> bool:
        n = 3
        prefix = [[0] * (n + 1) for _ in range(n + 1)]
        for i in range(n):
            for j in range(n):
                val = 1 if grid[i][j] == 'B' else 0
                prefix[i+1][j+1] = val + prefix[i][j+1] + prefix[i+1][j] - prefix[i][j]
        
        for i in range(2):
            for j in range(2):
                b_count = prefix[i+2][j+2] - prefix[i][j+2] - prefix[i+2][j] + prefix[i][j]
                w_count = 4 - b_count
                if b_count >= 3 or w_count >= 3:
                    return True
        return False

Complexity

• Time: O(n²) to build the prefix sum, where n is the grid dimension. For this problem, n=3, so it is effectively O(1).
• Space: O(n²) to store the prefix sum array.
• Notes: While this approach is generalizable to much larger grids and range queries, it uses more memory than the direct enumeration method for this specific problem size.