356. Rasta and Kheshtak - Biggest Common Subsquare

Two grids of integers, A (n rows by m columns) and B (x rows by y columns), are given. Find the largest integer s such that some contiguous s x s block of A is identical (matching values in matching positions) to some contiguous s x s block of B. Print 0 if not even a single value (a 1x1 block) is shared.

Input: The first line contains n and m, the dimensions of grid A, followed by n lines of m space-separated integers. The next line contains x and y, the dimensions of grid B, followed by x lines of y space-separated integers. Output: Print a single integer - the size s of the largest common contiguous square block shared by A and B.

1 <= n, m, x, y <= 50, 1 <= grid values <= 1000

Given the small constraints here (grids up to 50x50), even a more direct block-by-block comparison approach (without hashing) would likely run fast enough - the hashing optimization becomes genuinely necessary only at a larger scale.

Given two grids of numbers, find the biggest possible square block (same size, same exact values in the same positions) that appears somewhere in BOTH grids. Brute force: For every possible size s (from the largest possible down to 1), compare every s x s block of A against every s x s block of B directly, element by element - this is correct but very slow for larger grids, since it re-examines overlapping blocks with full comparisons. Optimised: Binary searching on the answer size s converts 'find the LARGEST working size' into a series of 'does a working size s exist' yes/no checks, and hashing every block of each size (instead of comparing them element-by-element) turns each block-matching check into a fast hash-set lookup - together these cut down both the number of sizes tried and the cost of checking each one.

Observe that if some s x s block is shared, any smaller sub-block within it is also shared, so try s from the largest feasible value down to 1 (stopping at the first success), but for each candidate s avoid cell-by-cell comparison: compute a 2D rolling hash for every s x s window of A, store those hashes in a set, then compute the hash of every s x s window of B in the same way and check for membership (verifying a real match on hash hit to guard against collisions). Each candidate s is now checked in time proportional to the grid sizes rather than the grid sizes times s^2, which is a large constant-factor win, though still checking every s down from the max is linear in the number of candidate sizes. Time: O(min(n,m,x,y) * (n*m + x*y)) Space: O(n*m + x*y)

Because 'some s x s block is shared' is a monotonic property in s (true for all sizes up to the true maximum, false above it), binary search on s directly instead of scanning it linearly: at each candidate s tested during the binary search, use the same 2D rolling-hash technique (hash all s x s windows of A into a set, check B's windows against it) to answer 'does a shared s x s block exist?' in time proportional to the grid sizes. This reduces the number of candidate sizes actually tested from O(min dimension) down to O(log(min dimension)), which is the key remaining inefficiency in the better approach. Time: O(log(min(n,m,x,y)) * (n*m + x*y)) Space: O(n*m + x*y)

For every candidate side length s from the largest possible down to 1, and for every position of an s x s window in A and every position of an s x s window in B, compare the two windows cell by cell; the first s for which any matching pair of windows is found is the answer. This is a direct, exhaustive check of the problem's definition, but the four nested loops (over s, over A's window positions, over B's window positions, and over the s x s cells themselves) make it extremely slow even at the given small bounds. Time: O(min(n,m,x,y) * n*m * x*y * s^2) worst case Space: O(1) extra

1. Binary search on the answer: try a candidate square size s, and check whether ANY s x s block of grid A exactly matches ANY s x s block of grid B. 2. To check a candidate size efficiently, use rolling hashes: compute a hash for every possible s x s block of both grids, and check if any hash value is shared between the two sets. 3. If a match exists at size s, try a bigger size; if not, try a smaller size - narrowing down to the largest size that still has a match.

Time: Roughly proportional to the grid size squared, multiplied by a logarithmic binary-search factor over possible answer sizes - specialized, but manageable for the small grid sizes in this problem's constraints (up to 50x50). Space: Proportional to the number of blocks hashed at each candidate size, which is bounded by the grid's total size.

no value at all shared between the two grids (print 0); grids as small as 1x1; and grids at the largest allowed 50x50 to confirm the approach is fast enough.

Be ready to explain 'binary search on the answer' as a general pattern (not specific to this problem) - whenever a problem asks for the LARGEST or SMALLEST value satisfying some checkable condition, and larger/smaller values behave predictably (monotonically), binary searching on that answer value itself is a powerful, reusable technique.