Skip to main content
Talentd

Match Alphanumerical Pattern in Matrix I - Solution & Explanation

MediumPremiumFree on FleetCodeArrayHash TableStringMatrix12 min readAsked at: Visa, Uber
Practice this problem

Problem Statement

You are given a 2D integer matrix board and a 2D character matrix pattern. Where 0 <= board[r][c] <= 9 and each element of pattern is either a digit or a lowercase English letter.

Your task is to find a submatrix of board that matches pattern.

An integer matrix part matches pattern if we can replace cells containing letters in pattern with some digits (each distinct letter with a unique digit) in such a way that the resulting matrix becomes identical to the integer matrix part. In other words,

  • The matrices have identical dimensions.
  • If pattern[r][c] is a digit, then part[r][c] must be the same digit.
  • If pattern[r][c] is a letter x:
    • For every pattern[i][j] == x, part[i][j] must be the same as part[r][c].
    • For every pattern[i][j] != x, part[i][j] must be different than part[r][c].

Return an array of length 2 containing the row number and column number of the upper-left corner of a submatrix of board which matches pattern. If there is more than one such submatrix, return the coordinates of the submatrix with the lowest row index, and in case there is still a tie, return the coordinates of the submatrix with the lowest column index. If there are no suitable answers, return [-1, -1].

 

Example 1:

1 2 2
2 2 3
2 3 3
a b
b b

Input: board = [[1,2,2],[2,2,3],[2,3,3]], pattern = ["ab","bb"]

Output: [0,0]

Explanation: If we consider this mapping: "a" -> 1 and "b" -> 2; the submatrix with the upper-left corner (0,0) is a match as outlined in the matrix above.

Note that the submatrix with the upper-left corner (1,1) is also a match but since it comes after the other one, we return [0,0].

Example 2:

1 1 2
3 3 4
6 6 6
a b
6 6

Input: board = [[1,1,2],[3,3,4],[6,6,6]], pattern = ["ab","66"]

Output: [1,1]

Explanation: If we consider this mapping: "a" -> 3 and "b" -> 4; the submatrix with the upper-left corner (1,1) is a match as outlined in the matrix above.

Note that since the corresponding values of "a" and "b" must differ, the submatrix with the upper-left corner (1,0) is not a match. Hence, we return [1,1].

Example 3:

1 2
2 1
x x

Input: board = [[1,2],[2,1]], pattern = ["xx"]

Output: [-1,-1]

Explanation: Since the values of the matched submatrix must be the same, there is no match. Hence, we return [-1,-1].

 

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 either a digit represented as a string or a lowercase English letter.

Approach Overview

Problem Overview: You are given a character matrix and an alphanumerical pattern string. The goal is to determine whether the pattern can match a contiguous segment in any row of the matrix such that the mapping between pattern characters and matrix characters is consistent. Each symbol in the pattern must map to exactly one matrix character, and different symbols cannot map to the same character.

Approach 1: Enumeration with Bidirectional Hash Mapping (O(m * n * k) time, O(k) space)

The direct strategy is to enumerate every possible starting position in the matrix where the pattern could fit. For each row i and column j, attempt to match the pattern against the substring of length k. While scanning the characters, maintain two hash tables: one mapping pattern symbols to matrix characters and another mapping matrix characters back to pattern symbols. This enforces a bijection so that repeated pattern symbols always map to the same matrix character and no two pattern symbols map to the same value.

During verification, iterate through the pattern and the candidate substring simultaneously. On each step, check the mapping in both hash tables. If a conflict appears, stop early and move to the next starting position. If the entire pattern is processed without conflicts, a valid match exists and the search can terminate.

This approach works well because the pattern length is typically much smaller than the total matrix size. The algorithm performs a bounded verification for each candidate position. The logic is straightforward and relies heavily on fast hash lookups.

From a structural perspective, the solution combines iteration over a matrix, substring comparison from string processing, and hash-based consistency checks. The key insight is enforcing the bijection using two maps rather than one, which guarantees correctness even when repeated characters appear in either the pattern or the matrix segment.

Recommended for interviews: The enumeration with bidirectional hash maps is the expected approach. A brute-force comparison without mapping fails when repeated pattern symbols must correspond to the same character. Demonstrating the bijection using two hash tables shows solid understanding of pattern matching problems and is the standard technique interviewers look for.

Solution

Let's denote m and n as the number of rows and columns in the matrix board, and r and c as the number of rows and columns in the matrix pattern.

We can enumerate each possible sub-matrix's top-left position (i, j) in the board from small to large, and then determine whether the r times c sub-matrix with (i, j) as the top-left corner matches pattern. If we find a matching sub-matrix, we return (i, j). Otherwise, we return (-1, -1).

The time complexity is O(m times n times r times c), where m and n are the number of rows and columns in the matrix board, and r and c are the number of rows and columns in the matrix pattern. The space complexity is O(|\Sigma|), where \Sigma is the character set. In this problem, \Sigma includes numbers and lowercase letters, so |\Sigma| leq 36.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Naive substring comparisonO(m * n * k)O(1)When pattern uniqueness constraints are ignored or for quick baseline testing
Enumeration with bidirectional hash mapsO(m * n * k)O(k)General solution ensuring a bijection between pattern symbols and matrix characters

Video Solution

3078. Match Alphanumerical Pattern in Matrix I (Leetcode Medium) • Programming Live with Larry • 427 views views

Frequently Asked Questions

Is Match Alphanumerical Pattern in Matrix I easy or hard?
Match Alphanumerical Pattern in Matrix I is considered a Medium difficulty problem. The main challenge is recognizing the need for a bijective mapping and implementing it correctly with hash tables. Once the mapping logic is clear, the rest of the algorithm is straightforward enumeration.
Match Alphanumerical Pattern in Matrix I Python/Java solution
The solution is straightforward to implement in Python, Java, C++, Go, or TypeScript. Each implementation iterates over matrix positions and uses hash maps or dictionaries to track the pattern-character mapping. The verification loop processes the pattern and candidate substring simultaneously.
How to solve Match Alphanumerical Pattern in Matrix I in O(n)?
A strict O(n) solution is generally not achievable because each possible starting position in the matrix must be validated against the pattern. The practical approach is O(m * n * k) using enumeration with hash maps. Each candidate segment is checked once with constant-time hash lookups for mapping validation.
What is the best approach for Match Alphanumerical Pattern in Matrix I?
The most effective approach is enumeration combined with bidirectional hash table mapping. For each possible starting position in the matrix, compare the pattern with the candidate substring while maintaining two maps to enforce a one‑to‑one relationship. This ensures repeated pattern symbols consistently map to the same matrix character. The overall complexity is O(m * n * k).
Is Match Alphanumerical Pattern in Matrix I asked at Google/Amazon/Meta?
Problems involving pattern matching with bijective mappings frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of this problem test understanding of hash tables, string matching, and constraint validation. The core idea is similar to word pattern or isomorphic string problems.
What data structure is used in Match Alphanumerical Pattern in Matrix I?
The solution primarily uses hash tables (hash maps) to maintain the mapping between pattern symbols and matrix characters. Two maps are typically used to enforce a bijection: pattern-to-character and character-to-pattern. The matrix itself is traversed using standard array iteration.
What is the time complexity of Match Alphanumerical Pattern in Matrix I?
The typical solution runs in O(m * n * k) time, where m is the number of rows, n is the number of columns, and k is the length of the pattern. Every possible starting position in the matrix is checked, and verifying a match requires scanning the pattern once. Hash table lookups keep each verification step constant time.

Ready to solve this problem?

Practice Match Alphanumerical Pattern in Matrix I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays