C++ Code (Based on Histogram Approach)
Intuition\n Describe your first thoughts on how to solve this problem. \nThis problem can be solved using Dynamic Programming but since constraints permit us to
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThis problem can be solved using Dynamic Programming but since constraints permit us to broaden our thinking horizon. We can use histogram approach and the task boils down to **count the number of square-submatrices ending at matrix[i][j]** where i is row and j is column of cell. At the end, we have to return the sum of all such submatrices\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nFirst of all, we generate **previous smaller element using stack**, a very popular question in itself. Then we will traverse row by row and count for every cumulative array of size equal to column size of matrix, which considers ith row as base.\nCumulative array(denoted by ca) is generated as follows:\nEg: If matrix is \n    1, 0, 0, 1\n    0, 1, 1, 1\n    1, 1, 0, 1\nthen for first iteration, i.e. considering only 1st row\nca = {1,0,0,1}\nthen for second iteration, i.e.\nca = {0,1,1,2}\nand at last\nca = {1,2,0,3}\nNow, we count the square submatrices as presented in the code.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(N*M*M) where N*M is size of given matrix\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(M) where N*M is the size of given matrix\n# Code\n```\n/* Based on Largest Area of Histogram or simply Histogram approach, no DP */\n//Code with comments\nclass Solution\n{\npublic:\n    // @Function Desc\n    // for every element, returns index of element smaller to an element peresent on an index  \n    // -1 indicates no such index exists\n    vector<int> prevSmaller(vector<int> &heights, int n)\n    {\n        stack<int> st;\n        st.push(-1);\n        vector<int> ans(n);\n        for (int i = 0; i < n; ++i)\n        {\n            int curr = heights[i];\n            while (st.top() != -1 && heights[st.top()] >= curr)\n            {\n                st.pop();\n            }\n            ans[i] = st.top();\n            st.push(i);\n        }\n        return ans;\n    }\n\n    // @Function Desc:\n    //for an array, return sum of count of count of square sub-matrices for every possible\n    //index of cumulative array\n    int solve(vector<int> &heights)\n    {\n        int r = 0;\n        int n = heights.size();\n        vector<int> prev = prevSmaller(heights, n);\n        for (int i = 0; i < n; i++)\n        {\n            //is_sq represents whether submatrix ending at heights[i] is square or not\n            bool is_sq = true;\n            for (int h = 0; h < heights[i]; h++)\n            {\n                //if height to be checked is greater than index, we break\n                if (h > i)\n                {\n                    break;\n                }\n                //we check for all possible heights\n                for (int x = i; x >= i - h; x--)\n                {\n                    //is cumulative heights is lesser, such a square is not possible\n                    if (heights[x] < h + 1)\n                    {\n                        is_sq = false;\n                        break;\n                    }\n                }\n                if (!is_sq)\n                {\n                    break;\n                }\n                //submatrix is indeed a square\n                r += 1;\n            }\n        }\n        return r;\n    }\n    \n\n    // @Func Desc: The given function in the question\n\n    int countSquares(vector<vector<int>> &matrix)\n    {\n        int row = matrix.size();\n        int col = matrix[0].size();\n        vector<int> heights(col, 0);\n        int maxi = 0;\n        for (int i = 0; i < row; i++)\n        {\n            for (int j = 0; j < col; j++)\n            {\n                //Cumulative array formation\n                if (matrix[i][j] == 1)\n                    heights[j]++;\n                else\n                    heights[j] = 0;\n            }\n            maxi += solve(heights);\n        }\n        return maxi;\n    }\n};\n```\nPlease upvote if it added some worth.\n
['Array', 'Stack', 'Matrix', 'Monotonic Stack', 'C++']