Find the Top-Left Submatrix Matching a Grid Pattern With Letter Variables
Company: Capital One
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
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
```python
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**
```text
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**
```text
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**
```text
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.
Overview: Locate a pattern grid inside an integer matrix, where each pattern cell is either an exact number or a letter that must stand for one consistent value, and return the top-left corner of the match with the lowest row and then the lowest column. It tests two-dimensional scanning, variable binding, and tie-breaking rules.
Read the full Capital One Software Engineer interview experience this question came from
You are given an integer matrix `matrix` and a pattern grid `pattern` 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 `matrix` that matches the pattern and return the coordinate `[r, c]` of its top-left cell. If several submatrices match, return the one with the lowest row index, and among those the lowest column index. If no submatrix matches, return `[-1, -1]`.
Implement `find_pattern(matrix, pattern)`.
### 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"`, `"0"` or `"-12"`) and matches only a matrix value equal to `v`. It is compared as an integer, so `"10"` does not match `100`.
- 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])`, where `p = len(pattern)` and `q = len(pattern[0])`; all pattern rows have length `q`.
- `-10^9 <= matrix[i][j] <= 10^9`
- Each pattern cell is either exactly one lowercase letter from `a` to `z`, or `str(v)` for an integer `-10^9 <= v <= 10^9`.
- No value can exceed `2^31 - 1` in absolute value, so signed 32-bit integers are enough in every language.
### Example 1
```text
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
```text
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.
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]), where p = len(pattern) and q = len(pattern[0]); all pattern rows have length q.
- -10^9 <= matrix[i][j] <= 10^9
- Each pattern cell is either exactly one lowercase letter from a to z, or str(v) for an integer -10^9 <= v <= 10^9.
- No value can exceed 2^31 - 1 in absolute value, so signed 32-bit integers are enough in every language.
Examples
Input: ([[5]], [['a']])
Expected Output: [0, 0]
Explanation: Minimum valid: 1x1 matrix with a 1x1 letter pattern; the single placement always matches.
Input: ([[-12]], [['-12']])
Expected Output: [0, 0]
Explanation: 1x1 negative number cell '-12' equals the only matrix value, so it matches.
Hints
- 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.
- 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.
- 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.