Make a Square with the Same Color - Practice Coding Problems

Make a Square with the Same Color - Problem

You are given a 3 × 3 matrix grid 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 × 2 square where all cells are of the same color.

Return true if it is possible to create a 2 × 2 square of the same color, otherwise return false.

Input & Output

Example 1 — Solution Exists

$ Input: grid = [["B","W","B"],["B","W","W"],["W","B","B"]]

› Output: true

💡 Note: The top-right 2×2 square is ["W","B"],["W","W"]. We can change grid[0][2] from "B" to "W" to make all cells "W".

Example 2 — Already Has Square

$ Input: grid = [["B","W","B"],["W","B","W"],["B","W","B"]]

› Output: false

💡 Note: No 2×2 square can be made uniform with at most 1 change. Each square needs 2 or more changes.

Example 3 — Already Perfect

$ Input: grid = [["B","B","W"],["B","B","W"],["W","W","W"]]

› Output: true

💡 Note: The top-left 2×2 square is already all "B": ["B","B"],["B","B"]. No changes needed.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Grid

3×3 matrix with B and W cells

Check 2×2 Squares

Find squares needing ≤1 change

Result

Return true if any square can be made uniform

Key Takeaway

🎯 Key Insight: Check all 4 possible 2×2 squares and count minimum changes needed for each

Asked in

G Google 15 f Meta 12 a Amazon 8

The key insight is that there are only 4 possible 2×2 squares in a 3×3 grid. For each square, count how many cells need to change to make all cells the same color (try both B and W). Best approach uses early termination when a solution is found. Time: O(1), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Enumeration	O(1)	O(1)	Check all possible 2×2 squares and count mismatches
Early Termination Check	O(1)	O(1)	Stop checking once we find a valid 2×2 square

Brute Force Enumeration — Algorithm Steps

Step 1: Iterate through all 4 possible 2×2 square positions
Step 2: For each square, try both colors ('B' and 'W')
Step 3: Count mismatches for each color and find minimum
Step 4: If minimum changes ≤ 1, return true

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Position (0,0)

Count changes needed for top-left 2×2

Check Position (0,1)

Count changes needed for top-right 2×2

Check Position (1,0)

Count changes needed for bottom-left 2×2

Check Position (1,1)

Count changes needed for bottom-right 2×2

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(char grid[3][3]) {
    // Check all 4 possible 2x2 squares in the 3x3 grid
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            // Extract the 2x2 square starting at position (i, j)
            char square[4] = {grid[i][j], grid[i][j+1], grid[i+1][j], grid[i+1][j+1]};
            
            // Count mismatches for both 'B' and 'W'
            int bMismatches = 0, wMismatches = 0;
            for (int k = 0; k < 4; k++) {
                if (square[k] != 'B') bMismatches++;
                if (square[k] != 'W') wMismatches++;
            }
            
            // If we need at most 1 change for either color
            int minChanges = (bMismatches < wMismatches) ? bMismatches : wMismatches;
            if (minChanges <= 1) {
                return true;
            }
        }
    }
    
    return false;
}

int main() {
    char line[100];
    fgets(line, sizeof(line), stdin);
    
    // Parse the 3x3 grid from JSON format
    char grid[3][3];
    char* ptr = line;
    
    // Skip to first character
    while (*ptr && (*ptr == '[' || *ptr == '"' || *ptr == ' ')) ptr++;
    
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            grid[i][j] = *ptr;
            ptr++;
            // Skip delimiters
            while (*ptr && (*ptr == '"' || *ptr == ',' || *ptr == ' ' || *ptr == '[' || *ptr == ']')) ptr++;
        }
    }
    
    bool result = solution(grid);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Fixed 3×3 grid means constant 4 squares × 2 colors × 4 cells = 32 operations

✓ Linear Growth

Space Complexity

O(1)

Only uses a few variables to count mismatches

✓ Linear Space

12.0K Views

Medium Frequency

~10 min Avg. Time

425 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Enumeration — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler