LeetCode Problem 3078

Difficulty: 🟡 Medium
Topics: Array, Hash Table, String, Matrix

Solution

LeetCode 3078 - Match Alphanumerical Pattern in Matrix I

Problem Understanding

This problem asks us to search for a rectangular submatrix inside a larger integer matrix, where the submatrix follows a pattern described by digits and lowercase letters.

The input consists of:

• board, a 2D matrix of integers from 0 to 9
• pattern, a 2D matrix represented as an array of strings

The dimensions of the submatrix we search for must exactly match the dimensions of pattern.

The matching rules are the core of the problem:

• If a cell in pattern contains a digit character like '3', then the corresponding cell in the submatrix must contain exactly the integer 3.
• If a cell contains a lowercase letter like 'a', then that letter represents some digit.
• Every occurrence of the same letter must map to the same digit.
• Different letters must map to different digits.

This means the mapping between letters and digits must be one-to-one.

For example, suppose the pattern is:

ab
bb

Then:

• all 'b' positions must contain the same number
• 'a' must contain a different number from 'b'

The problem asks us to return the coordinates [row, col] of the top-left corner of the first matching submatrix. The search order is:

1. smallest row index
2. smallest column index if rows tie

If no valid submatrix exists, we return [-1, -1].

The constraints are fairly small:

• board dimensions are at most 50 x 50
• pattern dimensions are at most 50 x 50

Even though the matrices are small, a naive implementation can still perform unnecessary repeated work if it does not carefully validate mappings.

Several edge cases are important:

• Multiple letters mapping to the same digit must be rejected.
• Repeated occurrences of the same letter must remain consistent.
• Digit characters inside the pattern must match exactly.
• The pattern may be the same size as the entire board.
• No valid submatrix may exist.
• The board may contain many repeated digits, which can easily expose incorrect bijection handling.

Approaches

Brute Force Approach

The brute force solution checks every possible submatrix position in board that could fit the pattern dimensions.

For each candidate position:

1. Extract the corresponding submatrix.
2. Attempt to build mappings between letters and digits.
3. Validate every cell one by one.

To enforce the one-to-one relationship correctly, we must maintain:

• a mapping from letter → digit
• a reverse mapping from digit → letter

If either mapping becomes inconsistent, the candidate fails.

This approach is correct because every possible valid placement is examined exhaustively. If a matching submatrix exists, brute force will eventually find it.

However, without careful implementation, this can become inefficient because:

• each candidate repeatedly scans the entire pattern
• mappings are rebuilt from scratch every time

Still, given the constraints, this solution is acceptable.

Key Insight for the Optimal Approach

The important observation is that the pattern dimensions are small enough that we can efficiently validate each candidate submatrix directly, but we must do so with early termination and constant-time consistency checks.

The optimal solution still enumerates all possible starting positions, but:

• it immediately rejects invalid candidates as soon as a mismatch appears
• it uses two hash maps to maintain a bijection efficiently

The two-way mapping is the key idea:

• letter_to_digit
• digit_to_letter

This guarantees:

• repeated letters remain consistent
• different letters never share the same digit

Since every cell is processed only once per candidate, the implementation remains efficient enough for the constraints.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O((R - PR + 1) × (C - PC + 1) × PR × PC)	O(1) to O(26)	Checks every candidate submatrix directly
Optimal	O((R - PR + 1) × (C - PC + 1) × PR × PC)	O(1)	Uses bidirectional hash maps with early rejection

Although the asymptotic complexity is the same, the optimized implementation performs significantly fewer unnecessary operations because mismatches terminate validation immediately.

Algorithm Walkthrough

1. Compute the dimensions of both matrices.

Let:

• rows, cols be the dimensions of board
• p_rows, p_cols be the dimensions of pattern

Any valid submatrix must have exactly the same dimensions as the pattern. 2. Iterate over every possible top-left corner.

The largest valid starting row is:

rows - p_rows

and similarly for columns.

For each candidate (start_row, start_col), we attempt to validate the pattern. 3. Create two hash maps.

We use:

• letter_to_digit
• digit_to_letter

The first ensures consistency for repeated letters.

The second ensures uniqueness across different letters. 4. Traverse every cell in the pattern.

For each pattern cell:

• read the corresponding board value
• inspect the pattern character

5. Handle digit characters.

If the pattern character is a digit:

• convert it to an integer
• compare directly with the board value

If they differ, the candidate fails immediately. 6. Handle letter characters.

If the character is a lowercase letter:

• check whether the letter already has an assigned digit
• if yes, verify consistency
• otherwise create a new mapping

At the same time:

• verify the digit is not already assigned to another letter

7. Reject invalid candidates immediately.

As soon as any rule fails:

• stop processing this candidate
• move to the next starting position

Early termination avoids unnecessary work. 8. Return the first valid position.

Because we iterate row-first and then column-first, the first successful candidate automatically satisfies the tie-breaking requirement. 9. Return [-1, -1] if no match exists.

Why it works

The algorithm explicitly enforces all matching rules:

• digit cells must match exactly
• repeated letters must map consistently
• different letters must map to different digits

The two-way mapping guarantees a valid bijection between letters and digits. Since every possible submatrix position is examined in row-major order, the first valid match returned is guaranteed to be the lexicographically smallest valid coordinate.

Python Solution

from typing import List

class Solution:
    def findPattern(self, board: List[List[int]], pattern: List[str]) -> List[int]:
        rows = len(board)
        cols = len(board[0])

        p_rows = len(pattern)
        p_cols = len(pattern[0])

        def matches(start_row: int, start_col: int) -> bool:
            letter_to_digit = {}
            digit_to_letter = {}

            for r in range(p_rows):
                for c in range(p_cols):
                    ch = pattern[r][c]
                    value = board[start_row + r][start_col + c]

                    if ch.isdigit():
                        if value != int(ch):
                            return False
                    else:
                        if ch in letter_to_digit:
                            if letter_to_digit[ch] != value:
                                return False
                        else:
                            if value in digit_to_letter:
                                return False

                            letter_to_digit[ch] = value
                            digit_to_letter[value] = ch

            return True

        for row in range(rows - p_rows + 1):
            for col in range(cols - p_cols + 1):
                if matches(row, col):
                    return [row, col]

        return [-1, -1]

The implementation begins by computing the dimensions of both the board and the pattern. This allows us to determine every valid starting location for a candidate submatrix.

The helper function matches performs the actual validation for one candidate position. Inside this function, two dictionaries are created:

• letter_to_digit
• digit_to_letter

These dictionaries enforce the bijection requirement.

The nested loops iterate through every pattern cell. For each cell:

• if the pattern character is numeric, we compare directly against the board value
• otherwise we validate or create the letter-digit mapping

Whenever an inconsistency appears, the function immediately returns False. This early rejection improves efficiency substantially.

The outer loops enumerate candidate positions in row-major order. Therefore, the first valid answer automatically satisfies the required tie-breaking rules.

If no candidate matches, the algorithm returns [-1, -1].

Go Solution

func findPattern(board [][]int, pattern []string) []int {
	rows := len(board)
	cols := len(board[0])

	pRows := len(pattern)
	pCols := len(pattern[0])

	matches := func(startRow, startCol int) bool {
		letterToDigit := make(map[byte]int)
		digitToLetter := make(map[int]byte)

		for r := 0; r < pRows; r++ {
			for c := 0; c < pCols; c++ {
				ch := pattern[r][c]
				value := board[startRow+r][startCol+c]

				if ch >= '0' && ch <= '9' {
					if value != int(ch-'0') {
						return false
					}
				} else {
					if mappedValue, exists := letterToDigit[ch]; exists {
						if mappedValue != value {
							return false
						}
					} else {
						if _, exists := digitToLetter[value]; exists {
							return false
						}

						letterToDigit[ch] = value
						digitToLetter[value] = ch
					}
				}
			}
		}

		return true
	}

	for row := 0; row <= rows-pRows; row++ {
		for col := 0; col <= cols-pCols; col++ {
			if matches(row, col) {
				return []int{row, col}
			}
		}
	}

	return []int{-1, -1}
}

The Go implementation follows exactly the same algorithmic structure as the Python version.

A few Go-specific details are worth noting:

• Go strings are indexed as bytes, which works correctly here because the pattern contains only ASCII characters.
• Maps are explicitly initialized using make.
• Character digit conversion uses:

int(ch - '0')

• Go does not support nested named functions directly in the same way as Python, so we use a closure assigned to matches.

No integer overflow concerns exist because all board values are between 0 and 9.

Worked Examples

Example 1

board =
[
  [1,2,2],
  [2,2,3],
  [2,3,3]
]

pattern =
[
  "ab",
  "bb"
]

We first test the submatrix starting at (0,0):

1 2
2 2

Traversal state:

Position	Pattern Char	Board Value	letter_to_digit	digit_to_letter	Result
(0,0)	a	1	{a:1}	{1:a}	valid
(0,1)	b	2	{a:1,b:2}	{1:a,2:b}	valid
(1,0)	b	2	unchanged	unchanged	valid
(1,1)	b	2	unchanged	unchanged	valid

All constraints hold, so we return:

[0,0]

Example 2

board =
[
  [1,1,2],
  [3,3,4],
  [6,6,6]
]

pattern =
[
  "ab",
  "66"
]

First candidate: (0,0)

Submatrix:

1 1
3 3

Processing:

Position	Pattern Char	Board Value	State	Result
(0,0)	a	1	a→1	valid
(0,1)	b	1	digit 1 already used	invalid

This fails because different letters cannot map to the same digit.

Next candidate: (1,1)

Submatrix:

3 4
6 6

Processing:

Position	Pattern Char	Board Value	State	Result
(0,0)	a	3	a→3	valid
(0,1)	b	4	b→4	valid
(1,0)	6	6	exact match	valid
(1,1)	6	6	exact match	valid

This succeeds, so we return:

[1,1]

Example 3

board =
[
  [1,2],
  [2,1]
]

pattern =
[
  "xx"
]

Only candidate:

1 2

Processing:

Position	Pattern Char	Board Value	State	Result
(0,0)	x	1	x→1	valid
(0,1)	x	2	expected 1	invalid

The repeated letter maps inconsistently, so no valid match exists.

Return:

[-1,-1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O((R - PR + 1) × (C - PC + 1) × PR × PC)	Every candidate submatrix scans the entire pattern once
Space	O(1)	Hash maps store at most 26 letter mappings and 10 digit mappings

The algorithm examines every valid starting position in the board. For each position, it may scan the entire pattern matrix once. Since the alphabet and digit range are bounded by constants, the auxiliary space remains constant.

Test Cases

from typing import List

class Solution:
    def findPattern(self, board: List[List[int]], pattern: List[str]) -> List[int]:
        rows = len(board)
        cols = len(board[0])

        p_rows = len(pattern)
        p_cols = len(pattern[0])

        def matches(start_row: int, start_col: int) -> bool:
            letter_to_digit = {}
            digit_to_letter = {}

            for r in range(p_rows):
                for c in range(p_cols):
                    ch = pattern[r][c]
                    value = board[start_row + r][start_col + c]

                    if ch.isdigit():
                        if value != int(ch):
                            return False
                    else:
                        if ch in letter_to_digit:
                            if letter_to_digit[ch] != value:
                                return False
                        else:
                            if value in digit_to_letter:
                                return False

                            letter_to_digit[ch] = value
                            digit_to_letter[value] = ch

            return True

        for row in range(rows - p_rows + 1):
            for col in range(cols - p_cols + 1):
                if matches(row, col):
                    return [row, col]

        return [-1, -1]

sol = Solution()

# Example 1
assert sol.findPattern(
    [[1,2,2],[2,2,3],[2,3,3]],
    ["ab","bb"]
) == [0,0]  # basic valid mapping

# Example 2
assert sol.findPattern(
    [[1,1,2],[3,3,4],[6,6,6]],
    ["ab","66"]
) == [1,1]  # distinct letters must map differently

# Example 3
assert sol.findPattern(
    [[1,2],[2,1]],
    ["xx"]
) == [-1,-1]  # repeated letter mismatch

# Single cell exact digit match
assert sol.findPattern(
    [[5]],
    ["5"]
) == [0,0]  # simplest possible valid case

# Single cell digit mismatch
assert sol.findPattern(
    [[5]],
    ["3"]
) == [-1,-1]  # simplest invalid case

# Entire board used as pattern
assert sol.findPattern(
    [[1,2],[2,1]],
    ["ab","ba"]
) == [0,0]  # whole board match

# Different letters cannot share digit
assert sol.findPattern(
    [[1,1]],
    ["ab"]
) == [-1,-1]  # bijection violation

# Repeated letter consistency
assert sol.findPattern(
    [[7,7]],
    ["aa"]
) == [0,0]  # repeated letter valid

# Prefer smallest row then column
assert sol.findPattern(
    [[1,2,1,2]],
    ["ab"]
) == [0,0]  # first valid occurrence returned

# Pattern larger than possible valid match
assert sol.findPattern(
    [[1,2],[3,4]],
    ["aaa","aaa"]
) == [-1,-1]  # impossible dimensions

# Mixed digits and letters
assert sol.findPattern(
    [[3,4],[6,6]],
    ["ab","66"]
) == [0,0]  # digits and mappings together

# Multiple repeated letters
assert sol.findPattern(
    [[5,6,5]],
    ["aba"]
) == [0,0]  # repeated mapping across row

Test Summary

Test	Why
Example 1	Valid repeated-letter mapping
Example 2	Ensures distinct letters map differently
Example 3	Detects inconsistent repeated letters
Single cell match	Minimum valid input
Single cell mismatch	Minimum invalid input
Entire board match	Pattern equals board dimensions
Different letters same digit	Tests bijection enforcement
Repeated identical letter	Valid consistency case
Multiple valid matches	Confirms lexicographically smallest result
Oversized pattern	Impossible placement case
Mixed digits and letters	Tests both rule types together
Repeated pattern structure	Verifies consistency across positions

Edge Cases

Different Letters Mapping to the Same Digit

A very common bug is checking only whether repeated letters remain consistent, while forgetting to enforce uniqueness between different letters.

For example:

pattern = "ab"
submatrix = [1,1]

A naive implementation might allow:

• a -> 1
• b -> 1

But this violates the one-to-one mapping rule.

The implementation avoids this by maintaining the reverse map digit_to_letter. Before assigning a digit to a new letter, it verifies that the digit has not already been assigned elsewhere.

Repeated Letter Appearing Multiple Times

Another important edge case occurs when the same letter appears in multiple positions.

Example:

pattern = "xx"
submatrix = [1,2]

The first occurrence maps:

x -> 1

The second occurrence must also be 1. Since it is 2, the candidate is rejected immediately.

The implementation handles this by storing the mapping in letter_to_digit and checking consistency every time the letter reappears.

Digit Characters Inside the Pattern

Pattern cells containing numeric characters behave differently from letters. They do not participate in mappings and must match exactly.

Example:

pattern = "66"
submatrix = [6,5]

Even though mappings are irrelevant here, the second cell fails because:

5 != 6

The implementation correctly distinguishes digits using isdigit() in Python and ASCII range checks in Go. Numeric pattern cells are compared directly against board values without involving the hash maps.