Find the Top-Left Submatrix Matching a Grid Pattern With Letter Variables

You are given a matrix of integers and a pattern grid with p rows and q columns. Each pattern cell is either a number, which must equal the matrix value it covers, or a lowercase letter, which stands for an unknown number: every cell holding the same letter must cover the same matrix value. Find a p x q submatrix of the matrix that matches the pattern and return the coordinate of its top-left cell. If several submatrices match, return the one with the lowest row index, and among those the lowest column index.

Function Signature

def find_pattern(matrix: list[list[int]], pattern: list[list[str]]) -> list[int]:

Rules

• Placing the pattern with its top-left cell at (r, c) lines up pattern[i][j] with matrix[r + i][c + j] for every 0 <= i < p and 0 <= j < q. The whole pattern must lie inside the matrix, and it is never rotated or reflected.
• A number cell is written as str(v) for an integer v (for example "5" or "-12") and matches only a matrix value equal to v.
• A letter cell matches any value, but within one placement all cells holding the same letter must cover equal values. Different letters are independent: they may cover equal or different values, and a letter may cover a value that also appears as a number cell.
• Return [r, c] for the matching placement with the smallest r, breaking ties by the smallest c. Return [-1, -1] if no placement matches.

Constraints

• 1 <= len(matrix) <= 50 and 1 <= len(matrix[0]) <= 50; all matrix rows have the same length.
• 1 <= p <= len(matrix) and 1 <= q <= len(matrix[0]); all pattern rows have length q.
• -10^9 <= matrix[i][j] <= 10^9
• Each pattern cell is either one lowercase letter from a to z, or str(v) for an integer -10^9 <= v <= 10^9.

Examples

Example 1

Input:  matrix = [[7, 8, 4, 4],
                  [6, 6, 5, 9],
                  [5, 3, 5, 0]]
        pattern = [["x", "x"],
                   ["5", "y"]]
Output: [0, 2]

At (0, 0) the two x cells cover 7 and 8, and at (0, 1) they cover 8 and 4, so both fail. At (0, 2) both x cells cover 4, the "5" cell covers 5, and y covers 9, so it matches. The placement at (1, 0) also matches (x covers 6 twice, "5" covers 5, y covers 3), but its row index is higher.

Example 2

Input:  matrix = [[1, 1], [1, 1]], pattern = [["a", "b"]]
Output: [0, 0]

a and b both cover 1, which is allowed because different letters are independent.

Example 3

Input:  matrix = [[1, 2, 3], [4, 5, 6]], pattern = [["a"], ["a"]]
Output: [-1, -1]

The three placements cover the pairs (1, 4), (2, 5) and (3, 6); none of them holds two equal values.

Find the First Placement of a Letter-and-Number Pattern in a Grid

Hints

1. A placement counts only if the entire p x q pattern fits inside the matrix; work out which top-left rows and columns that allows.
2. Within one placement, the first cell holding a letter fixes that letter's value, and every later cell with the same letter must cover exactly that value. What one placement learned about a letter says nothing about the next placement.
3. A number cell such as "10" matches only the integer 10, never 100. Two different letters, or a letter and a number cell, are allowed to cover equal values.

Approach

Approach: check every placement in the required order.

1. Preprocess the pattern once into a flat list of cells. A cell that is a single character from a to z is a letter and stores its index 0-25; every other cell is a number written as str(v) and stores the parsed integer v.
2. Enumerate top-left corners in row-major order: r from 0 to n - p and, for each r, c from 0 to m - q, where the matrix is n x m. These are exactly the placements that keep the whole pattern inside the matrix.
3. For each placement, start with no letter bindings (a per-placement table; the non-Python references use a 26-slot stamp array so the reset costs O(1)). Walk the pattern cells: a number cell fails the placement unless the covered value equals its integer; a letter cell binds the covered value on its first occurrence and fails the placement if a later occurrence covers a different value.
4. Return the first placement that survives every cell; if none does, return [-1, -1].

Correctness: a placement survives exactly when every number cell equals its covered value and, for each letter, all covered values equal the first one, which is the definition of a match. Each letter has its own slot, so different letters may share a value and a letter may equal a number cell, as the rules allow; bindings never carry over between placements. Because placements are visited in lexicographic (r, c) order, the first match found has the smallest row and, within that row, the smallest column.

Edge cases: a pattern the same size as the matrix has exactly one placement; single-row and single-column inputs work the same way; numbers are compared as integers, so "10" never matches 100 and "-12" is a number, not a letter; zero, negative values and the 10^9 extremes all fit in 32-bit integers.

• Time complexity: O((n - p + 1) * (m - q + 1) * p * q)
• Space complexity: O(p * q)