How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

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.

Quick Answer: 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.

Input: (["xxx", "xxx"])

Expected Output: 8

Explanation: There are 6 single-cell squares and 2 monochromatic 2x2 squares.

Input: (["ab", "ba"])

Expected Output: 4

Explanation: Only the four 1x1 squares are monochromatic; the 2x2 square contains different characters.

Input: (["aaaa"])

Expected Output: 4

Explanation: A single-row grid can only contain 1x1 squares, so all four cells count.

Input: (["AAA", "AAA", "AAA"])

Expected Output: 14

Explanation: All cells have the same color: 9 squares of size 1x1, 4 of size 2x2, and 1 of size 3x3.

Input: (["bbbb", "bbbb", "bbba"])

Expected Output: 18

Explanation: There are 12 single-cell squares, 5 monochromatic 2x2 squares, and 1 monochromatic 3x3 square.

Solution

def solution(grid):
    if not grid:
        return 0

    m = len(grid)
    n = len(grid[0])
    if n == 0:
        return 0

    total = 0
    prev = [0] * n

    for i in range(m):
        curr = [0] * n
        for j in range(n):
            if i == 0 or j == 0:
                curr[j] = 1
            else:
                c = grid[i][j]
                if c == grid[i - 1][j] and c == grid[i][j - 1] and c == grid[i - 1][j - 1]:
                    curr[j] = 1 + min(prev[j], curr[j - 1], prev[j - 1])
                else:
                    curr[j] = 1

            total += curr[j]

        prev = curr

    return total

Time complexity: O(m * n), where m is the number of rows and n is the number of columns.. Space complexity: O(n), because only the previous DP row and current DP row are stored..

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.

Quick Overview

This question evaluates understanding of 2D array manipulation, spatial pattern detection, and algorithmic counting with attention to time and space complexity.