FastPrep
Problem · Matrix

Find a Submatrix Matching a Pattern

Learn this problem
● MediumBoston Consulting Group logoBoston Consulting GroupNEW GRADINTERNOA

Problem statement

You are given a rectangular integer matrix board and a square pattern represented by the string array pattern. Each entry of board is a digit from 0 through 9. Each character of pattern is either a decimal digit or a lowercase English letter.

A submatrix matches pattern when it has the same dimensions and follows all of these rules:

  • If pattern[r][c] is a digit, then the corresponding submatrix entry must equal that digit.
  • Every occurrence of the same letter must correspond to the same digit.
  • Any two distinct letters must correspond to different digits.

Return an integer array [row, column] containing the zero-based coordinates of the upper-left corner of a matching submatrix. If several submatrices match, return the one with the smallest row index, breaking a remaining tie by the smallest column index. If no submatrix matches, return [-1, -1].

Expected complexity

A solution with time complexity no worse than O(board.length * board[0].length * pattern.length^2) is sufficient.

Function

findMatchingSubmatrix(board: int[][], pattern: String[]) → int[]

Examples

Example 1

board = [[1,2,1],[2,1,2]]pattern = ["ab","ba"]return = [0,0]

The submatrix starting at [0, 0] maps a to 1 and b to 2. The submatrix starting at [0, 1] also matches with the two mappings reversed, so the smaller column index determines the result.

Example 2

board = [[0,1,2,3],[4,5,6,7],[8,9,5,1]]pattern = ["a6","9a"]return = [1,1]

At [1, 1], both occurrences of a correspond to 5, while the literal characters 6 and 9 match their board entries. Every earlier candidate fails a literal-digit check.

Example 3

board = [[1,1],[1,1]]pattern = ["ab","ba"]return = [-1,-1]

The only candidate would map both a and b to 1. Distinct letters must map to distinct digits, so there is no match.

Constraints

  • board is a non-empty rectangular matrix.
  • Every board[r][c] is an integer from 0 through 9.
  • pattern is non-empty, and every pattern[r] has length pattern.length.
  • Every character in pattern is a decimal digit or a lowercase English letter.

More Boston Consulting Group problems

drafts saved locally
public int[] findMatchingSubmatrix(int[][] board, String[] pattern) {
    // write your code here
}
board[[1,2,1],[2,1,2]]
pattern["ab","ba"]
expected[0,0]
checking account