Find Repeated-Value Patterns in a Matrix

Find every placement of a small symbol matrix inside a larger integer matrix that preserves the pattern of equal and different values.

Implement find_pattern_positions(grid: int[][], pattern: string[]) -> int[][]. Each pattern string is one row of uppercase letter symbols. Return the zero-based top-left coordinate of every matching window, ordered by row and then column.

Matching contract

For each candidate window independently, there must be a one-to-one mapping between symbols and integer values:

• Every occurrence of the same symbol must match the same integer.
• Different symbols must match different integers.
• The mapping can differ between windows.

The report illustrates AT/TB matching 1,2/2,3 but does not explicitly resolve whether different symbols may share a value. This practice version chooses the one-to-one interpretation above.

Constraints & Assumptions

• The grid is rectangular, with 1 through 50 rows and columns.
• The pattern is rectangular, with 1 through 5 rows and columns, and symbols A through Z.
• Grid values are integers between -1,000,000,000 and 1,000,000,000.
• A window must fit fully inside the grid. If the pattern is larger in either dimension, return an empty list.
• Do not rotate, reflect, or resize the pattern.

Examples

grid = [[1,2,4,5],[2,3,6,7],[6,4,2,2]]
pattern = ["AT","TB"]
result = [[0,0]]

grid = [[7,7],[7,7]]
pattern = ["AA","AA"]
result = [[0,0]]

The first example's upper-left window maps A -> 1, T -> 2, and B -> 3.

Hint: Enforce both directions of the mapping

Remember both the integer assigned to each symbol and the symbol assigned to each integer. Checking only repeated symbols does not enforce distinctness between different symbols.

Find Bijective Symbol-Pattern Windows in an Integer Grid

Approach

Enumerate every fully contained top-left position in row-major order. For that window start fresh symbol-to-integer and integer-to-symbol maps. Each aligned cell must agree with both existing directions; otherwise reject immediately. Adding a new consistent pair preserves a bijection on all cells seen so far. After all cells pass, repeated symbols share values and different symbols have different values, which is precisely the matching contract. Fresh maps allow the same symbol to represent different numbers in separate windows. Append coordinates during enumeration so output is already ordered. No rotated, reflected or resized candidate is considered. For R by C grid and h by w pattern, time is O(max(0,R-h+1)max(0,C-w+1)hw) expected and per-window auxiliary state O(hw), bounded further by the alphabet. Oversized patterns naturally enumerate no windows.

• Time complexity: O(max(0,R-h+1) * max(0,C-w+1) * h * w) expected
• Space complexity: O(h * w) auxiliary entries plus output