Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Example:


Input: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Matrices

Dynamic programming

Data structures

Starter code: class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        

Solutions:
class Solution:

	def maximalSquare(self, matrix):
		if not matrix:
			return 0
		(m, n) = (len(matrix), len(matrix[0]))
		dp = [int(matrix[i][0]) for i in range(m)]
		vmax = max(dp)
		pre = 0
		for j in range(1, n):
			(pre, dp[0]) = (int(matrix[0][j - 1]), int(matrix[0][j]))
			for i in range(1, m):
				cur = dp[i]
				dp[i] = 0 if matrix[i][j] == '0' else min(dp[i - 1], dp[i], pre) + 1
				pre = cur
			vmax = max(vmax, max(dp))
		return vmax ** 2


class Solution:

	def maximalSquare(self, matrix):
		if len(matrix) == 0 or len(matrix[0]) == 0:
			return 0
		(n, m) = (len(matrix), len(matrix[0]))
		dp = [[0 for i in range(m)] for j in range(n)]
		for i in range(n):
			dp[i][0] = int(matrix[i][0])
		for j in range(m):
			dp[0][j] = int(matrix[0][j])
		for i in range(1, n):
			for j in range(1, m):
				if matrix[i][j] == '1':
					dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
		ans = 0
		for i in range(n):
			ans = max(ans, max(dp[i]))
		return ans ** 2


class Solution:

	def maximalSquare(self, matrix):
		if not matrix:
			return 0
		(rows, cols) = (len(matrix), len(matrix[0]))
		dp = list(map(int, matrix[0][:]))
		maxLen = 1 if sum(dp) > 0 else 0
		for i in range(1, rows):
			tmp = dp[0]
			dp[0] = int(matrix[i][0])
			maxLen = max(maxLen, dp[0])
			pre = tmp
			for j in range(1, cols):
				tmp = dp[j]
				if matrix[i][j] == '1':
					dp[j] = min(dp[j], dp[j - 1], pre) + 1
					maxLen = max(maxLen, dp[j])
				else:
					dp[j] = 0
				pre = tmp
		return maxLen * maxLen


class Solution:

	def maximalSquare(self, matrix):
		if not matrix:
			return 0
		(rows, cols) = (len(matrix), len(matrix[0]))
		dp = [0] * cols
		maxLen = 1 if sum(dp) > 0 else 0
		for i in range(0, rows):
			for j in range(0, cols):
				if matrix[i][j] == '1':
					if j == 0:
						dp[j] = int(matrix[i][j])
					else:
						k = min(dp[j], dp[j - 1])
						dp[j] = k + 1 if matrix[i - k][j - k] == '1' else k
					maxLen = max(maxLen, dp[j])
				else:
					dp[j] = 0
		return maxLen * maxLen


class Solution:

	def maximalSquare(self, matrix):
		if not matrix or len(matrix) == 0:
			return 0
		m = len(matrix)
		n = len(matrix[0])
		dp = [[0 for i in range(n)] for j in range(m)]
		dp[0] = list(map(lambda x: int(x), matrix[0]))
		maxLength = 1 if 1 in dp[0] else 0
		for i in range(1, m):
			dp[i][0] = int(matrix[i][0])
			if dp[i][0] == 1:
				maxLength = 1
		for i in range(1, m):
			for j in range(1, n):
				if matrix[i][j] == '0':
					dp[i][j] = 0
				else:
					dp[i][j] = 1 + min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1])
					maxLength = max(maxLength, dp[i][j])
		return maxLength ** 2


class Solution:

	def maximalSquare(self, matrix):
		(m, n) = (len(matrix), len(matrix[0]) if matrix else 0)
		dp = [0] * n
		best = 0
		for r in range(m):
			ndp = [0] * n
			for c in range(n):
				if matrix[r][c] == '1':
					ndp[c] = min(dp[c - 1], dp[c], ndp[c - 1]) + 1 if r and c else 1
					if ndp[c] > best:
						best = ndp[c]
			dp = ndp
		return best ** 2


class Solution:

	def maximalSquare(self, matrix):
		g = 0
		li = [[0 for a in x] for x in matrix]
		for i in range(0, len(matrix)):
			for j in range(0, len(matrix[0])):
				c = int(matrix[i][j])
				if c == 0:
					li[i][j] = 0
					continue
				if i == 0 or j == 0:
					li[i][j] = c
					if c > g:
						g = c
					continue
				m = min(li[i - 1][j], li[i][j - 1])
				if li[i - 1][j - 1] <= m:
					li[i][j] = 1 + li[i - 1][j - 1]
				else:
					li[i][j] = 1 + m
				if li[i][j] > g:
					g = li[i][j]
		return g ** 2


class Solution:

	def maximalSquare(self, matrix):
		if len(matrix) == 0 or len(matrix[0]) == 0:
			return 0
		dp = [[0 for i in range(len(matrix[0]))] for i in range(len(matrix))]
		largest = 0
		for i in range(len(matrix)):
			dp[i][0] = int(matrix[i][0])
			largest = max(largest, dp[i][0])
		for j in range(len(matrix[0])):
			dp[0][j] = int(matrix[0][j])
			largest = max(largest, dp[0][j])
		for i in range(1, len(matrix)):
			for j in range(1, len(matrix[0])):
				if matrix[i][j] == '1':
					if dp[i - 1][j] >= dp[i - 1][j - 1] and dp[i][j - 1] >= dp[i - 1][j - 1]:
						dp[i][j] = dp[i - 1][j - 1] + 1
					else:
						dp[i][j] = min(int(dp[i - 1][j]), int(dp[i][j - 1])) + 1
				else:
					dp[i][j] = 0
				largest = max(largest, dp[i][j])
		return largest * largest