Given a matrix A of dimensions NxN where every element is either O or X. Find the largest subsquare surrounded by X.
Example 1:
Input:
N=2
A=[[X,X][X,X]]
Output:
2
Explanation:
The largest square submatrix 
surrounded by X is the whole 
input matrix.
Example 2:
Input:
N=4
A=[[X,X,X,O],[X,O,X,X],
[X,X,X,O],[X,O,X,X]]
Output:
3
Explanation:
Here,the input represents following 
matrix of size 4 x 4
X X X O
X O X X
X X X O
X O X X
The square submatrix starting at 
(0,0) and ending at (2,2) is the 
largest submatrix surrounded by X.
Therefore, size of that matrix would be 3.
Your Task:
You don't need to read input or print anything. Your task is to complete the function largestSubsquare() which takes the integer N and the matrix A as input parameters and returns the size of the largest subsquare surrounded by 'X'.
Expected Time Complexity:O(N^{2})
Expected Auxillary Space:O(N^{2})
Constraints:
1<=N<=1000
A[i][j]={'X','O'}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Matrices

Data structures

Starter code: #User function Template for python3



class Solution:

    def largestSubsquare(self,N,A):

        #code here

Solutions:
class Solution:

	def largestSubsquare(self, N, A):
		m = [[[0 for _ in range(N)] for _ in range(N)] for _ in range(2)]
		for i in range(N):
			m[0][i][0] = 1 if A[i][0] == 'X' else 0
			for j in range(1, N):
				if A[i][j] == 'X':
					m[0][i][j] = m[0][i][j - 1] + 1
		for j in range(N):
			m[1][0][j] = 1 if A[0][j] == 'X' else 0
			for i in range(1, N):
				if A[i][j] == 'X':
					m[1][i][j] = m[1][i - 1][j] + 1
		ans = 0
		for i in range(N):
			for j in range(N):
				d = min(m[0][i][j], m[1][i][j])
				while d > 0:
					if m[0][i - d + 1][j] >= d and m[1][i][j - d + 1] >= d:
						ans = max(d, ans)
						break
					d -= 1
		return ans


class Solution:

	def get_hor_mat(self, n, a, hor):
		for i in range(n):
			for j in range(n):
				if i >= 0 and j == 0:
					if a[i][j] == 'X':
						hor[i][j] = 1
					else:
						hor[i][j] = 0
				elif a[i][j] == 'X':
					hor[i][j] = hor[i][j - 1] + 1
				else:
					continue

	def get_ver_mat(self, n, a, ver):
		for i in range(n):
			for j in range(n):
				if i == 0 and j >= 0:
					if a[i][j] == 'X':
						ver[i][j] = 1
				elif a[i][j] == 'X':
					ver[i][j] = ver[i - 1][j] + 1

	def largestSubsquare(self, n, a):
		hor = [[0 for j in range(n)] for i in range(n)]
		ver = [[0 for j in range(n)] for i in range(n)]
		max_square = 0
		self.get_hor_mat(n, a, hor)
		self.get_ver_mat(n, a, ver)
		for i in range(n - 1, -1, -1):
			for j in range(n - 1, -1, -1):
				min_val = min(hor[i][j], ver[i][j])
				while min_val > max_square:
					if ver[i][j - min_val + 1] >= min_val and hor[i - min_val + 1][j] >= min_val:
						max_square = min_val
					min_val -= 1
		return max_square


class Solution:

	def largestSubsquare(self, N, A):
		(ROWS, COLS) = (len(A), len(A[0]))
		dp = [[[0, 0] for i in range(ROWS + 1)] for j in range(COLS + 1)]
		for i in range(ROWS):
			for j in range(COLS):
				if A[i][j] == 'X':
					dp[i + 1][j + 1][0] = dp[i][j + 1][0] + 1
					dp[i + 1][j + 1][1] = dp[i + 1][j][1] + 1
		maxi = 0
		for i in range(ROWS, 0, -1):
			for j in range(COLS, 0, -1):
				curMin = min(dp[i][j][0], dp[i][j][1])
				while curMin > maxi:
					if dp[i - curMin + 1][j][1] >= curMin and dp[i][j - curMin + 1][0] >= curMin:
						maxi = curMin
					else:
						curMin -= 1
		return maxi


class Solution:

	def largestSubsquare(self, N, A):
		B = [[0] * N for i in range(N)]
		for row in range(N):
			for i in reversed(range(N)):
				if A[row][i] == 'X':
					if i == N - 1:
						B[row][i] = 1
					else:
						B[row][i] = B[row][i + 1] + 1
				else:
					B[row][i] = 0
		C = [[0] * N for i in range(N)]
		for col in range(N):
			for i in reversed(range(N)):
				if A[i][col] == 'X':
					if i == N - 1:
						C[i][col] = 1
					else:
						C[i][col] = C[i + 1][col] + 1
				else:
					C[i][col] = 0
		max_square = 0
		for i in range(N):
			for j in range(N):
				k = min(B[i][j], C[i][j])
				while k > 0:
					if C[i][j + k - 1] >= k and B[i + k - 1][j] >= k:
						if k > max_square:
							max_square = k
						break
					k -= 1
		return max_square
import math
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		a = []
		for i in range(N):
			s = list(map(str, input().strip().split()))
			a.append(s)
		ob = Solution()
		print(ob.largestSubsquare(N, a))


class Solution:

	def largestSubsquare(self, N, A):
		left_c = [[0] * N for i in range(N)]
		top_c = [[0] * N for i in range(N)]
		for i in range(N):
			for j in range(N):
				if A[i][j] == 'X':
					left_c[i][j] = (left_c[i][j - 1] if j > 0 else 0) + 1
					top_c[i][j] = (top_c[i - 1][j] if i > 0 else 0) + 1
		max_len = 0
		for i in range(N - 1, -1, -1):
			for j in range(N - 1, -1, -1):
				val = min(left_c[i][j], top_c[i][j])
				while val > max_len:
					if top_c[i][j - val + 1] >= val and left_c[i - val + 1][j] >= val:
						max_len = max(max_len, val)
					val -= 1
		return max_len


class Solution:

	def largestSubsquare(self, n, a):
		dp = [[[0, 0] for i in range(n)] for i in range(n)]
		dp[0][0] = [1, 1] if a[0][0] == 'X' else [0, 0]
		m = dp[0][0][0]

		def check(i, j, back):
			nonlocal dp
			nonlocal m
			while back > m and (dp[i - back + 1][j][1] < back or dp[i][j - back + 1][0] < back):
				back -= 1
			return back if back > m else m
		for i in range(1, n):
			if a[0][i] == 'X':
				dp[0][i] = [1, dp[0][i - 1][1] + 1]
			if a[i][0] == 'X':
				dp[i][0] = [dp[i - 1][0][0] + 1, 1]
			m = max(m, min(dp[0][i]), min(dp[i][0]))
		for i in range(1, n):
			for j in range(1, n):
				if a[i][j] == 'X':
					dp[i][j][0] = dp[i - 1][j][0] + 1
					dp[i][j][1] = dp[i][j - 1][1] + 1
					x = min(dp[i][j])
					if x > m:
						m = check(i, j, x)
		return m


class Solution:

	def largestSubsquare(self, N, A):
		a = [[[0, 0] for i in range(N)] for i in range(N)]
		for i in range(N):
			for j in range(N):
				if A[i][j] == 'O':
					a[i][j][0] = 0
					a[i][j][1] = 0
				elif A[i][j] == 'X':
					if i - 1 >= 0:
						a[i][j][1] = a[i - 1][j][1] + 1
					else:
						a[i][j][1] = 1
					if j - 1 >= 0:
						a[i][j][0] = a[i][j - 1][0] + 1
					else:
						a[i][j][0] = 1
		max = 0
		for i in range(N):
			for j in range(N):
				aa = min(a[i][j][0], a[i][j][1])
				while aa > max:
					if aa > max and a[i - aa + 1][j][0] >= aa and (a[i][j - aa + 1][1] >= aa):
						max = aa
						break
					aa -= 1
		return max


class Solution:

	def largestSubsquare(self, N, mat):
		Max = 0
		mp = [[(0, 0) for i in range(N)] for i in range(N)]
		for i in range(N):
			for j in range(N):
				if mat[i][j] == 'O':
					mp[i][j] = (0, 0)
				elif i == 0 and j == 0:
					mp[i][j] = (1, 1)
				elif i == 0:
					mp[i][j] = (1, mp[i][j - 1][1] + 1)
				elif j == 0:
					mp[i][j] = (mp[i - 1][j][0] + 1, 1)
				else:
					mp[i][j] = (mp[i - 1][j][0] + 1, mp[i][j - 1][1] + 1)
		for i in range(N - 1, -1, -1):
			for j in range(N - 1, -1, -1):
				small = mp[i][j][0] if mp[i][j][0] < mp[i][j][1] else mp[i][j][1]
				while small > Max:
					if mp[i][j - small + 1][0] >= small and mp[i - small + 1][j][1] >= small:
						Max = small
					small -= 1
		return Max