3078. Match Alphanumerical Pattern in Matrix I
Asked at Roblox
Difficulty
Medium
Time
O(R * C * r * c)
Space
O(1)
Pattern
Array
Companies
1
Problem
You get a grid of digits called board and a smaller grid called pattern. Each cell of pattern is either a digit character (like "3") or a lowercase letter (like "a").
You must find a submatrix of board — a rectangular block of the same height and width as pattern — that matches pattern. A block matches when you can give every letter in pattern one digit, so that the block becomes exactly equal to pattern after the swap. Two rules make this strict: the same letter must always get the same digit, and two different letters must get different digits. Also, a letter's digit must not equal the value of any digit cell in the pattern.
Return [row, col], the top-left corner of a matching block. If several blocks match, pick the one with the smallest row index; if there is still a tie, pick the smallest column index. If nothing matches, return [-1, -1].
Find the first matching block
Constraints
- ●
1 <= board.length <= 50 - ●
1 <= board[i].length <= 50 - ●
0 <= board[i][j] <= 9 - ●
1 <= pattern.length <= 50 - ●
1 <= pattern[i].length <= 50 - ●
pattern[i][j] is a digit character or a lowercase English letter
Examples
board = [[1,2,2],[2,2,3],[2,3,3]], pattern = ["ab","bb"][0,0]board = [[1,1,2],[3,3,4],[6,6,6]], pattern = ["ab","66"][1,1]board = [[1,2],[2,1]], pattern = ["xx"][-1,-1]Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Roblox | Medium | View all Roblox questions → |
How to Think About It
Board and pattern are at most 50x50, so trying every placement and checking every cell is fast enough.
For a placement, keep two maps: letter -> digit and digit -> letter. A letter cell must agree with its existing mapping, and its digit must not already belong to a different letter.
Digit cells must equal the board value exactly.
The subtle rule: a letter's digit must be different from the value of every non-letter cell too. So after mapping letters, reject the placement if any digit cell's value is also used by a letter.
Scan placements row by row, then column by column, and return the first match; that satisfies the tie-breaking rule.
Optimal Approach
Step 1: For each top-left (r, c) in row-major order:
l2d = {}, d2l = {}, digits = set(), ok = true.
For each pattern cell (i, j) with board value v:
If the pattern char is a digit: require v == digit; add v to digits.
Else (letter x): require l2d[x] (if set) == v and d2l[v] (if set) == x; record both.
Also require that no value in digits is a key of d2l.
If all checks pass, return [r, c].
Step 2: Return [-1, -1].
Time: O(R * C * r * c). Space: O(1) (at most 10 digits and 26 letters).
Check each placement with two maps
What Trips People Up in Real Interviews
Checking only that each letter maps consistently. Different letters must map to different digits (the reverse map).
Missing the rule that a letter's digit must differ from the pattern's literal digits.
Returning the last match instead of the first in row-major order.
Reusing maps across placements — each placement starts fresh.
Solution Code
O(R * C * r * c) timedef findPattern(board, pattern):
R, C = len(board), len(board[0])
r, c = len(pattern), len(pattern[0])
for top in range(R - r + 1):
for left in range(C - c + 1):
l2d, d2l, digits = {}, {}, set()
ok = True
for i in range(r):
for j in range(c):
v = board[top + i][left + j]
ch = pattern[i][j]
if ch.isdigit():
if v != int(ch):
ok = False
break
digits.add(v)
else:
if l2d.get(ch, v) != v or d2l.get(v, ch) != ch:
ok = False
break
l2d[ch] = v
d2l[v] = ch
if not ok:
break
if ok and not (digits & d2l.keys()):
return [top, left]
return [-1, -1]Frequently Asked Questions
What is the Match Alphanumerical Pattern in Matrix I problem?
Match Alphanumerical Pattern in Matrix I asks for the top-left corner of the first submatrix of a digit board that matches a pattern of digits and letters. Digit cells must match exactly; each letter stands for one digit, different letters stand for different digits, and a letter's digit must also differ from every digit cell in the pattern. It is a careful brute force over every placement.
How do you solve Match Alphanumerical Pattern in Matrix I?
The optimal approach runs in O(R * C * r * c) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Match Alphanumerical Pattern in Matrix I?
Match Alphanumerical Pattern in Matrix I is asked at Roblox. It is a medium difficulty problem.
What are common mistakes on Match Alphanumerical Pattern in Matrix I?
- Checking only that each letter maps consistently. Different letters must map to different digits (the reverse map).
- Missing the rule that a letter's digit must differ from the pattern's literal digits.
- Returning the last match instead of the first in row-major order.
- Reusing maps across placements — each placement starts fresh.