Valiant's New Map
Contest: Codeforces Round 841 (Div. 2) and Divide by Zero 2022
Difficulty rating: 1700
Tags: binary search, brute force, data structures, dp, two pointers

Game studio "DbZ Games" wants to introduce another map in their popular game "Valiant". This time, the map named "Panvel" will be based on the city of Mumbai.

Mumbai can be represented as $$$n \times m$$$ cellular grid. Each cell $$$(i, j)$$$ ($$$1 \le i \le n$$$; $$$1 \le j \le m$$$) of the grid is occupied by a cuboid building of height $$$a_{i,j}$$$.

This time, DbZ Games want to make a map that has perfect vertical gameplay. That's why they want to choose an $$$l \times l$$$ square inside Mumbai, such that each building inside the square has a height of at least $$$l$$$.

Can you help DbZ Games find such a square of the maximum possible size $$$l$$$?

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 1000$$$). Description of the test cases follows.

The first line of each test case contains two positive integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le m$$$; $$$1 \leq n \cdot m \leq 10^6$$$).

The $$$i$$$-th of next $$$n$$$ lines contains $$$m$$$ integers $$$a_{i,1}, a_{i,2}, \dots, a_{i,m}$$$ ($$$1 \leq a_{i,j} \leq 10^6$$$) — heights of buildings on the $$$i$$$-th row.

It's guaranteed that the sum of $$$n \cdot m$$$ over all test cases doesn't exceed $$$10^6$$$.

Output format:
For each test case, print the maximum side length $$$l$$$ of the square DbZ Games can choose.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, we can choose the square of side $$$l = 2$$$ (i. e. the whole grid) since the heights of all buildings are greater than or equal to $$$2$$$.

In the second test case, we can only choose the side as $$$1$$$, so the answer is $$$1$$$.

In the third test case, there are no squares of size $$$2$$$ that have all buildings of height at least $$$2$$$, so the answer is $$$1$$$.

Example input:
4
2 2
2 3
4 5
1 3
1 2 3
2 3
4 4 3
2 1 4
5 6
1 9 4 6 5 8
10 9 5 8 11 6
24 42 32 8 11 1
23 1 9 69 13 3
13 22 60 12 14 17

Example output:
2
1
1
3

Editorial:
The basic brute force solution for this problem was to just iterate through all the values of sides possible. Note that the value of sides can range only from $$$1$$$ to $$$1000$$$ as product of $$$n \cdot m$$$ can't exceed $$$10^6$$$, so there can't be a cube having all sides greater than $$$1000$$$. After setting side length (let's say $$$s$$$) we look into all possible submatrices of dimensions $$$s \times s$$$ and see if we can form a cube from any one of those. This could only be possible if there exists a submatrix with its minimum $$$\ge s$$$.
Now, we need to do all these operations efficiently, looking at the constraints. The main thing that we need to do is Binary search on the answer. As obviously, it is possible to make a cube with a smaller side if it is possible to make the one with the current side length.
Now from here, we have two different approaches -
Sparse Table - For a particular side $$$s$$$, check for all submatrices of size $$$s \times s$$$, if their minimum is greater than equal to $$$s$$$. If you find any such submatrix, then this value of side is possible. A minimum can be calculated in $$$O(1)$$$ using sparse tree. You might have tried using segment tree, which takes $$$\log m \cdot \log n$$$ time per query. But it may not to pass with these constraints.
So, the time complexity to solve this problem is $$$O(n \cdot m \cdot \log{(\min{(n, m)})}$$$). It would pass these constraints.
Another $$$O(n \cdot m \cdot \min{(n, m)}$$$) solution where you don't use binary search is also there but would fail with these constraints. The segment tree solution takes $$$O(n \cdot m \cdot \log{n} \cdot \log{m} \cdot \log{(\min{(n, m)})}$$$) . So, only sparse tree can be used.
Prefix Sum - This is a much simpler solution. First, we create another $$$n\times m$$$ matrix, let's say $$$B$$$. Now, for a particular side length $$$s$$$, we take all the indices where the building heights are greater than equal to $$$s$$$ and set the elements of $$$B$$$ at those indices to $$$1$$$. Other elements are set to $$$0$$$.
Now we precalculate the prefix sum for this matrix. Then for each index $$$(i, j)$$$ of the matrix $$$B$$$, we check if the square starting from that index has a prefix sum equal to $$$s^2$$$. If anyone of it does, then this side length for the cube is possible.
Time Complexity is again $$$O(n \cdot m \cdot \log{(\min{(n, m)})})$$$.