Hello everyone! I am here to ask you if there is any efficient way to solve this sub 2 dimensional array problem.

• You are given a 2 dimensional array of integers $$$A_{n,n}$$$. there are $$$k$$$ different integers in this array. try to find out the smallest sub 2 dimensional array containing all kinds of integer.

Unlike the linear variant (where we can use a greedy method with two pointers to complete this task in $$$O(n)$$$ time), the problem is not that simple. So far, I have only found two optimizations based on the brute-force method. One is to use binary search method to find out the least size containing all kinds of integer. The other is while recording the times an integer appears in the subarray, updateing differences between each move rather than counting up again and again. After those optimizations, the time complexity of this method is $$$O(n^3\cdot \log^2 n)$$$, where we use $$$O(\log n)$$$ to binary search the size, $$$O(\ln n)$$$ to enumerate all possible width and height for each size, and $$$O(n^3)$$$ for each possible shape of a specific rectangle.

Since the 1 dimesional variant can be solved in linear time, and with intuition that I thought the 2 dimesional version can be solved in square time. Is there a way to solve this problem in $$$O(n^2)$$$ time? If there is not, what is the lower bound of the time complexity to solve this problem?