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 1:
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:
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:
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 == 3grid[i].length == 3grid[i][j] is either 'W' or 'B'.This approach involves iterating over all possible 2x2 subgrids in the 3x3 matrix and checking if any such subgrid is either already uniform or can be made uniform by changing one cell.
In C, the solution iterates over all possible 2x2 subgrids within the 3x3 grid. For each subgrid, it counts the number of 'B' and 'W'. If either count is 3 or more, it means at most one cell change can make the subgrid uniform, and it can return true.
C++
Time Complexity: O(1) - The operation is constant as it consists of checking a fixed number of 2x2 subgrids.
Space Complexity: O(1) - No additional space is used apart from the input grid.
This approach recognizes specific patterns within the 2x2 subgrid that can benefit from altering a single cell to achieve uniformity.
The Java solution builds on the known fact that for any 2x2 subgrid, if at least three cells are the same, the subgrid becomes uniform with only one change. By forming a string pattern of all cells within the subgrid, it's quick to identify potential transformations to a flat color.
Python
Time Complexity: O(1).
Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Approach 1: Check 2x2 Subgrids Directly | Time Complexity: O(1) - The operation is constant as it consists of checking a fixed number of 2x2 subgrids. |
| Approach 2: Optimized Check by Pattern Recognition | Time Complexity: O(1). |
This is the Most Asked FAANG Interview Question! - Two Sum - Leetcode 1 • Greg Hogg • 649,221 views views
Watch 9 more video solutions →Practice Make a Square with the Same Color with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor