Given a N*M matrix of ones and zeros, return how many square submatrices have all ones.
Example 1:
Input:
N = 3
M = 4
matrix [ ][ ] =
                      [ [0, 1, 1, 1],
                        [1, 1, 1, 1], 
                        [0, 1, 1, 1] ]
Output: 15
Explanation: 
There are 10 squares of side 1.
There are 4 squares of side 2.
There are 1 squares of side 3.
Total number of squares = 10 + 4 + 1 =15
 
Example 2:
Input:
N = 3
M = 3
matrix [ ][ ] =
                        [ [1, 0, 1],
                        [1, 1, 0], 
                        [1, 1, 0] ]
Output: 7
Explanation: 
There are 6 squares of side 1.
There are 1 squares of side 2.
Total number of squares = 6  + 1 =7
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function countSquares() which takes the interger N, integer M and 2D integer array matrix[ ][ ] as parameters and returns the number of square submatrices have all ones.
Expected Time Complexity: O(N*M)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N,M ≤  3*10^{3}
0 ≤ matrix [ i ][ j ] ≤ 1

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: #User function Template for python3



class Solution:

    def countSquares(self, N, M, matrix):

        # Code here

Solutions:
class Solution:

	def countSquares(self, N, M, matrix):
		su = 0
		dp = [[0] * M for i in range(N)]
		for i in range(N):
			dp[i][0] = matrix[i][0]
		for j in range(M):
			dp[0][j] = 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][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1
				else:
					dp[i][j] = 0
		for i in range(N):
			su = su + sum(dp[i])
		return su


import itertools

class Solution:

	def countSquares(self, n, m, mat):
		for (i, j) in itertools.product(range(1, n), range(1, m)):
			if mat[i][j]:
				mat[i][j] = min(mat[i][j - 1], mat[i - 1][j], mat[i - 1][j - 1]) + 1
		return sum(map(sum, mat))


class Solution:

	def countSquares(self, N, M, matrix):
		(m, n) = (len(matrix), len(matrix[0]))
		res = 0
		dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if matrix[i - 1][j - 1] == 1:
					dp[i][j] = 1 + min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j])
					res = max(res, dp[i][j])
		ans = 0
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				ans += dp[i][j]
		return ans


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def countSquares(self, N, M, matrix):
		ans = 0
		for i in range(N - 1, -1, -1):
			for j in range(M - 1, -1, -1):
				if matrix[i][j] == 0:
					continue
				else:
					right = 0
					down = 0
					diag = 0
					if j + 1 < M:
						right = matrix[i][j + 1]
					if i + 1 < N:
						down = matrix[i + 1][j]
					if i + 1 < N and j + 1 < M:
						diag = matrix[i + 1][j + 1]
					matrix[i][j] = 1 + min(right, diag, down)
				ans += matrix[i][j]
		return ans


class Solution:

	def countSquares(self, N, M, matrix):
		ans = 0
		for i in range(N - 1, -1, -1):
			for j in range(M - 1, -1, -1):
				if matrix[i][j] == 0:
					continue
				else:
					right = 0
					down = 0
					diag = 0
					if j + 1 < M:
						right = matrix[i][j + 1]
					if i + 1 < N:
						down = matrix[i + 1][j]
					if i + 1 < N and j + 1 < M:
						diag = matrix[i + 1][j + 1]
					matrix[i][j] = 1 + min(right, diag, down)
				ans += matrix[i][j]
		return ans


class Solution:

	def countSquares(self, n, m, arr):
		dp = [[0 for i in range(m)] for n in range(n)]
		for i in range(n):
			dp[i][0] = arr[i][0]
		for j in range(m):
			dp[0][j] = arr[0][j]
		for i in range(1, n):
			for j in range(1, m):
				if arr[i][j] == 1:
					dp[i][j] = 1 + min(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1])
		total = 0
		for i in range(n):
			for j in range(m):
				total += dp[i][j]
		return total


class Solution:

	def countSquares(self, N, M, matrix):
		total = 0
		total += sum(matrix[0])
		for i in range(1, N):
			total += matrix[i][0]
		for i in range(1, N):
			for j in range(1, M):
				if matrix[i][j] == 1:
					matrix[i][j] = 1 + min(matrix[i - 1][j - 1], matrix[i - 1][j], matrix[i][j - 1])
					total += matrix[i][j]
		return total


class Solution:

	def countSquares(self, N, M, matrix):
		ans = 0
		for i in range(N - 1, -1, -1):
			for j in range(M - 1, -1, -1):
				if i == N - 1:
					ans += matrix[i][j]
				elif j == M - 1:
					ans += matrix[i][j]
				elif matrix[i][j] != 0:
					mini = 10 ** 9 + 7
					mini = min(matrix[i + 1][j + 1], min(matrix[i][j + 1], matrix[i + 1][j]))
					matrix[i][j] = mini + 1
					ans = ans + matrix[i][j]
		return ans


class Solution:

	def countSquares(self, n, m, matrix):
		dp = [[0] * m for _ in range(n)]
		for j in range(m):
			dp[0][j] = matrix[0][j]
		for i in range(1, n):
			dp[i][0] = matrix[i][0]
		for i in range(1, n):
			for j in range(1, m):
				if matrix[i][j] == 0:
					dp[i][j] = 0
				else:
					dp[i][j] = 1 + min(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1])
		ans = 0
		for i in range(n):
			for j in range(m):
				ans += dp[i][j]
		return ans


class Solution:

	def countSquares(self, M, N, matrix):
		dp = [[0] * N for _ in range(M)]
		dp[0] = matrix[0]
		res = sum(matrix[0])
		for i in range(1, M):
			dp[i][0] = matrix[i][0]
			res += matrix[i][0]
		for i in range(1, M):
			for j in range(1, N):
				if matrix[i][j]:
					dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
				res += dp[i][j]
		return res


class Solution:

	def countSquares(self, N, M, matrix):
		row = N
		col = M
		dp = [[0 for i in range(col)] for j in range(row)]
		total_sum = 0
		for r in range(row):
			for c in range(col):
				if r == 0 or c == 0:
					dp[r][c] = matrix[r][c]
				elif matrix[r][c] == 1:
					dp[r][c] = 1 + min(dp[r - 1][c], dp[r][c - 1], dp[r - 1][c - 1])
			total_sum += sum(dp[r])
		return total_sum


class Solution:

	def countSquares(self, N, M, a):
		(r, c) = (len(a), len(a[0]))
		dp = [[0 for i in range(c)] for i in range(r)]
		for i in range(r):
			for j in range(c):
				if a[i][j]:
					up = dup = left = 0
					if i - 1 >= 0:
						up = dp[i - 1][j]
					if j - 1 >= 0:
						left = dp[i][j - 1]
					if i - 1 >= 0 and j - 1 >= 0:
						dup = dp[i - 1][j - 1]
					dp[i][j] = min(up, left, dup) + 1
		return sum([sum(l) for l in dp])