Rasta and Kheshtak (largest common square submatrix pattern)

Hard

Problem

Given two matrices of integers, return the side length of the largest square pattern that appears in both. Binary-search the side length and compare 2-D rolling hashes of the squares.

Example 1

Input:  two small matrices sharing a 2 × 2 block
Output: 2

Also asked as: Rasta and Kheshtak

Test cases

No automated tests for this problem yet. Use the examples above to check your output.

Your solution ✓ Solved

Ctrl/⌘ + Enter to run

This problem has no automated tests. Run executes your code and shows what it logs.

View solutionHide solution1 approach

1. Binary search on the square size + hashing

Time O(R·C·log(min(R,C)))Space O(R·C)

Binary-search the side length k. For each candidate k, hash every k×k submatrix of both grids (2-D rolling hash / prefix hashing) and check for a common hash. Largest k with an intersection is the answer.

// sketch — 2D prefix hashing
function has_common_square(A, B, k) {
const hashesA = new Set();
const grab = (G, out) => {
for (let r = 0; r + k <= G.length; r++)
for (let c = 0; c + k <= G[0].length; c++) {
let h = '';
for (let i = 0; i < k; i++) h += G[r + i].slice(c, c + k).join(',') + ';';
out.add(h);
}
};
grab(A, hashesA);
const hashesB = new Set();
grab(B, hashesB);
for (const h of hashesB) if (hashesA.has(h)) return true;
return false;
}

The string concatenation above is O(k²) per window; a real solution uses polynomial 2-D rolling hashes for O(1) per window.