Given a binary matrix mat of size n * m, find out the maximum size square sub-matrix with all 1s.
Example 1:
Input: n = 2, m = 2
mat = {{1, 1}, 
       {1, 1}}
Output: 2
Explaination: The maximum size of the square
sub-matrix is 2. The matrix itself is the 
maximum sized sub-matrix in this case.
Example 2:
Input: n = 2, m = 2
mat = {{0, 0}, 
       {0, 0}}
Output: 0
Explaination: There is no 1 in the matrix.
Your Task:
You do not need to read input or print anything. Your task is to complete the function maxSquare() which takes n, m and mat as input parameters and returns the size of the maximum square sub-matrix of given matrix.
Expected Time Complexity: O(n*m)
Expected Auxiliary Space: O(n*m)
Constraints:
1 ≤ n, m ≤ 50
0 ≤ mat[i][j] ≤ 1

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3

class Solution:
    def maxSquare(self, n, m, mat):
        # code here

Solutions:
class Solution:

	def maxSquare(self, n, m, mat):
		mx = 0
		dp = [[0 for j in range(m + 1)] for i in range(n + 1)]
		for i in range(n - 1, -1, -1):
			for j in range(m - 1, -1, -1):
				right = dp[i][j + 1]
				diag = dp[i + 1][j + 1]
				down = dp[i + 1][j]
				if mat[i][j] == 1:
					dp[i][j] = 1 + min(right, min(diag, down))
					mx = max(mx, dp[i][j])
				else:
					dp[i][j] = 0
		return mx


class Solution:

	def maxSquare(self, n, m, mat):
		dp = [[0 for i in range(m)] for j in range(n)]
		for j in range(m):
			dp[0][j] = mat[0][j]
		for i in range(n):
			dp[i][0] = mat[i][0]
		for i in range(1, n):
			for j in range(1, m):
				if mat[i][j] == 1:
					dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
		maxi = 0
		for i in range(n):
			for j in range(m):
				maxi = max(maxi, dp[i][j])
		return maxi


class Solution:

	def maxSquare(self, n, m, mat):
		stateMap = [[0 for i in range(m + 1)] for _ in range(n + 1)]
		maxVal = 0
		for r in range(1, n + 1):
			for c in range(1, m + 1):
				if mat[r - 1][c - 1]:
					stateMap[r][c] = 1 + min(stateMap[r - 1][c - 1], stateMap[r - 1][c], stateMap[r][c - 1])
					maxVal = max(maxVal, stateMap[r][c])
		return maxVal


class Solution:

	def maxSquare(self, n, m, mat):
		(m, n) = (n, m)
		out = []
		i = 0
		while i < m:
			j = 0
			temp = []
			while j < n:
				if i == 0 or j == 0:
					temp.append(mat[i][j])
				else:
					temp.append(0)
				j += 1
			out.append(temp)
			i += 1
		i = 1
		while i < m:
			j = 1
			while j < n:
				if mat[i][j] == 1:
					values1 = [out[i - 1][j - 1], out[i - 1][j], out[i][j - 1]]
					min1 = out[i - 1][j - 1]
					k = 1
					while k < 3:
						if values1[k] < min1:
							min1 = values1[k]
						k += 1
					values2 = [mat[i - 1][j - 1], mat[i - 1][j], mat[i][j - 1]]
					min2 = int(mat[i - 1][j - 1])
					k = 1
					while k < 3:
						if values2[k] < min2:
							min2 = values2[k]
						k += 1
					out[i][j] = max(min1 + 1, min2 + 1)
				else:
					out[i][j] = 0
				j += 1
			i += 1
		i = 0
		final_output = 0
		while i < m:
			j = 0
			while j < n:
				final_output = max(final_output, out[i][j])
				j += 1
			i += 1
		return final_output


class Solution:

	def maxSquare(self, n, m, mat):
		s = [[0 for i in range(m)] for j in range(n)]
		for i in range(n):
			s[i][0] = mat[i][0]
		for j in range(m):
			s[0][j] = mat[0][j]
		for i in range(1, n):
			for j in range(1, m):
				if mat[i][j] == 1:
					s[i][j] = min(s[i][j - 1], s[i - 1][j], s[i - 1][j - 1]) + 1
				else:
					s[i][j] = 0
		maxres = 0
		for i in range(n):
			for j in range(m):
				maxres = max(maxres, s[i][j])
		return maxres


import numpy as np

class Solution:

	def dp_sol(self, n, m, mat):
		dp = np.array([[0] * (m + 1)] * (n + 1))
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if mat[i - 1][j - 1] == 1:
					dp[i][j] = min(min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1
				else:
					dp[i][j] = 0
		return np.max(dp)

	def maxSquare(self, n, m, mat):
		return self.dp_sol(n, m, mat)


class Solution:

	def solve(self, mat, i, j, maxi, dp):
		if i >= len(mat) or j >= len(mat[0]):
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		right = self.solve(mat, i, j + 1, maxi, dp)
		diagonal = self.solve(mat, i + 1, j + 1, maxi, dp)
		down = self.solve(mat, i + 1, j, maxi, dp)
		if mat[i][j] == 1:
			dp[i][j] = 1 + min(right, diagonal, down)
			maxi[0] = max(maxi[0], dp[i][j])
			return dp[i][j]
		else:
			dp[i][j] = 0
			return dp[i][j]

	def maxSquare(self, n, m, mat):
		maxi = [0]
		dp = [[-1 for i in range(m)] for j in range(n)]
		self.solve(mat, 0, 0, maxi, dp)
		return maxi[0]


class Solution:

	def maxSquare(self, n, m, mat):
		dp = [[0] * m for i in range(n)]
		sol = 0
		for i in range(n):
			dp[i][0] = t = mat[i][0]
			if t > 0:
				sol = 1
		for i in range(m):
			dp[0][i] = t = mat[0][i]
			if t > 0:
				sol = 1
		for i in range(1, n):
			for j in range(1, m):
				if mat[i][j] == 0:
					continue
				dp[i][j] = t = min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1
				if t > sol:
					sol = t
		return sol


class Solution:

	def maxSquare(self, n, m, a):
		for i in range(1, n):
			for j in range(1, m):
				if a[i][j] != 0:
					a[i][j] = min(a[i - 1][j], min(a[i][j - 1], a[i - 1][j - 1])) + 1
		ans = 0
		for i in range(n):
			for j in range(m):
				ans = max(ans, a[i][j])
		return ans


class Solution:

	def solve(self, i, j, n, m, mat, maxi):
		if i >= n or j >= m:
			return 0
		right = self.solve(i, j + 1, n, m, mat, maxi)
		diagonal = self.solve(i + 1, j + 1, n, m, mat, maxi)
		left = self.solve(i + 1, j, n, m, mat, maxi)
		if mat[i][j] == 1:
			ans = 1 + min(right, diagonal, left)
			maxi[0] = max(maxi[0], ans)
			return ans
		return 0

	def solve_memo(self, i, j, n, m, mat, maxi, F):
		if i >= n or j >= m:
			return 0
		if F[i][j] != -1:
			return F[i][j]
		right = self.solve_memo(i, j + 1, n, m, mat, maxi, F)
		diagonal = self.solve_memo(i + 1, j + 1, n, m, mat, maxi, F)
		left = self.solve_memo(i + 1, j, n, m, mat, maxi, F)
		if mat[i][j] == 1:
			F[i][j] = 1 + min(right, diagonal, left)
			maxi[0] = max(maxi[0], F[i][j])
			return F[i][j]
		else:
			F[i][j] = 0
			return F[i][j]

	def solve_tab(self, n, m, mat, maxi):
		F = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
		for i in range(n - 1, -1, -1):
			for j in range(m - 1, -1, -1):
				right = F[i][j + 1]
				diagonal = F[i + 1][j + 1]
				left = F[i + 1][j]
				if mat[i][j] == 1:
					F[i][j] = 1 + min(right, diagonal, left)
					maxi[0] = max(maxi[0], F[i][j])
				else:
					F[i][j] = 0

	def solve_so(self, n, m, mat, maxi):
		for i in range(n - 1, -1, -1):
			for j in range(m - 1, -1, -1):
				right = mat[i][j + 1] if j + 1 < m else 0
				diagonal = mat[i + 1][j + 1] if i + 1 < n and j + 1 < m else 0
				left = mat[i + 1][j] if i + 1 < n else 0
				if mat[i][j] == 1:
					mat[i][j] = 1 + min(right, diagonal, left)
					maxi[0] = max(maxi[0], mat[i][j])
				else:
					mat[i][j] = 0

	def maxSquare(self, n, m, mat):
		maxi = [0]
		self.solve_so(n, m, mat, maxi)
		return maxi[0]