Problem

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.

Examples

Example 1

1
2
3
4
5
6
7
8


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]`.

Example 2

1
2
3
4
5
6
7
8


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

Output: false

Explanation:

It cannot be done by changing at most one cell.

Example 3

1
2
3
4
5
6
7
8


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'.

Solution

Method 1 – Brute Force Enumeration

Intuition

Since the grid is only 3x3, we can try changing each cell (or none) to either ‘B’ or ‘W’ and check if any 2x2 square becomes monochromatic. This brute force is feasible due to the small size.

Approach

  1. For each cell (including no change), try changing it to ‘B’ and ‘W’ (if not already that color).
  2. For each configuration, check all four possible 2x2 squares in the 3x3 grid.
  3. If any 2x2 square is all the same color, return true.
  4. If no configuration works, return false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    bool canMakeSquare(vector<vector<char>>& grid) {
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                for (char c : {'B', 'W'}) {
                    auto g = grid;
                    g[i][j] = c;
                    if (check(g)) return true;
                }
            }
        }
        return check(grid);
    }
    bool check(vector<vector<char>>& g) {
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {
                char c = g[i][j];
                if (g[i][j+1] == c && g[i+1][j] == c && g[i+1][j+1] == c) return true;
            }
        }
        return false;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

func canMakeSquare(grid [][]byte) bool {
    check := func(g [][]byte) bool {
        for i := 0; i < 2; i++ {
            for j := 0; j < 2; j++ {
                c := g[i][j]
                if g[i][j+1] == c && g[i+1][j] == c && g[i+1][j+1] == c {
                    return true
                }
            }
        }
        return false
    }
    for i := 0; i < 3; i++ {
        for j := 0; j < 3; j++ {
            for _, c := range []byte{'B', 'W'} {
                g := make([][]byte, 3)
                for k := range g {
                    g[k] = make([]byte, 3)
                    copy(g[k], grid[k])
                }
                g[i][j] = c
                if check(g) {
                    return true
                }
            }
        }
    }
    return check(grid)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public boolean canMakeSquare(char[][] grid) {
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                for (char c : new char[]{'B', 'W'}) {
                    char[][] g = new char[3][3];
                    for (int x = 0; x < 3; ++x) g[x] = grid[x].clone();
                    g[i][j] = c;
                    if (check(g)) return true;
                }
            }
        }
        return check(grid);
    }
    boolean check(char[][] g) {
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {
                char c = g[i][j];
                if (g[i][j+1] == c && g[i+1][j] == c && g[i+1][j+1] == c) return true;
            }
        }
        return false;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun canMakeSquare(grid: Array<CharArray>): Boolean {
        fun check(g: Array<CharArray>): Boolean {
            for (i in 0..1) for (j in 0..1) {
                val c = g[i][j]
                if (g[i][j+1] == c && g[i+1][j] == c && g[i+1][j+1] == c) return true
            }
            return false
        }
        for (i in 0..2) for (j in 0..2) for (c in charArrayOf('B','W')) {
            val g = Array(3) { grid[it].clone() }
            g[i][j] = c
            if (check(g)) return true
        }
        return check(grid)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def canMakeSquare(self, grid: list[list[str]]) -> bool:
        def check(g):
            for i in range(2):
                for j in range(2):
                    c = g[i][j]
                    if g[i][j+1] == c and g[i+1][j] == c and g[i+1][j+1] == c:
                        return True
            return False
        for i in range(3):
            for j in range(3):
                for c in 'BW':
                    g = [row[:] for row in grid]
                    g[i][j] = c
                    if check(g):
                        return True
        return check(grid)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

impl Solution {
    pub fn can_make_square(grid: Vec<Vec<char>>) -> bool {
        fn check(g: &Vec<Vec<char>>) -> bool {
            for i in 0..2 {
                for j in 0..2 {
                    let c = g[i][j];
                    if g[i][j+1] == c && g[i+1][j] == c && g[i+1][j+1] == c {
                        return true;
                    }
                }
            }
            false
        }
        for i in 0..3 {
            for j in 0..3 {
                for &c in ['B','W'].iter() {
                    let mut g = grid.clone();
                    g[i][j] = c;
                    if check(&g) {
                        return true;
                    }
                }
            }
        }
        check(&grid)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    canMakeSquare(grid: string[][]): boolean {
        function check(g: string[][]): boolean {
            for (let i = 0; i < 2; ++i) for (let j = 0; j < 2; ++j) {
                const c = g[i][j];
                if (g[i][j+1] === c && g[i+1][j] === c && g[i+1][j+1] === c) return true;
            }
            return false;
        }
        for (let i = 0; i < 3; ++i) for (let j = 0; j < 3; ++j) for (const c of ['B','W']) {
            const g = grid.map(row => row.slice());
            g[i][j] = c;
            if (check(g)) return true;
        }
        return check(grid);
    }
}

Complexity

  • ⏰ Time complexity: O(3*3*2*4) = O(1), as the grid is fixed size and we check all possibilities.
  • 🧺 Space complexity: O(1), as we use only a few variables and small copies.