Match Alphanumerical Pattern in Matrix I
Asked at Roblox
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.
Asked At
| 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).
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
def 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.