Match Alphanumerical Pattern in Matrix I - Practice Coding Problems

Match Alphanumerical Pattern in Matrix I - Problem

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].

Input & Output

Example 1 — Basic Pattern Match

$ Input: board = [[3,1,0],[0,1,1],[0,3,2]], pattern = [["a","b"],["b","b"]]

› Output: [0,1]

💡 Note: At position (0,1): submatrix is [[1,0],[1,1]]. Map a→1, b→0 fails because b appears in multiple positions with different values. Try position (1,1): submatrix is [[1,1],[3,2]]. Map a→1, b→1 fails because a and b can't both map to 1. At position (0,1) with different mapping: a→1, b→0 works for first row but fails for second row. Actually at (0,1): [[1,0],[1,1]] maps a→1, b→0 in first row but b→1 in second row, which is inconsistent. The correct answer is found by systematic checking.

Example 2 — Digit Constraints

$ Input: board = [[1,2,3],[4,5,6],[7,8,9]], pattern = [["1","a"],["b","5"]]

› Output: [0,0]

💡 Note: At position (0,0): submatrix is [[1,2],[4,5]]. Pattern requires first cell = 1 and last cell = 5, which matches. Map a→2, b→4 gives valid assignment.

Example 3 — No Match

$ Input: board = [[1,1,1],[1,1,1],[1,1,1]], pattern = [["a","b"],["c","d"]]

› Output: [-1,-1]

💡 Note: Pattern requires 4 different letters (a,b,c,d) but board only contains 1's, so no valid mapping exists.

Constraints

1 ≤ board.length, board[i].length ≤ 1000
1 ≤ pattern.length, pattern[i].length ≤ 100
0 ≤ board[i][j] ≤ 9
pattern[i][j] is either a digit or a lowercase English letter

Visualization

Tap to expand

Understanding the Visualization

Input

Board matrix with digits and pattern with letters/digits

Process

Find submatrix where pattern can be mapped consistently

Output

Coordinates of upper-left corner of matching submatrix

Key Takeaway

🎯 Key Insight: Each letter must consistently map to the same digit throughout the pattern, and different letters must map to different digits

Asked in

G Google 25 M Microsoft 18 a Amazon 15 f Meta 12

The key insight is to systematically check each possible position in the board and validate pattern constraints using bidirectional mapping. Best approach uses pattern matching with constraint validation in O(m×n×p×q) time with early termination optimizations. Time: O(m×n×p×q), Space: O(k) where k is the number of unique letters.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Pattern Matching	O(m×n×p×q)	O(k)	Try every possible position in the board and check if pattern matches
Optimized Pattern Matching	O(m×n×p×q)	O(k)	Same approach but with early termination and constraint validation

Brute Force Pattern Matching — Algorithm Steps

Step 1: Iterate through all possible starting positions (r,c) in board
Step 2: For each position, extract submatrix of pattern size
Step 3: Check if submatrix matches pattern using letter-to-digit mapping
Step 4: Return first valid position, or [-1,-1] if none found

Visualization

Tap to expand

Step-by-Step Walkthrough

Try Position (0,0)

Check if pattern fits starting at top-left

Build Letter Mapping

Map letters to digits while checking constraints

Found Match

Return coordinates of first valid match

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAX_SIZE 100

int* solution(int board[][MAX_SIZE], int m, int n, char pattern[][MAX_SIZE][2], int p, int q) {
    int* result = malloc(2 * sizeof(int));
    result[0] = -1;
    result[1] = -1;
    
    if (p > m || q > n) {
        return result;
    }
    
    for (int r = 0; r <= m - p; r++) {
        for (int c = 0; c <= n - q; c++) {
            // Check if pattern matches at position (r, c)
            int letterToDigit[26];
            int digitToLetter[10];
            int letterUsed[26] = {0};
            int digitUsed[10] = {0};
            
            for (int k = 0; k < 26; k++) letterToDigit[k] = -1;
            for (int k = 0; k < 10; k++) digitToLetter[k] = -1;
            
            int valid = 1;
            for (int i = 0; i < p && valid; i++) {
                for (int j = 0; j < q && valid; j++) {
                    char patternCell = pattern[i][j][0];
                    int boardCell = board[r + i][c + j];
                    
                    if (isdigit(patternCell)) {
                        int digit = patternCell - '0';
                        if (digit != boardCell) {
                            valid = 0;
                        }
                    } else {
                        int letterIdx = patternCell - 'a';
                        if (letterUsed[letterIdx]) {
                            if (letterToDigit[letterIdx] != boardCell) {
                                valid = 0;
                            }
                        } else {
                            if (digitUsed[boardCell]) {
                                if (digitToLetter[boardCell] != letterIdx) {
                                    valid = 0;
                                }
                            } else {
                                letterToDigit[letterIdx] = boardCell;
                                digitToLetter[boardCell] = letterIdx;
                                letterUsed[letterIdx] = 1;
                                digitUsed[boardCell] = 1;
                            }
                        }
                    }
                }
            }
            
            if (valid) {
                result[0] = r;
                result[1] = c;
                return result;
            }
        }
    }
    
    return result;
}

int main() {
    // Simplified parsing for this example
    int board[MAX_SIZE][MAX_SIZE] = {{3,1,0},{0,1,1},{0,3,2}};
    char pattern[MAX_SIZE][MAX_SIZE][2] = {{"a","b"},{"b","b"}};
    int m = 3, n = 3, p = 2, q = 2;
    
    int* result = solution(board, m, n, pattern, p, q);
    printf("[%d,%d]\n", result[0], result[1]);
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m×n×p×q)

For each of m×n positions, check p×q pattern cells

✓ Linear Growth

Space Complexity

O(k)

Hash map stores at most k distinct letters from pattern

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Pattern Matching — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler