C++ O(n^3) Solution (because of hint!)
(I know there is a more efficient O(n^2) solution.)\nHere is a solution by using sum of elements in submatrices.\nAlgorithm :\nStore the sum of submatrices in a
(I know there is a more efficient O(n^2) solution.)\nHere is a solution by using sum of elements in submatrices.\nAlgorithm :\nStore the sum of submatrices in a matrix so that we can access sum of each submatrices in constant time. \nThen loop over every square submatrix in O(n^3).\nif sum of elements in square submatrix = area of that square, then we increment the count.\n\n```\nclass Solution {\npublic:\n    \n    int check(vector<vector<int>>& sum_v,int r1,int c1,int r2,int c2)\n    {\n        int ans = sum_v[r2][c2];\n        \n        if(c1>0)\n            ans -= sum_v[r2][c1-1];\n        if(r1>0)\n            ans -= sum_v[r1-1][c2];\n        if(r1>0 && c1>0)\n            ans += sum_v[r1-1][c1-1];\n        \n\t\t//ans  = sum of submatrix with topleft = (r1,c1) , rightbottom = (r2,c2) \n\t\t\n        if(ans == (r2-r1+1)*(r2-r1+1)) //checking if sum is equal to area of square submatrix.\n            return 1;\n        else return 0;\n    \n    }\n    \n    int countSquares(vector<vector<int>>& matrix) {\n        vector<vector<int>> sum_v(matrix.size(),vector<int>(matrix[0].size()));\n        \n\t\t// storing the sum of each submatrix having topleft = (0,0) and right bottom = (i,j) \n        for(int i=0;i<sum_v.size();i++)\n        {\n            for(int j = 0;j<sum_v[i].size();j++)\n            {\n                if(i==0&&j==0)\n                {\n                    sum_v[i][j] = matrix[i][j];\n                }\n                else if(i==0)\n                {\n                    sum_v[i][j] = sum_v[i][j-1] + matrix[i][j];\n                }\n                else if(j==0)\n                {\n                    sum_v[i][j] = sum_v[i-1][j] + matrix[i][j];\n                }\n                else\n                {\n                    sum_v[i][j] = sum_v[i-1][j] + sum_v[i][j-1] - sum_v[i-1][j-1] + matrix[i][j];\n                }\n            }\n        }\n        \n        \n        int count = 0;\n        for(int i = 0;i<sum_v.size();i++)\n        {\n            for(int j=0;j<sum_v[i].size();j++)\n            {\n\t\t\t\t// looping every square submatrix with right bottom=(i,j), topleft = (i-k,j-k) \n                for(int k = 0; min(i,j)-k >=0 ;k++)\n                {\n                    count+= check(sum_v,i-k,j-k,i,j);\n                }\n            }\n        }\n        \n        return count;\n        \n    }\n};\n```
[]