C# Solution for Count Square Submatrices With All Ones Problem
Intuition\n Describe your first thoughts on how to solve this problem. \nThe intuition behind this approach is:\n\n\u2022\tFor every cell (i, j) that has a 1, t
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe intuition behind this approach is:\n\n\u2022\tFor every cell (i, j) that has a 1, treat it as a potential top-left corner of a square submatrix.\n\u2022\tGradually expand the square\u2019s side length from 1 upwards until we either reach a 0 (which breaks the square) or reach the matrix boundaries.\n\u2022\tCount each successfully formed square by expanding from the top-left corner, thereby capturing all squares of size 1x1, 2x2, etc., that can be formed from each starting point.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1.\tIterate Over All Cells:\n\t\u2022\tLoop through each cell in the matrix. If a cell contains a 1, it can serve as the top-left corner of potential squares.\n2.\tSquare Expansion:\n\t\u2022\tFor each cell with 1, attempt to expand squares of increasing size. For a square of side length k, ensure all entries within the square boundary (bottom row and rightmost column) are 1.\n\t\u2022\tFor each expansion, check the cells along the current boundary. If any cell along the boundary is 0, stop expanding for that cell.\n\t\u2022\tEach time we successfully expand by 1 unit, it represents a new square, so increment the count.\n3.\tSumming Counts:\n\t\u2022\tCount each valid square formed during the expansion phase and add it to the total count.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nTime Complexity: O(m x n x {min}(m, n))\n\u2022\tFor each cell (i, j), we try expanding squares up to the size of the smallest dimension (either rows or columns) starting from that cell.\n\u2022\tEach expansion step requires a boundary check along the expanding square, leading to an average complexity of O({min}(m, n)) per cell.\n\u2022\tTherefore, the overall time complexity is O(m x n x {min}(m, n)).\n\u2022\tThis approach can be slower than the dynamic programming solution, especially for larger matrices.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nSpace Complexity: O(1)\n\u2022\tThis approach only uses constant space, as we count squares directly without storing intermediate results or additional structures (ignoring the input matrix itself).\n\n# Code\n```csharp []\npublic class Solution {\n    public int CountSquares(int[][] matrix) {\n        int rows = matrix.Length;\n        int cols = matrix[0].Length;\n        int count = 0;\n        for (int i = 0; i < rows; i++) {\n            for (int j = 0; j < cols; j++) {\n                if (matrix[i][j] == 1) {\n                    int maxSize = Math.Min(rows - i, cols - j);\n                    for (int size = 1; size <= maxSize; size++) {\n                        bool isSquare = true;\n                        for (int x = 0; x < size && isSquare; x++) {\n                            if (matrix[i + x][j + size - 1] == 0 || matrix[i + size - 1][j + x] == 0) {\n                                isSquare = false;\n                            }\n                        }\n                        if (isSquare) {\n                            count++;  \n                        } else {\n                            break;  \n                        }\n                    }\n                }\n            }\n        }\n\n        return count;\n    }\n}\n```
['C#']