Count same-color squares in a character grid
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You are given a 2D grid (matrix) of characters. Each character represents a color: cells with the same character are considered the same color.
Formally:
- The grid has `m` rows and `n` columns.
- `grid[i][j]` is an alphabetic character (e.g., `'a'`–`'z'` or `'A'`–`'Z'`).
A **square** in this grid is defined as a contiguous `k × k` submatrix aligned with the grid axes, for some integer `k ≥ 1`.
A square is **monochromatic** if **all** of its cells contain the **same** character (i.e., the same color).
Task:
- Count and return the total number of monochromatic squares in the grid.
- Count all sizes of squares (1×1, 2×2, ..., up to the largest possible that fits in the grid).
Example (just for clarity, not necessarily exhaustive):
If the grid is:
```
a a b
a a b
b b b
```
Then some monochromatic squares include:
- All 1×1 cells (each single cell is a monochromatic square).
- The 2×2 square in the top-left corner formed by `'a'`.
Your function should return the total count of such monochromatic squares for a given input grid.
Overview: This question evaluates understanding of 2D array manipulation, spatial pattern detection, and algorithmic counting with attention to time and space complexity.
You are given a 2D grid of characters, where each character represents a color. A square is a contiguous k × k submatrix aligned with the grid axes, for some k >= 1. A square is monochromatic if all of its cells contain the same character. Return the total number of monochromatic squares of all possible sizes and positions in the grid. Every 1 × 1 cell is considered a monochromatic square.
Constraints
- 0 <= len(grid) <= 1000
- If grid is non-empty, 0 <= len(grid[0]) <= 1000
- All rows in grid have the same length
- grid[i][j] is an alphabetic character
- The total number of cells is at most 1,000,000
Examples
Input: ([])
Expected Output: 0
Explanation: An empty grid contains no squares.
Input: (["aab", "aab", "bbb"])
Expected Output: 10
Explanation: There are 9 single-cell squares and one 2x2 monochromatic square of 'a' in the top-left corner.
Hints
- Try defining dp[i][j] as the side length of the largest monochromatic square whose bottom-right corner is cell (i, j).
- A square larger than 1 can end at (i, j) only if the current cell matches its top, left, and top-left neighboring cells.
Community answers
Answer by sourabh.eshaadi
public class Solution {
public long solution(String[] grid) {
if (grid == null || grid.length == 0 || grid[0].isEmpty()) {
return 0;
}
int m = grid.length;
int n = grid[0].length();
Integer[][] memo = new Integer[m][n];
long totalSquares = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
totalSquares += solve(i, j, grid, memo);
}
}
return totalSquares;
}
private int solve(int i, int j, String[] grid, Integer[][] memo) {
if (i < 0 || j < 0) return 0;
if (memo[i][j] != null) return memo[i][j];
int top = solve(i - 1, j, grid, memo);
int left = solve(i, j - 1, grid, memo);
int topLeft = solve(i - 1, j - 1, grid, memo);
if (i == 0 || j == 0) {
memo[i][j] = 1;
return 1;
}
char c = grid[i].charAt(j);
int res = 1;
if (grid[i - 1].charAt(j) == c
&& grid[i].charAt(j - 1) == c
&& grid[i - 1].charAt(j - 1) == c) {
res = 1 + Math.min(top, Math.min(left, topLeft));
}
memo[i][j] = res;
return res;
}
}
Answer by Josef420
def solution(grid):
if not grid:
return 0
ROWS = len(grid)
COLS = len(grid[0])
dp = [[None for in range(COLS)] for in range(ROWS)]
result: int = 0
for row in range(ROWS):
for col in range(COLS):
left = dp[row][col-1] if col -1 >= 0 else [-1,-1]
top = dp[row-1][col] if row -1 >= 0 else [-1,-1]
top_left = dp[row-1][col-1] if row -1 >= 0 and col -1 >= 0 else [-1,-1]
if left[0] == top[0] == top_left[0] == grid[row][col]:
val = min(left[1],top[1],top_left[1]) + 1
dp[row][col] = (grid[row][col], val)
else:
dp[row][col] = (grid[row][col], 1)
result += dp[row][col][1]
return result
Answer by memo
def solution(grid):
if not grid:
return 0
m = len(grid)
n = len(grid[0])
dp = [[0] * n for _ in range(m)]
ans = 0
for i in range(m):
for j in range(n):
if i == 0 or j == 0:
dp[i][j] = 1
else:
size = 1
if grid[i][j] == grid[i-1][j] == grid[i][j-1] == grid[i-1][j-1]:
size += min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1])
dp[i][j] = size
ans += dp[i][j]
return ans