Rasta and Kheshtak (largest common square submatrix pattern)
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.
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 hashingfunction 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.