We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Make a Square with the Same Color

Difficulty: Easy

Problem Description

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.

Key Insights

  • The grid is always 3x3, which limits the number of potential 2x2 squares to check.
  • There are four possible positions for a 2x2 square within a 3x3 grid.
  • To form a 2x2 square of uniform color, either all four cells must be the same, or three cells must be the same with only one cell different.

Space and Time Complexity

Time Complexity: O(1) - Since the grid size is fixed, the number of checks is constant. Space Complexity: O(1) - No additional space is required.

Solution

To determine if we can create a 2x2 square of the same color, we can check each possible 2x2 square in the 3x3 grid. We will identify the characters in each square and count how many of them are the same. If three or four of them are the same, we can change at most one cell to achieve the desired result. The possible positions for the 2x2 squares in the 3x3 grid are:

  1. Top-left corner (grid[0][0], grid[0][1], grid[1][0], grid[1][1])
  2. Top-right corner (grid[0][1], grid[0][2], grid[1][1], grid[1][2])
  3. Bottom-left corner (grid[1][0], grid[1][1], grid[2][0], grid[2][1])
  4. Bottom-right corner (grid[1][1], grid[1][2], grid[2][1], grid[2][2])

For each of these squares, we can count the occurrences of 'B' and 'W' and determine if it is possible to create a uniform square.

Code Solutions

def canMakeSquare(grid):
    # Function to check if a 2x2 square can be made
    def checkSquare(r, c):
        colors = [grid[r][c], grid[r][c+1], grid[r+1][c], grid[r+1][c+1]]
        countB = colors.count('B')
        countW = colors.count('W')
        return countB >= 3 or countW >= 3

    # Check each possible 2x2 square
    for i in range(2):
        for j in range(2):
            if checkSquare(i, j):
                return True
    return False
← Back to All Questions