Facebook Pixel

3078. Match Alphanumerical Pattern in Matrix I

MediumArrayHash TableStringMatrix
Leetcode Link

Problem Description

You have two 2D matrices: board (containing integers 0-9) and pattern (containing digits and lowercase letters). Your goal is to find a submatrix within board that matches the pattern.

A submatrix matches the pattern if you can map each distinct letter in the pattern to a unique digit such that:

  1. Both matrices have the same dimensions (same number of rows and columns)

  2. For digit characters in pattern: If pattern[r][c] contains a digit, then the corresponding position in the submatrix part[r][c] must have that exact same digit

  3. For letter characters in pattern: Each distinct letter must map to exactly one digit, and this mapping must be consistent:

    • All occurrences of the same letter must map to the same digit
    • Different letters must map to different digits
    • For example, if letter 'a' maps to digit 5, then every position with 'a' in the pattern must have 5 in the corresponding submatrix position

The task is to find such a matching submatrix in board and return the coordinates [row, column] of its upper-left corner. If multiple matches exist, return the one with:

  • The smallest row index first
  • If row indices are equal, the smallest column index

If no matching submatrix exists, return [-1, -1].

Example: If pattern is [['a','b'], ['b','a']] and we find a 2×2 submatrix [[3,7], [7,3]] in board, this would be a match because we can map 'a'→3 and 'b'→7 consistently throughout the pattern.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

Since we need to find a submatrix in board that matches the pattern, the most straightforward approach is to try every possible position where the pattern could fit within the board.

Think of it like sliding a window (the pattern) across the board. At each valid position, we check if the current submatrix matches our pattern. The key insight is that we only need to check positions where the pattern can fully fit - that is, positions (i, j) where i + pattern_rows <= board_rows and j + pattern_cols <= board_cols.

For each candidate position, we need to verify the matching rules. The challenge is handling the letter-to-digit mapping. We realize we need bidirectional mapping:

  • Forward mapping (d1): Maps each letter to its corresponding digit. This ensures that the same letter always maps to the same digit.
  • Reverse mapping (d2): Maps each digit back to its letter. This ensures that different letters don't map to the same digit.

Why do we need both mappings? Consider pattern [['a', 'b']] and submatrix [[5, 5]]. Without reverse mapping, we might incorrectly map both 'a'→5 and 'b'→5, violating the uniqueness constraint.

The checking process for each position follows these rules:

  1. If the pattern has a digit at position [a][b], the board must have the exact same digit at the corresponding position
  2. If the pattern has a letter, we either establish a new mapping (if we haven't seen this letter before) or verify the existing mapping is consistent
  3. We also check that no two different letters map to the same digit using the reverse mapping

By iterating through positions in row-major order (left to right, top to bottom), we naturally find the lexicographically smallest valid position first, satisfying the problem's tie-breaking requirements.

Solution Approach

The solution implements a brute-force approach with efficient pattern matching validation.

Main Algorithm Structure:

  1. Outer loops for enumeration: We iterate through all valid starting positions (i, j) in the board where a submatrix of size r × c can fit:

    • i ranges from 0 to m - r (inclusive)
    • j ranges from 0 to n - c (inclusive)

  2. Pattern matching validation: For each candidate position (i, j), we call the check(i, j) function to verify if the submatrix starting at that position matches the pattern.

The check function implementation:

The function uses two dictionaries to maintain the bidirectional mapping:

  • d1: Maps pattern letters → board digits
  • d2: Maps board digits → pattern letters

For each cell (a, b) in the pattern:

  1. Calculate the corresponding position in the board: (x, y) = (i + a, j + b)

  2. If the pattern cell contains a digit:

    • Simply verify that int(pattern[a][b]) == board[x][y]
    • Return False if they don't match

  3. If the pattern cell contains a letter:

    • Check if this letter already has a mapping in d1:
      • If yes and the mapped value differs from board[x][y], return False
    • Check if the board value already has a mapping in d2:
      • If yes and the mapped letter differs from pattern[a][b], return False
    • If both checks pass, establish/update the mappings:
      • d1[pattern[a][b]] = board[x][y]
      • d2[board[x][y]] = pattern[a][b]

Why the dual dictionary approach works:

  • d1 ensures consistency: same letter always maps to same digit
  • d2 ensures uniqueness: different letters can't map to same digit

Time Complexity: O((m-r+1) × (n-c+1) × r × c) where we check at most (m-r+1) × (n-c+1) positions, and each check takes O(r × c) time.

Space Complexity: O(1) since the dictionaries can hold at most 26 letters and 10 digits.

The algorithm returns [i, j] for the first matching position found (which is lexicographically smallest due to our iteration order), or [-1, -1] if no match exists.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Given:

  • board = [[1,2,2], [2,2,3], [3,3,3]]
  • pattern = [['a','b'], ['b','b']]

We need to find a 2×2 submatrix in board that matches the pattern.

Step 1: Try position (0, 0)

  • Submatrix: [[1,2], [2,2]]
  • Initialize empty mappings: d1 = {}, d2 = {}
  • Check pattern[0][0] = 'a' against board[0][0] = 1:
    • 'a' not in d1, 1 not in d2
    • Set d1['a'] = 1, d2[1] = 'a'
  • Check pattern[0][1] = 'b' against board[0][1] = 2:
    • 'b' not in d1, 2 not in d2
    • Set d1['b'] = 2, d2[2] = 'b'
  • Check pattern[1][0] = 'b' against board[1][0] = 2:
    • 'b' in d1, d1['b'] = 2 ✓ (matches board[1][0])
  • Check pattern[1][1] = 'b' against board[1][1] = 2:
    • 'b' in d1, d1['b'] = 2 ✓ (matches board[1][1])
  • Match found! Return [0, 0]

Step 2: Verify our understanding with position (0, 1)

  • Submatrix: [[2,2], [2,3]]
  • Initialize: d1 = {}, d2 = {}
  • Check pattern[0][0] = 'a' against board[0][1] = 2:
    • Set d1['a'] = 2, d2[2] = 'a'
  • Check pattern[0][1] = 'b' against board[0][2] = 2:
    • 'b' not in d1, but 2 already in d2!
    • d2[2] = 'a' ≠ 'b'
    • Failed! Different letters can't map to same digit

Step 3: Try position (1, 0)

  • Submatrix: [[2,2], [3,3]]
  • Initialize: d1 = {}, d2 = {}
  • Check pattern[0][0] = 'a' against board[1][0] = 2:
    • Set d1['a'] = 2, d2[2] = 'a'
  • Check pattern[0][1] = 'b' against board[1][1] = 2:
    • 'b' not in d1, but 2 already in d2!
    • d2[2] = 'a' ≠ 'b'
    • Failed!

Since we already found a match at position (0, 0), and we iterate in lexicographic order, the answer is [0, 0].

This example demonstrates:

  1. How we systematically check each valid position
  2. The importance of bidirectional mapping (d1 and d2)
  3. How d2 prevents different letters from mapping to the same digit
  4. Why the first match found is the lexicographically smallest solution

Solution Implementation

1class Solution:
2    def findPattern(self, board: List[List[int]], pattern: List[str]) -> List[int]:
3        """
4        Find the top-left position of a pattern in the board.
5        Pattern can contain digits (exact match) or letters (variable match with bijection).
6
7        Args:
8            board: 2D list of integers representing the board
9            pattern: 2D list of strings representing the pattern to find
10
11        Returns:
12            List containing [row, col] of top-left corner if pattern found, else [-1, -1]
13        """
14
15        def check_pattern_at_position(start_row: int, start_col: int) -> bool:
16            """
17            Check if the pattern matches the board starting at given position.
18
19            Args:
20                start_row: Starting row index in the board
21                start_col: Starting column index in the board
22
23            Returns:
24                True if pattern matches at this position, False otherwise
25            """
26            # Dictionary to map pattern characters to board values
27            pattern_to_board = {}
28            # Dictionary to map board values to pattern characters (ensure bijection)
29            board_to_pattern = {}
30
31            # Iterate through each cell in the pattern
32            for pattern_row in range(pattern_rows):
33                for pattern_col in range(pattern_cols):
34                    # Calculate corresponding board position
35                    board_row = start_row + pattern_row
36                    board_col = start_col + pattern_col
37
38                    current_pattern_cell = pattern[pattern_row][pattern_col]
39                    current_board_value = board[board_row][board_col]
40
41                    # Check if pattern cell is a digit (exact match required)
42                    if current_pattern_cell.isdigit():
43                        if int(current_pattern_cell) != current_board_value:
44                            return False
45                    else:
46                        # Pattern cell is a letter (variable match with consistent mapping)
47
48                        # Check if this pattern character was already mapped to a different value
49                        if (current_pattern_cell in pattern_to_board and
50                            pattern_to_board[current_pattern_cell] != current_board_value):
51                            return False
52
53                        # Check if this board value was already mapped to a different character
54                        if (current_board_value in board_to_pattern and
55                            board_to_pattern[current_board_value] != current_pattern_cell):
56                            return False
57
58                        # Store the bidirectional mapping
59                        pattern_to_board[current_pattern_cell] = current_board_value
60                        board_to_pattern[current_board_value] = current_pattern_cell
61
62            return True
63
64        # Get dimensions of board and pattern
65        board_rows, board_cols = len(board), len(board[0])
66        pattern_rows, pattern_cols = len(pattern), len(pattern[0])
67
68        # Try each possible starting position where pattern can fit
69        for row in range(board_rows - pattern_rows + 1):
70            for col in range(board_cols - pattern_cols + 1):
71                if check_pattern_at_position(row, col):
72                    return [row, col]
73
74        # Pattern not found in board
75        return [-1, -1]
76
1class Solution {
2    /**
3     * Finds the top-left corner position of a pattern in a 2D board.
4     * @param board 2D integer array representing the board
5     * @param pattern String array representing the pattern to search for
6     * @return Array containing [row, column] of pattern's top-left corner, or [-1, -1] if not found
7     */
8    public int[] findPattern(int[][] board, String[] pattern) {
9        int boardRows = board.length;
10        int boardCols = board[0].length;
11        int patternRows = pattern.length;
12        int patternCols = pattern[0].length();
13
14        // Try each possible starting position in the board
15        for (int startRow = 0; startRow <= boardRows - patternRows; startRow++) {
16            for (int startCol = 0; startCol <= boardCols - patternCols; startCol++) {
17                // Check if pattern matches at this position
18                if (isPatternMatch(board, pattern, startRow, startCol)) {
19                    return new int[] {startRow, startCol};
20                }
21            }
22        }
23
24        // Pattern not found in board
25        return new int[] {-1, -1};
26    }
27
28    /**
29     * Checks if the pattern matches the board starting at given position.
30     * Pattern can contain:
31     * - Digits (0-9): must match exactly with board value
32     * - Letters (a-z): act as variables that can map to any board value (bijective mapping)
33     *
34     * @param board The game board
35     * @param pattern The pattern to match
36     * @param startRow Starting row position in board
37     * @param startCol Starting column position in board
38     * @return true if pattern matches at this position, false otherwise
39     */
40    private boolean isPatternMatch(int[][] board, String[] pattern, int startRow, int startCol) {
41        // Mapping from pattern letters (a-z) to board values
42        int[] letterToBoardValue = new int[26];
43        // Mapping from board values (0-9) to pattern letters
44        int[] boardValueToLetter = new int[10];
45
46        // Initialize mappings with -1 (indicating no mapping exists yet)
47        Arrays.fill(letterToBoardValue, -1);
48        Arrays.fill(boardValueToLetter, -1);
49
50        // Check each cell in the pattern
51        for (int patternRow = 0; patternRow < pattern.length; patternRow++) {
52            for (int patternCol = 0; patternCol < pattern[0].length(); patternCol++) {
53                // Calculate corresponding board position
54                int boardRow = startRow + patternRow;
55                int boardCol = startCol + patternCol;
56                char patternChar = pattern[patternRow].charAt(patternCol);
57
58                if (Character.isDigit(patternChar)) {
59                    // Pattern contains a digit - must match exactly
60                    int expectedValue = patternChar - '0';
61                    if (expectedValue != board[boardRow][boardCol]) {
62                        return false;
63                    }
64                } else {
65                    // Pattern contains a letter - check bijective mapping
66                    int letterIndex = patternChar - 'a';
67                    int boardValue = board[boardRow][boardCol];
68
69                    // Check if letter already mapped to a different board value
70                    if (letterToBoardValue[letterIndex] != -1 &&
71                        letterToBoardValue[letterIndex] != boardValue) {
72                        return false;
73                    }
74
75                    // Check if board value already mapped to a different letter
76                    if (boardValueToLetter[boardValue] != -1 &&
77                        boardValueToLetter[boardValue] != letterIndex) {
78                        return false;
79                    }
80
81                    // Establish or confirm the bidirectional mapping
82                    letterToBoardValue[letterIndex] = boardValue;
83                    boardValueToLetter[boardValue] = letterIndex;
84                }
85            }
86        }
87
88        return true;
89    }
90}
91
1class Solution {
2public:
3    vector<int> findPattern(vector<vector<int>>& board, vector<string>& pattern) {
4        int boardRows = board.size();
5        int boardCols = board[0].size();
6        int patternRows = pattern.size();
7        int patternCols = pattern[0].size();
8
9        // Lambda function to check if pattern matches at position (startRow, startCol)
10        auto isPatternMatch = [&](int startRow, int startCol) {
11            // Mapping from pattern letters to board values
12            vector<int> letterToValue(26, -1);
13            // Mapping from board values to pattern letters
14            vector<int> valueToLetter(10, -1);
15
16            // Check each cell in the pattern
17            for (int row = 0; row < patternRows; ++row) {
18                for (int col = 0; col < patternCols; ++col) {
19                    int boardRow = startRow + row;
20                    int boardCol = startCol + col;
21                    char patternChar = pattern[row][col];
22                    int boardValue = board[boardRow][boardCol];
23
24                    if (isdigit(patternChar)) {
25                        // Pattern contains a digit - must match exactly
26                        int patternDigit = patternChar - '0';
27                        if (patternDigit != boardValue) {
28                            return false;
29                        }
30                    } else {
31                        // Pattern contains a letter - check bijective mapping
32                        int letterIndex = patternChar - 'a';
33
34                        // Check if this letter was already mapped to a different value
35                        if (letterToValue[letterIndex] != -1 &&
36                            letterToValue[letterIndex] != boardValue) {
37                            return false;
38                        }
39
40                        // Check if this board value was already mapped to a different letter
41                        if (valueToLetter[boardValue] != -1 &&
42                            valueToLetter[boardValue] != letterIndex) {
43                            return false;
44                        }
45
46                        // Update the bidirectional mapping
47                        letterToValue[letterIndex] = boardValue;
48                        valueToLetter[boardValue] = letterIndex;
49                    }
50                }
51            }
52            return true;
53        };
54
55        // Try all possible starting positions on the board
56        for (int row = 0; row <= boardRows - patternRows; ++row) {
57            for (int col = 0; col <= boardCols - patternCols; ++col) {
58                if (isPatternMatch(row, col)) {
59                    return {row, col};
60                }
61            }
62        }
63
64        // Pattern not found
65        return {-1, -1};
66    }
67};
68
1/**
2 * Finds a pattern within a 2D board where the pattern can contain:
3 * - Digits (0-9): Must match exactly with the board value
4 * - Letters (a-z): Act as variables that can match any digit, but must be consistent
5 *
6 * @param board - 2D array of numbers representing the board
7 * @param pattern - 2D array of strings representing the pattern to find
8 * @returns Array with [row, col] of the top-left corner where pattern is found, or [-1, -1] if not found
9 */
10function findPattern(board: number[][], pattern: string[]): number[] {
11    const boardRows: number = board.length;
12    const boardCols: number = board[0].length;
13    const patternRows: number = pattern.length;
14    const patternCols: number = pattern[0].length;
15
16    /**
17     * Checks if the pattern matches the board starting at position (startRow, startCol)
18     *
19     * @param startRow - Starting row position in the board
20     * @param startCol - Starting column position in the board
21     * @returns true if pattern matches at this position, false otherwise
22     */
23    const checkPatternMatch = (startRow: number, startCol: number): boolean => {
24        // Map from letter (a-z) to board value (0-9)
25        const letterToDigit: number[] = Array(26).fill(-1);
26        // Map from board value (0-9) to letter index (0-25)
27        const digitToLetter: number[] = Array(10).fill(-1);
28
29        // Iterate through each cell in the pattern
30        for (let patternRow = 0; patternRow < patternRows; ++patternRow) {
31            for (let patternCol = 0; patternCol < patternCols; ++patternCol) {
32                const boardRow: number = startRow + patternRow;
33                const boardCol: number = startCol + patternCol;
34                const patternCell: string = pattern[patternRow][patternCol];
35
36                // Check if the pattern cell is a digit
37                if (!isNaN(Number(patternCell))) {
38                    const patternDigit: number = Number(patternCell);
39                    // Digit must match exactly with board value
40                    if (patternDigit !== board[boardRow][boardCol]) {
41                        return false;
42                    }
43                } else {
44                    // Pattern cell is a letter (variable)
45                    const letterIndex: number = patternCell.charCodeAt(0) - 'a'.charCodeAt(0);
46                    const boardValue: number = board[boardRow][boardCol];
47
48                    // Check if this letter was already mapped to a different digit
49                    if (letterToDigit[letterIndex] !== -1 && letterToDigit[letterIndex] !== boardValue) {
50                        return false;
51                    }
52
53                    // Check if this board value was already mapped to a different letter
54                    if (digitToLetter[boardValue] !== -1 && digitToLetter[boardValue] !== letterIndex) {
55                        return false;
56                    }
57
58                    // Create bidirectional mapping
59                    letterToDigit[letterIndex] = boardValue;
60                    digitToLetter[boardValue] = letterIndex;
61                }
62            }
63        }
64        return true;
65    };
66
67    // Try all possible starting positions where the pattern can fit
68    for (let row = 0; row < boardRows - patternRows + 1; ++row) {
69        for (let col = 0; col < boardCols - patternCols + 1; ++col) {
70            if (checkPatternMatch(row, col)) {
71                return [row, col];
72            }
73        }
74    }
75
76    // Pattern not found
77    return [-1, -1];
78}
79

Time and Space Complexity

Time Complexity: O(m × n × r × c)

The algorithm iterates through all possible starting positions in the board where the pattern could fit. For each valid starting position (i, j), there are (m - r + 1) × (n - c + 1) such positions. For each starting position, the check function examines every cell in the pattern, which requires r × c operations. Therefore, the total time complexity is O((m - r + 1) × (n - c + 1) × r × c), which simplifies to O(m × n × r × c) when considering the dominant terms.

Space Complexity: O(|Σ|)

The space complexity is determined by the two dictionaries d1 and d2 used in the check function. Dictionary d1 maps pattern characters to board values, while d2 maps board values to pattern characters. The maximum size of these dictionaries is bounded by the size of the character set Σ. Since the pattern can contain lowercase letters and the board contains digits (0-9), and considering the bijective mapping requirement between pattern characters and board values, the space required is O(|Σ|) where |Σ| ≤ 36 (26 lowercase letters + 10 digits).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall: Forgetting Bidirectional Mapping Validation

One of the most common mistakes is only checking in one direction when validating letter-to-digit mappings. Developers often implement only the pattern-to-board mapping (d1 or pattern_to_board) but forget to verify that different letters don't map to the same digit.

Incorrect Implementation:

def check_pattern_at_position(start_row, start_col):
    pattern_to_board = {}

    for pattern_row in range(pattern_rows):
        for pattern_col in range(pattern_cols):
            board_row = start_row + pattern_row
            board_col = start_col + pattern_col

            current_pattern_cell = pattern[pattern_row][pattern_col]
            current_board_value = board[board_row][board_col]

            if current_pattern_cell.isdigit():
                if int(current_pattern_cell) != current_board_value:
                    return False
            else:
                # WRONG: Only checking one direction
                if current_pattern_cell in pattern_to_board:
                    if pattern_to_board[current_pattern_cell] != current_board_value:
                        return False
                else:
                    pattern_to_board[current_pattern_cell] = current_board_value

    return True

Why This Fails: Consider pattern [['a', 'b']] and board submatrix [[5, 5]]. The incorrect code would:

  1. Map 'a' → 5
  2. Map 'b' → 5 (without checking that 5 is already mapped to 'a')
  3. Return True (incorrectly, since 'a' and 'b' should map to different digits)

Correct Solution: Always maintain both dictionaries:

  • pattern_to_board: Ensures the same letter always maps to the same digit
  • board_to_pattern: Ensures different letters map to different digits
# Check both directions for consistency
if current_pattern_cell in pattern_to_board:
    if pattern_to_board[current_pattern_cell] != current_board_value:
        return False

if current_board_value in board_to_pattern:
    if board_to_pattern[current_board_value] != current_pattern_cell:
        return False

# Only then establish the mapping
pattern_to_board[current_pattern_cell] = current_board_value
board_to_pattern[current_board_value] = current_pattern_cell

This ensures a proper bijection between letters and digits, preventing multiple letters from mapping to the same digit or one letter from mapping to multiple digits.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Depth first search is equivalent to which of the tree traversal order?

Recommended Readings

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More