Valiant's New Map (Codeforces 1731D)
Tags: 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: 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: For each test case, print the maximum side length $$$l$$$ of the square DbZ Games can choose.

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$$$. 

Sample Inputs:
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

Sample Outputs:
2
1
1
3

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict as dd
from collections import deque
import bisect
import heapq

def ri():
    return int(input())

def rl():
    return list(map(int, input().split()))

def solve():
    (n, m) = rl()
    grid = []
    dp = []
    for _ in range(n):
        grid.append(rl())
        dp.append([0] * m)

    def feasible(l):
        if l == 1:
            return True
        if l > min(n, m):
            return False
        for i in range(n):
            for j in range(m):
                dp[i][j] = 0
        for i in range(n):
            if grid[i][0] >= l:
                dp[i][0] = 1
        for j in range(m):
            if grid[0][j] >= l:
                dp[0][j] = 1
        for i in range(1, n):
            for j in range(1, m):
                if grid[i][j] < l:
                    continue
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
                if dp[i][j] >= l:
                    return True
        return False
    (lo, hi) = (1, min(n, m) + 1)
    while lo < hi - 1:
        mid = (lo + hi) // 2
        if feasible(mid):
            lo = mid
        else:
            hi = mid
    print(lo)
mode = 'T'
if mode == 'T':
    t = ri()
    for i in range(t):
        solve()
else:
    solve()

Solution (Python):
import os, sys
from io import BytesIO, IOBase
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from heapq import heappush, heappop
from functools import lru_cache
from itertools import accumulate
import math
import sys
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ii = lambda : int(input())
mii = lambda : map(int, input().split())
fii = lambda : map(float, input().split())
lmii = lambda : list(map(int, input().split()))
i2c = lambda n: chr(ord('a') + n)
c2i = lambda c: ord(c) - ord('a')
mod = 10 ** 9 + 7

def solve():
    (n, m) = mii()
    grid = []
    for _ in range(n):
        grid.append(lmii())
    (left, right) = (1, min(n, m) + 1)

    def check(s):
        up = [[0] * m for _ in range(n)]
        for i in range(n):
            for j in range(m):
                if grid[i][j] < s:
                    continue
                if i == 0:
                    up[i][j] = 1
                else:
                    up[i][j] = up[i - 1][j] + 1
        for i in range(n):
            for j in range(m):
                if up[i][j] < s:
                    up[i][j] = 0
                    continue
                if j == 0:
                    up[i][j] = 1
                else:
                    up[i][j] = up[i][j - 1] + 1
                    if up[i][j] >= s:
                        up = []
                        return True
        up = []
        return False
    while left < right - 1:
        mid = (left + right) // 2
        if check(mid):
            left = mid
        else:
            right = mid
    print(left)
for _ in range(ii()):
    solve()

Solution (Python):
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
for i in range(t):
    (n, m) = [int(k) for k in input().decode('utf-8').rstrip('\r\n').split()]
    w = []
    for j in range(n):
        w.append([int(k) for k in input().decode('utf-8').rstrip('\r\n').split()])
    a = 1
    b = min(n, m) + 1
    while b - a > 1:
        c = (a + b) // 2
        rho = []
        for j in range(n):
            rho.append([0 for k in range(m)])
        for j in range(n):
            if w[j][0] >= c:
                rho[j][0] = 1
        for j in range(m):
            if w[0][j] >= c:
                rho[0][j] = 1
        check = 0
        for j in range(1, n):
            for k in range(1, m):
                if w[j][k] >= c:
                    rho[j][k] = min(rho[j - 1][k], rho[j][k - 1], rho[j - 1][k - 1]) + 1
                    if rho[j][k] >= c:
                        a = c
                        check = 1
                        break
            if check == 1:
                break
        else:
            b = c
    print(a)