# 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: interview

Starter code:

def count(chessBoard):
	

Solutions:
from collections import defaultdict

def count(chessBoard):
    # Initialize:
    board = chessBoard.copy()
    tally = defaultdict(int)

    # Compute Longest square ending in bottom right corner of each element and tally up:
    for i, row in enumerate(board):
        for j, element in enumerate(row):
            # Edge detection:
            if i == 0 or j == 0:
                continue

            # Compute & Tally:
            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
    #for i in range(n+1):
        #print(grid[i])
    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