Searching & SortingProblem 20 of 36

Rasta and Kheshtak

Brute Force
Time: O(n² * m²)
Space: O(1)
Optimal
Time: O(n * m)
Space: O(n * m)

Problem Statement

Given two matrices A (n×m) and B (x×y), determine if matrix B is a submatrix of matrix A. A submatrix is a contiguous 2D block within the larger matrix.

Constraints:

  • 1 ≤ n, m ≤ 1000
  • 1 ≤ x ≤ n, 1 ≤ y ≤ m
  • Matrix elements can be any integers

Example:

  • Input: A = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]] B = [[6, 7], [10, 11]]
  • Output: true
  • Explanation: B appears in A starting at position (1, 1)

Example 2:

  • Input: A = [[1, 2, 3], [4, 5, 6]] B = [[1, 3], [4, 6]]
  • Output: false
  • Explanation: B is not a contiguous submatrix of A

Approach 1: Brute Force (Check All Positions)

Intuition

Try every possible starting position in matrix A and check if the submatrix starting at that position matches B.

Algorithm

  1. For each possible starting position (i, j) in A:
    • Where i can be from 0 to n-x and j can be from 0 to m-y
  2. Check if the x×y submatrix starting at (i, j) matches B
  3. If match found, return true
  4. Return false if no match found
java
public class Solution {
    public boolean isSubmatrix(int[][] A, int[][] B) {
        int n = A.length, m = A[0].length;
        int x = B.length, y = B[0].length;
        
        // Check if B can fit in A
        if (x > n || y > m) return false;
        
        // Try all starting positions
        for (int i = 0; i <= n - x; i++) {
            for (int j = 0; j <= m - y; j++) {
                boolean match = true;
                
                // Check if submatrix matches B
                outer:
                for (int bi = 0; bi < x; bi++) {
                    for (int bj = 0; bj < y; bj++) {
                        if (A[i + bi][j + bj] != B[bi][bj]) {
                            match = false;
                            break outer;
                        }
                    }
                }
                
                if (match) return true;
            }
        }
        
        return false;
    }
}

Complexity Analysis

  • Time Complexity: O(n² × m²) in worst case - O((n-x)×(m-y)×x×y)
  • Space Complexity: O(1) - No extra space used

Approach 2: Hashing with Rabin-Karp (Optimal)

Intuition

Use 2D rolling hash (Rabin-Karp) to efficiently compare submatrices. First hash each row, then use column-wise hashing on row hashes.

Key Observations:

  1. Compute hash for each row of length y using polynomial hashing
  2. Stack row hashes and compute column hash of height x
  3. Use rolling hash to slide the window efficiently

Algorithm

  1. Compute hash for pattern B
  2. For each valid column position j:
    • Compute row hashes of length y for each row
    • Use rolling hash vertically to find matching column hash
  3. Verify match to handle hash collisions
java
public class SubmatrixSearch {
    private static final long MOD = 1000000007;
    private static final long BASE1 = 31;
    private static final long BASE2 = 37;
    
    private long power(long base, int exp) {
        long result = 1;
        base %= MOD;
        while (exp > 0) {
            if ((exp & 1) == 1) result = (result * base) % MOD;
            base = (base * base) % MOD;
            exp >>= 1;
        }
        return result;
    }
    
    public boolean isSubmatrix(int[][] A, int[][] B) {
        int n = A.length, m = A[0].length;
        int x = B.length, y = B[0].length;
        
        if (x > n || y > m) return false;
        
        // Compute hash for pattern B
        long patternHash = 0;
        for (int i = 0; i < x; i++) {
            long rowHash = 0;
            for (int j = 0; j < y; j++) {
                rowHash = (rowHash * BASE1 + B[i][j] + 1) % MOD;
            }
            patternHash = (patternHash * BASE2 + rowHash) % MOD;
        }
        
        // Precompute powers
        long pow1 = power(BASE1, y - 1);
        long pow2 = power(BASE2, x - 1);
        
        // Compute row hashes for matrix A
        long[][] rowHashes = new long[n][m - y + 1];
        
        for (int i = 0; i < n; i++) {
            long hash = 0;
            for (int j = 0; j < y; j++) {
                hash = (hash * BASE1 + A[i][j] + 1) % MOD;
            }
            rowHashes[i][0] = hash;
            
            for (int j = 1; j <= m - y; j++) {
                hash = (((hash - (A[i][j-1] + 1) * pow1 % MOD + MOD) % MOD) * BASE1 + A[i][j+y-1] + 1) % MOD;
                rowHashes[i][j] = hash;
            }
        }
        
        // Check column-wise hashes
        for (int j = 0; j <= m - y; j++) {
            long colHash = 0;
            
            for (int i = 0; i < x; i++) {
                colHash = (colHash * BASE2 + rowHashes[i][j]) % MOD;
            }
            
            if (colHash == patternHash && verify(A, B, 0, j)) {
                return true;
            }
            
            for (int i = 1; i <= n - x; i++) {
                colHash = (((colHash - rowHashes[i-1][j] * pow2 % MOD + MOD) % MOD) * BASE2 + rowHashes[i+x-1][j]) % MOD;
                
                if (colHash == patternHash && verify(A, B, i, j)) {
                    return true;
                }
            }
        }
        
        return false;
    }
    
    private boolean verify(int[][] A, int[][] B, int si, int sj) {
        int x = B.length, y = B[0].length;
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                if (A[si + i][sj + j] != B[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }
}

Dry Run Example

A = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]] B = [[6, 7], [10, 11]] Step 1: Compute pattern hash for B Row 0: hash = 6*31 + 7 = 193 Row 1: hash = 10*31 + 11 = 321 Pattern hash = 193*37 + 321 = 7462 Step 2: Compute row hashes for A (window size 2) Row 0: [1*31+2=33, 2*31+3=65, 3*31+4=97] Row 1: [5*31+6=161, 6*31+7=193, 7*31+8=225] Row 2: [9*31+10=289, 10*31+11=321, 11*31+12=353] Step 3: Check column hashes (window height 2) At j=1: colHash = 193*37 + 321 = 7462 = patternHash Verify match: A[1][1..2] and A[2][1..2] == B Match found! Result: true

Complexity Analysis

  • Time Complexity: O(n × m) - Single pass with rolling hash
  • Space Complexity: O(n × m) - For storing row hashes

Key Takeaways

  1. 2D Rolling Hash: Extend Rabin-Karp to 2D by hashing rows first, then columns
  2. Double Hashing: Use different bases for row and column to reduce collisions
  3. Verification: Always verify matches due to possible hash collisions
  4. Rolling Hash: Allows O(1) window sliding instead of O(window_size) recomputation
  5. Preprocessing: Computing row hashes first enables efficient column-wise sliding
  6. Applications: Pattern matching, image processing, plagiarism detection
Previous
Bishu and Soldiers
Next
Kth smallest number again