# Task

You are given a `chessBoard`, a 2d integer array that contains only `0` or `1`. `0` represents a chess piece and `1` represents a empty grid. It's always square shape.

Your task is to count the number of squares made of empty grids.

The smallest size of the square is `2 x 2`. The biggest size of the square is `n x n`, where `n` is the size of chess board. 

A square can overlap the part of other squares. For example:

If

```
chessBoard=[
  [1,1,1],
  [1,1,1],
  [1,1,1]
]
```

...there are four 2 x 2 squares in the chess board:

```
[1,1, ]  [ ,1,1]  [ , , ]  [ , , ]
[1,1, ]  [ ,1,1]  [1,1, ]  [ ,1,1]
[ , , ]  [ , , ]  [1,1, ]  [ ,1,1]
```

And one 3 x 3 square:
```
[1,1,1]
[1,1,1]
[1,1,1]
```

Your output should be an object/dict. Each item in it should be: `size:number`, where size is the square's size, and number is the number of squares. 

For example, if there are four `2 x 2` squares and one `3 x 3` square in the chess board, the output should be: `{2:4,3:1}` (or any equivalent hash structure in your language). The order of items is not important, `{3:1,2:4}` is also a valid output.

If there is no square in the chess board, just return `{}`.

# Note

```if:javascript
- `2 <= chessBoard.length <= 400`
```
```if:python
- `2 <= chessBoard.length <= 120`
```
```if:ruby
- `2 <= chessBoard.length <= 130`
```
```if:java
- `2 <= chessBoard.length <= 250`
```
```if:haskell
- `2 <= chessBoard.length <= 120`
```
```if:csharp
- `2 <= chessBoard.Length <= 220`
```

- `5` fixed testcases

- `100` random testcases, testing for correctness of solution

- `100` random testcases, testing for performance of code

- All inputs are valid.

- Pay attention to code performance.

- If my reference solution gives the wrong result in the random tests, please let me know(post an issue). 

# Example

For 
```
chessBoard = [
  [1,1],
  [1,1]
]
```

the output should be `{2:1}`.


For 
```
chessBoard = [
  [0,1],
  [1,1]
]
```

the output should be `{}`.

For 
```
chessBoard = [
  [1,1,1],
  [1,1,1],
  [1,1,1]
]
```

the output should be `{2:4,3:1}`.

For 
```
chessBoard = [
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
```

the output should be `{}`.

Difficulty: MEDIUM
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:
def count(chessBoard):
	

Solutions:
from collections import defaultdict

def count(chessBoard):
	board = chessBoard.copy()
	tally = defaultdict(int)
	for (i, row) in enumerate(board):
		for (j, element) in enumerate(row):
			if i == 0 or j == 0:
				continue
			if element:
				n = board[i][j] = min(board[i - 1][j], board[i][j - 1], board[i - 1][j - 1]) + 1
				for x in range(n, 1, -1):
					tally[x] += 1
	return tally


def count(board):
	(cnt, scan) = ({}, [0] * (len(board) + 1))
	for row in board:
		(prev, scan) = (scan, [0])
		for (n, b) in enumerate(row):
			scan.append(b and min(prev[n], prev[n + 1], scan[n]) + 1)
		for x in scan:
			if x > 1:
				cnt[x] = cnt.get(x, 0) + 1
	for x in range(max(cnt, default=2), 2, -1):
		cnt[x - 1] += cnt[x]
	return cnt


from collections import defaultdict

def count(chessBoard):
	(n, result) = (len(chessBoard), defaultdict(int))
	memo = [[0] * (n + 1) for _ in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			if chessBoard[i - 1][j - 1]:
				memo[i][j] = min(memo[i - 1][j], memo[i][j - 1], memo[i - 1][j - 1]) + 1
				for x in range(2, memo[i][j] + 1):
					result[x] += 1
	return result


def count(board):
	cnt = [0] * (len(board) + 1)
	scan = [0] * (len(board) + 1)
	for row in board:
		(prev, scan) = (scan, [0])
		for (n, b) in enumerate(row):
			scan.append(b and min(prev[n], prev[n + 1], scan[n]) + 1)
		for x in scan:
			cnt[x] += 1
	ans = {}
	for x in range(len(cnt) - 1, 1, -1):
		if not cnt[x]:
			continue
		ans[x] = cnt[x]
		cnt[x - 1] += cnt[x]
	return ans


def count(chessBoard):
	caseDict = dict()
	runRow = [[chessBoard[x][y] for y in range(len(chessBoard))] for x in range(len(chessBoard))]
	runCol = [[chessBoard[x][y] for y in range(len(chessBoard))] for x in range(len(chessBoard))]
	runBox = [[chessBoard[x][y] for y in range(len(chessBoard))] for x in range(len(chessBoard))]
	for x in range(0, len(chessBoard)):
		for y in range(0, len(chessBoard)):
			if y != 0:
				runRow[x][y] = runRow[x][y - 1] + 1 if chessBoard[x][y] == 1 else 0
			if x != 0:
				runCol[x][y] = runCol[x - 1][y] + 1 if chessBoard[x][y] == 1 else 0
			if x != 0 and y != 0:
				runBox[x][y] = min(runBox[x - 1][y - 1] + 1, runRow[x][y], runCol[x][y]) if chessBoard[x][y] == 1 else 0
	cnts = [0 for _ in range(len(chessBoard) + 1)]
	for r in runBox:
		for v in r:
			cnts[v] += 1
	for i in range(len(cnts) - 2, -1, -1):
		cnts[i] = cnts[i] + cnts[i + 1]
	for i in range(2, len(cnts)):
		if cnts[i] > 0:
			caseDict[i] = cnts[i]
	return caseDict


from collections import defaultdict

def count(chessBoard):
	result = defaultdict(int)
	n = len(chessBoard)
	for i in range(1, n):
		for j in range(1, n):
			chessBoard[i][j] = chessBoard[i][j] * (min(chessBoard[i - 1][j], chessBoard[i][j - 1], chessBoard[i - 1][j - 1]) + 1)
	for i in range(1, n):
		for j in range(1, n):
			if chessBoard[i][j] > 1:
				for k in range(2, chessBoard[i][j] + 1):
					result[k] += 1
	return dict(result)


def count(chessBoard):
	d = {}
	count = 0
	size = 2
	l = len(chessBoard)
	coords = []
	for i in range(l):
		for j in range(l):
			if chessBoard[i][j] == 0:
				coords.append([i, j])
	while True:
		for point in coords:
			for i in range(point[0] - size + 1, point[0] + 1):
				chessBoard[i][point[1] - size + 1] = 0
			for i in range(point[1] - size + 1, point[1] + 1):
				chessBoard[point[0] - size + 1][i] = 0
		for i in range(l):
			chessBoard[i][l - size + 1] = 0
		chessBoard[l - size + 1] = [0] * l
		count = sum([sum(x) for x in chessBoard])
		if count > 0:
			d[size] = count
		else:
			break
		size += 1
		count = 0
	return d


import time

def count(board):
	N = len(board)
	dp = board
	size_cnt = {}
	for row in range(1, N):
		for col in range(1, N):
			if board[row][col] == 1:
				size = 1 + min(dp[row - 1][col - 1], min(dp[row - 1][col], dp[row][col - 1]))
				dp[row][col] = size
				if size > 1:
					size_cnt[size] = size_cnt.get(size, 0) + 1
	res = {}
	for k in size_cnt:
		for s in range(2, k + 1):
			res[s] = res.get(s, 0) + size_cnt[k]
	return res


from collections import defaultdict

def count(chessBoard):
	(n, ans) = (len(chessBoard), defaultdict(int))
	grid = [[0] * (n + 1) for i in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			if chessBoard[i - 1][j - 1] != 0:
				grid[i][j] = min(grid[i - 1][j], grid[i][j - 1], grid[i - 1][j - 1]) + 1
				for x in range(2, grid[i][j] + 1):
					ans[x] += 1
	return ans


def count(chessBoard):
	c = chessBoard
	n = len(chessBoard)
	compteur = [0 for k in range(n + 1)]
	copie = [[0 for k in range(n)] for j in range(n)]
	copie[0] = c[0]
	for k in range(1, n):
		copie[k][0] = c[k][0]
	for ligne in range(1, n):
		for col in range(1, n):
			if c[ligne][col]:
				valeur = 1 + min(copie[ligne][col - 1], copie[ligne - 1][col - 1], copie[ligne - 1][col])
				copie[ligne][col] = valeur
				compteur[valeur] += 1
	for k in range(n - 1, 1, -1):
		compteur[k] += compteur[k + 1]
	d = {}
	for (k, v) in enumerate(compteur):
		if v and k > 1:
			d[k] = v
	return d