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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Make a Square with the Same Color

Number: 3398

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given a 3 x 3 grid consisting of characters 'B' (black) and 'W' (white), determine if it is possible to form a 2 x 2 subgrid with all cells of the same color by changing the color of at most one cell.

Key Insights

  • There are only four possible 2 x 2 subgrids in a 3 x 3 grid.
  • For each subgrid, count the number of 'B' and 'W' cells.
  • If any subgrid has at least 3 cells of the same color, you can change the remaining cell (if needed) to form a uniform 2 x 2 square.
  • Check each subgrid and return true as soon as a valid configuration is found.

Space and Time Complexity

Time Complexity: O(1) – There is a fixed number of subgrids (4 subgrids) and each checks 4 cells. Space Complexity: O(1) – A constant amount of extra space is used.

Solution

The approach is to enumerate all 2 x 2 subgrids starting at positions (0,0), (0,1), (1,0), and (1,1). For each subgrid, count how many 'B' and 'W' cells there are. If either count is 3 or 4, then with at most one change you can have a uniform square. Otherwise, move on to the next subgrid. Return true if any subgrid can be made uniform, and false if none qualify.

Code Solutions

# Function to determine if a uniform 2x2 subgrid can be formed by changing at most one cell.
def makeASquare(grid):
    # There are only 4 possible 2x2 subgrids in a 3x3 grid.
    for i in range(2):
        for j in range(2):
            countB = 0
            countW = 0
            # Check the 2x2 subgrid starting at (i, j)
            for di in range(2):
                for dj in range(2):
                    if grid[i + di][j + dj] == 'B':
                        countB += 1
                    else:
                        countW += 1
            # If at least 3 out of 4 cells are the same, we can change the one cell if needed.
            if countB >= 3 or countW >= 3:
                return True
    return False

# Example usage:
grid = ["BWB", "BWW", "BWB"]
print(makeASquare(grid))  # Expected output: True
← Back to All Questions