Searching & Sorting · 20 of 36

Rasta and Kheshtak

Find the biggest square patch of tiles that appears in both of two tiled floors, by guessing a size and comparing fingerprints of all patches of that size.

HardBinary search on the answer

Simple way: time O(n*m*p*q*L^2)
room O(1)
Clever way: time O((n*m + p*q) log L)
room O(n*m)

The problem, simply

You get two grids of numbers: A with n rows and m columns, and B with p rows and q columns. (In the original story a grid of numbers is called a kheshtak.) A square block is a piece of a grid with the same number of rows and columns, cut out as one unbroken block.

Find the biggest size s such that some s by s block of A is exactly equal, number for number, to some s by s block of B. If no single number appears in both grids, the answer is 0.

A story to remember it

Picture it

gridA

gridB

The biggest common square is 2 by 2: the block 1 2 over 1 2. It sits at the top left of A and at the top right of B.

answer

Examples

The sample

In: A = [[1,2,0],[1,2,1],[1,2,3]], B = [[0,1,2],[1,1,2],[3,1,2]]
Out: 2

The block 1 2 over 1 2 is in both. No 3 by 3 block matches, because that would be the whole grids, and they differ.

Nothing in common

In: A = [[1,2],[3,4]], B = [[5,6],[7,8]]
Out: 0

Not even one number is shared.

One grid inside the other

In: A = [[9,9,9,9],[9,1,2,3],[9,4,5,6],[9,7,8,0]], B = [[1,2,3],[4,5,6],[7,8,0]]
Out: 3

All of B appears in the lower right of A.

Single cells

In: A = [[5]], B = [[7, 5]]
Out: 1

A 1 by 1 block is just a shared number.

Way 1: the simple way

Try every top left corner in A together with every top left corner in B, and grow a square from both corners while it still matches.

For each corner (i, j) in A and each corner (r, c) in B:
Start with size s = 0. While the next bigger square fits in both grids, check only the new bottom row and new right column of that bigger square. If they all match, s grows by 1. Otherwise stop.
Keep the biggest s you ever reach.

java

class Solution {
    public int biggestCommonSquare(int[][] A, int[][] B) {
        int n = A.length, m = A[0].length, p = B.length, q = B[0].length;
        int best = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                for (int r = 0; r < p; r++)
                    for (int c = 0; c < q; c++) {
                        int s = 0;
                        while (i + s < n && j + s < m && r + s < p && c + s < q
                                && edgeMatches(A, B, i, j, r, c, s)) {
                            s++;                       // the (s+1) square matches
                        }
                        best = Math.max(best, s);
                    }
        return best;
    }

    // check the new bottom row and right column of the square of size s + 1
    private boolean edgeMatches(int[][] A, int[][] B, int i, int j, int r, int c, int s) {
        for (int t = 0; t <= s; t++) {
            if (A[i + s][j + t] != B[r + s][c + t]) return false;   // bottom row
            if (A[i + t][j + s] != B[r + t][c + s]) return false;   // right column
        }
        return true;
    }
}

How long it takes: there are n*m*p*q pairs of corners, and growing to size L (the smallest side of the two grids) costs about L^2 checks, so O(n*m*p*q*L^2). On 700 by 700 grids that is far too slow. Extra room: O(1).

Way 2: the clever way

Binary search the size, and test one size with fingerprints.

lo = 1, hi = L, where L is the smallest of n, m, p and q.
For a size s, common(s) says whether any s by s block is in both grids:
- Give every s by s block of A a fingerprint, a hash, and put the fingerprints in a hash set.
- Give every s by s block of B a fingerprint and look it up in the set.
If common(mid) is yes, remember mid and try bigger: lo = mid + 1. Otherwise try smaller: hi = mid - 1.

To make all fingerprints of one size fast, use a rolling hash twice. First slide a window of width s along each row, so each row position gets a number for its s cells. Then slide a window of height s down each column of those row numbers. Each slide adds the new cell and removes the old one in O(1), so all blocks of one size take O(n*m) time.

Binary search the size, fingerprints decide each guess

01 / 14

gridA

gridB

arraysizes

The smallest side is 3, so the answer is a size from 1 to 3. lo = 1, hi = 3.

best: 0

looking now
seen
done
answer
rejected
just added

java

class Solution {
    static final long MOD = 1_000_000_007L;

    public int biggestCommonSquare(int[][] A, int[][] B) {
        int L = Math.min(Math.min(A.length, A[0].length), Math.min(B.length, B[0].length));
        int lo = 1, hi = L, best = 0;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (common(A, B, mid)) {
                best = mid;          // a mid by mid block is shared: try bigger
                lo = mid + 1;
            } else {
                hi = mid - 1;        // none of this size: try smaller
            }
        }
        return best;
    }

    private boolean common(int[][] A, int[][] B, int s) {
        Set<Long> box = new HashSet<>();
        long[][] a1 = hashes(A, s, 131, 137), a2 = hashes(A, s, 911, 919);
        for (int i = 0; i < a1.length; i++)
            for (int j = 0; j < a1[0].length; j++)
                box.add(a1[i][j] << 32 | a2[i][j]);         // two hashes as one key
        long[][] b1 = hashes(B, s, 131, 137), b2 = hashes(B, s, 911, 919);
        for (int i = 0; i < b1.length; i++)
            for (int j = 0; j < b1[0].length; j++)
                if (box.contains(b1[i][j] << 32 | b2[i][j])) return true;
        return false;
    }

    // hash of every s by s block, with base x along rows and base y down columns
    private long[][] hashes(int[][] M, int s, long x, long y) {
        int n = M.length, m = M[0].length;
        long px = 1, py = 1;
        for (int t = 1; t < s; t++) { px = px * x % MOD; py = py * y % MOD; }
        long[][] row = new long[n][m - s + 1];
        for (int i = 0; i < n; i++) {                       // slide along each row
            long h = 0;
            for (int j = 0; j < m; j++) {
                if (j >= s) h = (h - Math.floorMod(M[i][j - s], MOD) * px % MOD + MOD) % MOD;
                h = (h * x + Math.floorMod(M[i][j], MOD)) % MOD;
                if (j >= s - 1) row[i][j - s + 1] = h;
            }
        }
        long[][] out = new long[n - s + 1][m - s + 1];
        for (int j = 0; j <= m - s; j++) {                  // slide down each column
            long h = 0;
            for (int i = 0; i < n; i++) {
                if (i >= s) h = (h - row[i - s][j] * py % MOD + MOD) % MOD;
                h = (h * y + row[i][j]) % MOD;
                if (i >= s - 1) out[i - s + 1][j] = h;
            }
        }
        return out;
    }
}

How long it takes: each guess hashes both grids in O(n*m + p*q), and there are O(log L) guesses, so O((n*m + p*q) log L). Extra room: the hash tables and the set, O(n*m).

Watch out for

The binary search only works because sizes go "yes, then no". Make sure your check is about the same size in both grids, not "at least size s".
Negative numbers break value % MOD. Use Math.floorMod.
Forgetting the answer 0 when no number is shared. Start best at 0.
Removing the old cell in a rolling hash needs base^(s - 1), not base^s.

What interviewers ask next

Is B a block inside A at all? That is a 2D pattern search: hash B once and slide over A, or use 2D KMP. This is a smaller problem than the one here.
Biggest common square without hashing? A table dp[i][j][r][c] = biggest matching square ending at (i, j) in A and (r, c) in B, from its three neighbors like the "largest square of 1s" problem. That is O(n*m*p*q), exact but slow.
The 1D version is the longest common substring of two strings. Binary search the length plus rolling hash works there too, or use a suffix automaton.
Why one base for rows and another for columns? With the same base, a block and its copy flipped over the diagonal always get the same fingerprint.

Remember this

Grown-up words: the grids are matrices, a square patch is a square submatrix, the fingerprint is a 2D polynomial rolling hash, the box is a hash set, and guessing the size is binary search on the answer.