Skip to main content

Matrix

Make a Square with the Same Color Solution In C++/Python/java/JS

Make a Square with the Same Color Question Description

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.

Example  

Input: grid = [["B","W","B"],["B","W","W"],["B","W","B"]]
Output: true
Explanation: It can be done by changing the color of the grid[0][2].

Input: grid = [["B","W","B"],["W","B","W"],["B","W","B"]]
Output: false
Explanation: It cannot be done by changing at most one cell.

Input: grid = [["B","W","B"],["B","W","W"],["B","W","W"]]
Output: true
Explanation: The grid already contains a 2 x 2 square of the same color.

Constraints

  • grid.length == 3
  • grid[i].length == 3
  • grid[i][j] is either 'W' or 'B'.
💡
Try Solving "Make a Square with the Same Color" Yourself First !!
Figuring out "Make a Square with the Same Color solution" can be solved using different approaches. We will first figure out the most intuitive approach and move to the optimal approach if exists. Let's sit with a pen and paper and figure out the algorithm !!

Optimal Approach

Intuition

We’re given a 3×3 grid, and each cell is either black ('B') or white ('W'). We’re allowed to change at most one cell. Our goal is to form a 2×2 square of the same color. Think we can spot how to do it?

So we want to find a 2×2 square where all four cells are either 'B' or all 'W'? And we can change just one cell?
Exactly. Let’s take an example:
W B B
B B W
W W B

Okay, We’ll try looking at all 2×2 sections. There are only a few of them, right?
A 3×3 grid has four 2×2 squares:

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

Let’s go through them one at a time. Look at the top-left square first:

W B
B B

That’s 3 blacks and 1 white. So if we change the white to black, we get four blacks!

Exactly! That would give us a valid 2×2 square of all black. Now think about this: What are we really trying to spot in these 2×2 sections?

I guess… if we see three or more of the same color, we can just flip the remaining one, and we’re done?

Exactly! we nailed the intuition. If any 2×2 section has at least 3 of one color, we can always make it uniform by flipping the fourth. Remember, we can only flip one cell, so two of each color won’t work. Let’s test that with another square from this grid.

Take the bottom-right:
B W
W B
Ah, two blacks and two whites. That’s not going to work—flipping one won’t be enough.

Precisely. So now we just need to check each 2×2 square in the grid, and for each one, count how many black and white cells it has. If either black or white count is 3 or 4, we’re good to go.
So we're not doing anything fancy like dynamic programming or graphs here—we’re just checking small patches in the grid?

Yep! It's just a simple local check. The intuition we just walked through—checking 2×2 blocks for having 3 or more same-color squares—is what leads us to this optimal solution. Now that we’ve built this understanding, here’s how we can translate it into code.

Oh wow! Now the code totally makes sense. We just slide a window over all 2×2 blocks and look for those 3+ same-colored cells.

Exactly! Because the grid is always 3×3, we’re doing a constant amount of work. So this solution is O(1) in both time and space.

And now we know, it’s not about blindly flipping a cell. It’s about scanning smartly for a near-complete square!

Next time we see a grid problem, we mustn't panic rather just look for patterns and break it down, one block at a time.

Yes! Now, let’s outline the steps of our Algorithm

Make a Square with the Same Color Algorithm

Step 1: Iterate Over All 2x2 Subgrids
There are only 4 possible 2x2 squares in a 3x3 grid:

  • Top-left at (0,0)
  • Top-left at (0,1)
  • Top-left at (1,0)
  • Top-left at (1,1)

Loop i from 0 to 1 (rows).
Loop j from 0 to 1 (columns).
For each (i, j) as top-left:

  • Initialize black = 0, white = 0.

Step 2: Count 'B' and 'W' in Each 2x2 Block

  • For x in 0 to 1 and y in 0 to 1:
    • Access grid[i + x][j + y].
    • If it's 'B', increment black.
    • Else (must be 'W'), increment white.

Step 4: Check Condition
After counting the characters:

  • If black >= 3 OR white >= 3, return true (a valid square exists).

Step 5: Final Result

  • If no such 2x2 square satisfies the condition, return false.
  • Print "YES" if result is true, otherwise "NO".

Dry-Run

This matrix is stored as:

char[][] grid = {
{'B', 'W', 'B'},
{'W', 'B', 'W'},
{'B', 'W', 'B'}
};

Dry Run of canMakeSquare(grid)

Loop over all possible 2x2 squares (top-left corners at (0,0), (0,1), (1,0), (1,1)):

Subgrid at (0, 0):
B W 
W B

  • black = 0, white = 0
  • Count each cell:
    • B → black = 1
    • W → white = 1
    • W → white = 2
    • B → black = 2
  • Final counts: black = 2, white = 2
  • Not enough to return true

Subgrid at (0, 1):
W B 
B W

  • black = 0, white = 0
  • Count each cell:
    • W → white = 1
    • B → black = 1
    • B → black = 2
    • W → white = 2
  • Final counts: black = 2, white = 2
  • Not enough to return true

Subgrid at (1, 0):
W B 
B W

  • Same pattern as previous
  • Final counts: black = 2, white = 2
  • Not enough to return true

Subgrid at (1, 1):

B W 
W B

  • Same pattern
  • Final counts: black = 2, white = 2
  • Not enough to return true

Conclusion

  • None of the 2x2 subgrids have 3 or more cells with the same character
  • So, the method returns: false

Output: NO

Let's Visualize the Dry-Run with the images

Make a Square with the Same Color(Dry-Run)
Make a Square with the Same Color (Dry-Run)

Make a Square with the Same Color Solution

Now lets checkout the "Make a Square with the Same Color code in C++ , Java, Python and JavaScript.

"Make a Square with the Same Color" Code in all Languages.
1. Make a Square with the Same Color solution in C++ Try on Compiler 
class Solution {
public:
    // Method to check if a 2x2 square contains at least 3 same characters
    bool canMakeSquare(vector<vector<char>>& grid) {

        // Loop over the top-left corners of all 2x2 subgrids
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {

                // Count black and white cells
                int black = 0;
                int white = 0;

                // Check each cell in the 2x2 block
                for (int x = 0; x < 2; ++x) {
                    for (int y = 0; y < 2; ++y) {
                        if (grid[i + x][j + y] == 'B') {
                            ++black;
                        } else {
                            ++white;
                        }
                    }
                }

                // If there are 3 or more of one type, return true
                if (black >= 3 || white >= 3)
                    return true;
            }
        }

        // No valid square found
        return false;
    }
};

2. Make a Square with the Same Color Solution in Java Try on Compiler 
class Solution {

    // Method to check if a 2x2 square in the grid has at least 3 same characters
    public boolean canMakeSquare(char[][] grid) {

        // Loop through all top-left corners of possible 2x2 subgrids
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {

                // Initialize counts of 'B' and 'W'
                int black = 0;
                int white = 0;

                // Count colors in the current 2x2 block
                for (int x = 0; x < 2; ++x) {
                    for (int y = 0; y < 2; ++y) {
                        if (grid[i + x][j + y] == 'B') {
                            ++black;
                        } else {
                            ++white;
                        }
                    }
                }

                // If 3 or more cells are the same color, return true
                if (black >= 3 || white >= 3) return true;
            }
        }

        // No valid square found
        return false;
    }
}

3. Make a Square with the Same Color Solution in Python Try on Compiler 
def canMakeSquare(grid):
    # Iterate over all possible top-left corners of 2x2 squares
    for i in range(2):
        for j in range(2):
            black = 0
            white = 0

            # Count black and white cells in the 2x2 square
            for x in range(2):
                for y in range(2):
                    if grid[i + x][j + y] == 'B':
                        black += 1
                    else:
                        white += 1

            # If at least 3 are the same, return True
            if black >= 3 or white >= 3:
                return True

    # No such square found
    return False

4. Make a Square with the Same Color solution in JavaScript Try on Compiler 
class Solution {
    // Method to check if a 2x2 square contains at least 3 same characters
    canMakeSquare(grid) {
        // Loop through each top-left corner of 2x2 subgrids
        for (let i = 0; i < 2; ++i) {
            for (let j = 0; j < 2; ++j) {

                // Count 'B' and 'W' in the current 2x2 block
                let black = 0;
                let white = 0;

                for (let x = 0; x < 2; ++x) {
                    for (let y = 0; y < 2; ++y) {
                        if (grid[i + x][j + y] === 'B') {
                            black++;
                        } else {
                            white++;
                        }
                    }
                }

                // If 3 or more of the same type, return true
                if (black >= 3 || white >= 3) {
                    return true;
                }
            }
        }

        // No valid square found
        return false;
    }
}

Make a Square with the Same Color Complexity Analysis

Time Complexity: O(n)

1. Outer Loop:

  • Iterates over all 2x2 subgrids in the 3x3 grid.
  • You can have 4 possible top-left corners for 2x2 squares in a 3x3 grid:
    • (0,0), (0,1), (1,0), (1,1)

So:
for (int i = 0; i < 2; ++i)
for (int j = 0; j < 2; ++j)

Runs 4 times.

Inner Loop: For each 2x2 subgrid, it loops through the 4 cells:
for (int x = 0; x < 2; ++x)
for (int y = 0; y < 2; ++y)

Also runs 4 times per subgrid.

3. Total Time:

  • Outer: 4 iterations
  • Inner: 4 operations per iteration

→ 4 × 4 = 16 time operations

Hence, Time Complexity: O(n)

Space Complexity: O(1)

Auxiliary Space Complexity refers to the extra space required by an algorithm other than the input space.

  • The method uses:
    • Two integer counters: black and white
    • A few loop variables
  • All are primitive variables; no extra data structures are allocated.

Auxiliary Space Complexity: O(1)
Total Space Complexity

  • The input grid is of fixed size: char[3][3]
  • This consumes 9 characters, i.e., O(n)

Total Space Complexity: O(n)

Similar Problems

House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Rat in a Maze Problem - I

Consider a rat placed at position (0, 0) in an n x n square matrix mat. The rat's goal is to reach the destination at position (n-1, n-1). The rat can move in four possible directions: 'U'(up), 'D'(down), 'L' (left), 'R' (right).

The matrix contains only two possible values:

  • 0: A blocked cell through which the rat cannot travel.
  • 1: A free cell that the rat can pass through.