Given a `m * n`

matrix of ones and zeros, return how many **square** submatrices have all ones.

**Example 1:**

Input:matrix = [ [0,1,1,1], [1,1,1,1], [0,1,1,1] ]Output:15Explanation:There are10squares of side 1. There are4squares of side 2. There is1square of side 3. Total number of squares = 10 + 4 + 1 =15.

**Example 2:**

Input:matrix = [ [1,0,1], [1,1,0], [1,1,0] ]Output:7Explanation:There are6squares of side 1. There is1square of side 2. Total number of squares = 6 + 1 =7.

**Constraints:**

`1 <= arr.length <= 300`

`1 <= arr[0].length <= 300`

`0 <= arr[i][j] <= 1`

## Solution

### C# Program with DP Approach

In this program, instead of creating of new 2d array, I solved the problem in-place of the array.

using System; namespace LeetcodeProgram { class Program { //Driver static void Main(string[] args) { int[][] arr = new int[2][]; int[,] matrix = new int[3, 3] { { 1, 0, 1 }, { 1, 1, 0 }, { 1, 1, 0 } }; /* [[1,0,1], [1,1,0], [1,1,0]] */ int result = CountSquares(matrix); Console.WriteLine("CountSquares is {0}", result); } public static int CountSquares(int[,] matrix) { int row = matrix.GetLength(0); int col = matrix.GetLength(1); int sum = 0; for(int i=1;i<row;i++) { for(int j=1;j<col;j++) { if(matrix[i,j] != 0 && matrix[i-1,j-1] != 0 && matrix[i-1,j] != 0 && matrix[i,j-1] != 0) { matrix[i, j] = Math.Min(Math.Min(matrix[i - 1, j], matrix[i, j - 1]), matrix[i - 1, j - 1]) + 1; } sum += matrix[i, j]; } } //First Row for(int i = 0; i < col; i++) { if (matrix[0, i] != 0) sum += matrix[0, i]; } //First Column for(int i=1;i<row;i++) { if (matrix[i, 0] != 0) sum += matrix[i, 0]; } return sum; } } }

Time Complexity; O(m x n)

Space Complexity: O(1) Since, I never created any new arrays.