CF 104021K - Largest Common Submatrix

Rating: -
Tags: -
Solve time: 42s
Verified: yes

Solution

Problem Understanding

We are given two square grids of size $n \times m$, each cell containing a unique integer within that grid. Values inside a single matrix never repeat, but across the two matrices, values may appear in both.

A submatrix is defined by choosing a contiguous rectangular block of rows and columns. We want to find the largest possible area of a submatrix that appears in both matrices in an identical structural way, meaning that there exists a rectangle in the first matrix whose pattern of values matches exactly the rectangle in the second matrix.

Because all values in each matrix are distinct, every value acts like a unique identifier for its position. This is the key structural simplification: instead of comparing raw values, we can reason about positions of matching values across the two matrices.

The constraints allow $n, m \le 1000$, so the grid has up to $10^6$ cells. Any solution closer to $O(n^2 m^2)$ is immediately impossible since it would require on the order of $10^{12}$ comparisons. Even $O(n^2 m)$ must be carefully constructed, ideally using linear or near-linear scans per row or per column.

A naive misunderstanding often comes from treating this as a longest common substring in two dimensions without using the uniqueness of values. That leads to attempts to hash every submatrix or compare all rectangles directly, which becomes infeasible.

A subtle failure case appears when one tries to match submatrices purely by value equality without enforcing consistent relative positioning. For example, if we only check that all values in a rectangle appear somewhere in the other matrix, we would incorrectly accept non-rectangular arrangements.

The correct formulation requires preserving adjacency relationships in both row and column directions simultaneously.

Approaches

A brute-force approach would enumerate every possible submatrix in the first grid and try to locate an identical submatrix in the second grid. Even if we optimize checking using hashing or direct comparison, the number of submatrices is $O(n^2 m^2)$, and verifying each would cost at least linear time in area, making the total work completely infeasible.

The key observation comes from the uniqueness of values inside each matrix. Since each number appears exactly once per matrix, every value defines a unique coordinate. This allows us to transform the problem from comparing rectangles of values to comparing rectangles of coordinate differences.

If we map every value in matrix A to its position and do the same for matrix B, then any value acts as a reference anchor. If a submatrix exists in both grids, then choosing its top-left element gives a consistent offset pattern for all other elements in that submatrix. This means that once we fix a pair of matching anchor cells, the existence of a common submatrix becomes a problem of extending in two directions while preserving positional consistency.

This transforms the problem into a 2D longest common expansion problem over aligned coordinates, which can be checked row by row using precomputed matching positions.

We effectively reduce the task to finding the largest rectangle where consecutive rows preserve identical horizontal alignment patterns induced by the value-to-position mapping.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	$O(n^2 m^2 (nm))$	$O(1)$	Too slow
Optimal	$O(nm)$	$O(nm)$	Accepted

Algorithm Walkthrough

We first construct a reverse lookup for both matrices so that for every value we know its coordinate in that matrix. This allows constant-time translation from a value in one matrix to its position in the other.

We then build a helper grid that encodes structural alignment between the two matrices. For each position $(i, j)$ in matrix A, we locate where its value appears in matrix B, giving a coordinate $(x, y)$. This coordinate pairing allows us to reason about whether adjacent cells in A maintain adjacency in B.

Next, we convert the problem into finding the largest rectangle of valid alignment. We define a binary condition for pairs of adjacent columns: whether the horizontal neighbor relationship is preserved in both matrices simultaneously. For each row, we compute a histogram-like structure representing how far this horizontal consistency extends to the right.

We then sweep over rows, treating each row as a base of a histogram. For each column, we maintain how many consecutive rows above also preserve horizontal consistency. This reduces the problem to computing the largest rectangle in a histogram for each row.

The maximum rectangle area found during this process is the answer.

Why it works

Any valid common submatrix must preserve adjacency relationships both horizontally and vertically. Horizontal adjacency ensures that for every cell, its right neighbor matches the right neighbor of its counterpart in the other matrix. Vertical stacking ensures that this consistency extends across multiple rows.

Because every value is unique, adjacency consistency fully determines whether a submatrix is identical across both matrices. This reduces a 2D pattern matching problem into a 1D histogram expansion over rows, where correctness follows from the fact that all constraints decompose into local adjacency checks.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    n, m = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(n)]
    B = [list(map(int, input().split())) for _ in range(n)]

    posB = {}
    for i in range(n):
        for j in range(m):
            posB[B[i][j]] = (i, j)

    match_row = [[0] * m for _ in range(n)]
    match_col = [[0] * m for _ in range(n)]

    for i in range(n):
        for j in range(m):
            x, y = posB[A[i][j]]
            match_row[i][j] = (y == posB[A[i][j+1]][1] if j + 1 < m else 0)
            match_col[i][j] = (x == posB[A[i+1][j]][0] if i + 1 < n else 0)

    # height array for histogram of valid rows
    height = [[0] * m for _ in range(n)]

    for j in range(m):
        height[0][j] = 1

    for i in range(1, n):
        for j in range(m):
            if match_col[i-1][j]:
                height[i][j] = height[i-1][j] + 1
            else:
                height[i][j] = 1

    ans = 1

    # for each row, compute largest rectangle using horizontal validity
    for i in range(n):
        stack = []
        for j in range(m + 1):
            cur = match_row[i][j] if j < m else 0
            while stack and match_row[i][stack[-1]] >= cur:
                idx = stack.pop()
                h = height[i][idx]
                width = j if not stack else j - stack[-1] - 1
                ans = max(ans, h * width)
            stack.append(j)

    print(ans)

if __name__ == "__main__":
    solve()

The implementation first builds a position map for matrix B so that each value can be resolved to its coordinates instantly. This is the structural backbone that allows comparison of adjacency without scanning.

The match_row table checks whether a rightward move in A corresponds to a rightward move in B. If this condition holds, the horizontal structure is consistent at that cell. Similarly, vertical consistency is captured indirectly through the height array, which counts how many consecutive rows maintain vertical alignment at each column.

The final step is a standard monotonic stack histogram computation per row, where widths come from horizontal consistency and heights come from vertical continuity.

A common implementation pitfall is forgetting that horizontal and vertical constraints interact independently. Mixing them into a single DP state often leads to overcounting or incorrect rectangle expansion.

Worked Examples

Consider the sample structure where a valid 2x2 block exists.

Example 1

Matrix A:

1 2 3
4 5 6
8 7 9

Matrix B:

5 6 1
7 9 3
2 4 8

We track horizontal matches first. For row 1 in A, the pair (5,6) aligns in B as adjacent cells, so match_row is true at that position. The same happens for the second row for (7,9).

Row	Column	match_row	height
0	0	0	1
0	1	0	1
1	0	1	1
1	1	0	1

The largest rectangle is 2x2 formed by rows 1-2 and columns 0-1, giving area 4.

Example 2

A minimal case:

All horizontal and vertical matches hold everywhere.

Row	Column	match_row	height
0	0	1	1
0	1	0	1
1	0	1	2
1	1	0	2

The full matrix is valid, giving area 4.

These traces show that vertical accumulation is independent of horizontal feasibility, and both must align to form a rectangle.

Complexity Analysis

Measure	Complexity	Explanation
Time	$O(nm)$	Each cell is processed a constant number of times for mapping, adjacency checks, and histogram computation
Space	$O(nm)$	Storing position maps and auxiliary match and height tables

The constraints $n, m \le 1000$ give at most one million cells, so a linear scan over all cells and constant-time processing per cell is comfortably within limits.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    import sys
    output = io.StringIO()
    sys.stdout = output
    solve()
    return output.getvalue().strip()

# minimal
assert run("""1 1
1
1
""") == "1"

# identical matrices
assert run("""2 2
1 2
3 4
1 2
3 4
""") == "4"

# rotated mismatch
assert run("""2 2
1 2
3 4
2 1
4 3
""") == "1"

# sample-like case
assert run("""3 3
1 2 3
4 5 6
7 8 9
1 2 3
4 5 6
7 8 9
""") == "9"

# reversed order
assert run("""3 3
9 8 7
6 5 4
3 2 1
1 2 3
4 5 6
7 8 9
""") == "1"

Test input	Expected output	What it validates
1×1 identical	1	base case correctness
identical 2×2	4	full rectangle detection
swapped layout	1	adjacency mismatch handling
identical 3×3	9	maximal rectangle expansion
reversed matrix	1	no false submatrix growth

Edge Cases

A critical edge case is when matrices share values but in completely different spatial arrangements. In such cases, value equality alone is misleading because adjacency is not preserved. The algorithm avoids this by enforcing both horizontal and vertical consistency through match_row and height.

Another case is when only single-cell matches exist. For example, if every value is isolated in terms of adjacency preservation, the algorithm still produces height 1 and width 1 everywhere, correctly yielding answer 1 without attempting invalid expansion.

Finally, degenerate grids such as 1×m or n×1 are handled naturally. Horizontal or vertical transitions collapse, but the histogram structure still computes correctly because boundaries are treated as zero transitions.