You are given matrix *a* of size *n* × *m*, its elements are integers. We will assume that the rows of the matrix are numbered from top to bottom from 1 to *n*, the columns are numbered from left to right from 1 to *m*. We will denote the element on the intersecting of the *i*-th row and the *j*-th column as *a*<sub class="lower-index">*ij*</sub>.

We'll call submatrix *i*<sub class="lower-index">1</sub>, *j*<sub class="lower-index">1</sub>, *i*<sub class="lower-index">2</sub>, *j*<sub class="lower-index">2</sub> (1 ≤ *i*<sub class="lower-index">1</sub> ≤ *i*<sub class="lower-index">2</sub> ≤ *n*; 1 ≤ *j*<sub class="lower-index">1</sub> ≤ *j*<sub class="lower-index">2</sub> ≤ *m*) such elements *a*<sub class="lower-index">*ij*</sub> of the given matrix that *i*<sub class="lower-index">1</sub> ≤ *i* ≤ *i*<sub class="lower-index">2</sub> AND *j*<sub class="lower-index">1</sub> ≤ *j* ≤ *j*<sub class="lower-index">2</sub>. We'll call the area of the submatrix number (*i*<sub class="lower-index">2</sub> - *i*<sub class="lower-index">1</sub> + 1)·(*j*<sub class="lower-index">2</sub> - *j*<sub class="lower-index">1</sub> + 1). We'll call a submatrix inhomogeneous, if all its elements are distinct.

Find the largest (in area) inhomogenous submatrix of the given matrix.
The first line contains two integers *n*, *m* (1 ≤ *n*, *m* ≤ 400) — the number of rows and columns of the matrix, correspondingly.

Each of the next *n* lines contains *m* integers *a*<sub class="lower-index">*ij*</sub> (1 ≤ *a*<sub class="lower-index">*ij*</sub> ≤ 160000) — the elements of the matrix.
#!/usr/bin/python

import time
import random
from math import ceil, log2
from typing import List, Tuple, Dict


# Get a matrix, return the largest inhomogenous submatrix
def get_largest_submatrix(A: List[List[int]]) -> Tuple[int, int, int, int, int]:
    N, M = len(A), len(A[0])

    dup_per_columns = get_columns(A)
    dup_per_rows = get_rows(A)

    max_columns = get_max_columns(dup_per_columns, N, M)
    max_rows = get_max_rows(dup_per_rows, N, M)

    sizes = [[0 for j in range(M)] for i in range(N)]
    idxes = [[None for j in range(M)] for i in range(N)]
    for i in range(N):
        for j in range(M):

            n = max_columns[i][j]
            m = max_rows[i][j]

            if i != 0 and j != 0:

                ui = max(i - 1, 0)
                lj = max(j - 1, 0)

                left_up, left, up = (
                    idxes[ui][lj][2:4],
                    idxes[i][lj][2:4],
                    idxes[ui][j][2:4],
                )

                if (
                    (i + n - 1 <= left_up[0] and j + m - 1 <= left_up[1])
                    or (i + n - 1 <= left[0] and j + m - 1 <= left[1])
                    or (i + n - 1 <= up[0] and j + m - 1 <= up[1])
                ):
                    sizes[i][j] = n * m
                    idxes[i][j] = (i, j, i + n - 1, j + m - 1)
                    continue

            limit_rows = [max_rows[i + ii][j] for ii in range(n)]
            limit_columns = [max_columns[i][j + jj] for jj in range(m)]

            max_size = limit_rows[0]
            max_idx = (i, j, i, j + m - 1)
            for ii in range(1, n):
                max_width_by_row = min(limit_rows[: ii + 1])
                max_width_by_col = max_width_by_row
                for k, m in enumerate(limit_columns):
                    if m < ii + 1:
                        max_width_by_col = k

                height = ii + 1
                width = min(max_width_by_row, max_width_by_col)
                size = height * width

                if size > max_size and check_distinct(A, i, j, height, width):
                    max_size = size
                    max_idx = (i, j, i + height - 1, j + width - 1)

            sizes[i][j] = max_size
            idxes[i][j] = max_idx

    max_size = max(sum(sizes, []))
    idx = sum(sizes, []).index(max_size)
    max_idx = sum(idxes, [])[idx]

    return max_size, max_idx


def check_distinct(A: List[List[int]], i, j, height, width: int) -> bool:

    sub = [[A[ii][jj] for jj in range(j, j + width)] for ii in range(i, i + height)]
    subset = sum(sub, [])

    return len(set(subset)) == len(subset)


# Get a matrix, return duplicate elements and their indices in each column
def get_columns(A: List[List[int]]) -> Dict[int, List[Tuple[int]]]:
    N, M = len(A), len(A[0])

    dup_per_columns = {j: [] for j in range(M)}
    for j in range(M):
        column = [A[i][j] for i in range(N)]

        dups = {}
        for idx, i in enumerate(column):
            dups[i] = dups.get(i, ()) + (idx,)

        dup_idxs = [v for v in dups.values() if len(v) > 1]

        dup_per_columns[j] = dup_idxs

    return dup_per_columns


# Get a matrix, return duplicate elements and their indices in each row
def get_rows(A: List[List[int]]) -> Dict[int, List[Tuple[int]]]:
    N, M = len(A), len(A[0])

    dup_per_rows = {i: [] for i in range(N)}
    for i in range(N):
        row = A[i]

        dups = {}
        for idx, j in enumerate(row):
            dups[j] = dups.get(j, ()) + (idx,)

        dup_idxs = [v for v in dups.values() if len(v) > 1]

        dup_per_rows[i] = dup_idxs

    return dup_per_rows


def get_max_columns(
    dup_per_columns: Dict[int, List[Tuple[int]]], N, M
) -> List[List[int]]:
    max_columns = [[0 for j in range(M)] for i in range(N)]

    for j in range(M):
        dups = dup_per_columns[j]
        pivots = [d + 1 for d in sum(dups, ())]

        for i in range(N):
            if i == 0 or i in pivots:
                max_columns[i][j] = get_max(dups, i, N)
            else:
                max_columns[i][j] = max_columns[i - 1][j] - 1

    return max_columns


def get_max_rows(dup_per_rows: Dict[int, List[Tuple[int]]], N, M) -> List[List[int]]:
    max_rows = [[0 for j in range(M)] for i in range(N)]

    for i in range(N):
        dups = dup_per_rows[i]
        pivots = [d + 1 for d in sum(dups, ())]

        for j in range(M):
            if j == 0 or j in pivots:
                max_rows[i][j] = get_max(dups, j, M)
            else:
                max_rows[i][j] = max_rows[i][j - 1] - 1

    return max_rows


# Return length of the maximum inhomongenous bin
def get_max(l: List[Tuple[int]], start: int, end: int) -> int:
    last_idx = start + 1
    for idx in range(start + 1, end + 1):

        homo = False
        for tup in l:
            if len([i for i in tup if i >= start and i < idx]) > 1:
                homo = True
                last_idx = idx - 1
                break

        if homo:
            break

        last_idx = idx

    return last_idx - start


def pprint(A):
    for row in A:
        print(" ".join([f"{i:>3}" for i in row]))


if __name__ == "__main__":
    N = 100
    M = 100
    A = [[random.randint(1, 10000) for j in range(M)] for i in range(N)]

    # pprint(A)

    start = time.time()
    max_size, max_idx = get_largest_submatrix(A)
    end = time.time()

    print(f"max_size: {max_size}, max_idx: {max_idx}")
    print(f"time: {end - start}")
