Python/JS/C++ O( m*n ) sol by DP [w/ Demo]
Python O( m * n ) sol. by dynamic programming\n\n---\n\nHint & Algorithm:\n\nThink of the dynamic programming technique.\n\nLike what we did in Leetcode #221 Ma
Python O( m * n ) sol. by dynamic programming\n\n---\n\n**Hint** & **Algorithm**:\n\nThink of the **dynamic programming** technique.\n\nLike what we did in [Leetcode #221 Maximal Square](https://leetcode.com/problems/maximal-square/), \nwe had a dynamic programming approach to find the **maximum side length of square** for each matrix cell.\n\nSimilarly, this time, we can use same technique again.\n\nFirst, **find** the **max side length of square for each matrix cell** by dynamic programming with optimal substructure (this will be described later).\n\nSecond, compute the **summation of dynamic programming table**, and we get the **number of all square submatrices** of given input matrix.\n\n---\n\n**Optimal substructure**: for maximum side length of square, in dynamic programming.\n\nLet DP[ *i* ][ *j* ] denote the max side length, and **[ *i* ][ *j* ]** as the **anchor point** (i.e., bottom-right point) of square\n\nFor any i, j with i > 0 and j > 0:\nDP[ *i* ][ *j* ] = 1 + min( DP[ *i* ][ *j* - 1 ] , DP[ *i* - 1 ][ *j* - 1 ] , DP[ *i* ][ *j* - 1 ] ), if matrix[ *i* ][ *j* ] = 1\n\nDP[ *i* ][ *j* ] = matrix[ *i* ][ *j* ] = 0, Otherwise.\n\n---\n\n**Abstract model** for update with optimal substructure:\n\n![image](https://assets.leetcode.com/users/brianchiang_tw/image_1582454810.png)\n\n\n---\n\n**Demo**:\n\n![image](https://assets.leetcode.com/users/brianchiang_tw/image_1582448013.png)\n\n---\n\n![image](https://assets.leetcode.com/users/brianchiang_tw/image_1582448024.png)\n\n---\n\n![image](https://assets.leetcode.com/users/brianchiang_tw/image_1582448030.png)\n\n---\n\n**Implementation**:\nOut-of-place update, with O( m * n ) space, O( m * n ) time\n\nPython:\n\n```\nfrom itertools import chain\n\nclass Solution:\n    def countSquares(self, matrix: List[List[int]]) -> int:\n        \n        # DP[y][x] denotes the largest edge length of square, whose bottom right point is [y][x]\n        dp_table = [ list(row) for row in matrix ]\n        \n        h, w = len(matrix), len(matrix[0])\n        \n        # Visit each matrix cell, except for row_0 and column_0\n        for y in range(1, h):\n            for x in range(1, w):\n                \n                if matrix[y][x]:\n                    \n                    # Make sure matrix[y][x] is 1, thus square can cover current matrix cell.\n                    # Update largest edge length of sqaure, whose bottom right point is [y][x]\n                    \n                    dp_table[y][x] = 1 + min(dp_table[y][x-1],dp_table[y-1][x-1],dp_table[y-1][x])\n        \n        return sum( chain(*dp_table) )\n```\n\n---\n\nJavascript:\n\n```\nvar countSquares = function(matrix) {\n    \n    \n    // DP[y][x] denotes the largest edge length of square, whose bootom right point is [y][x]\n    \n    // shallow copy of matrix\n    dp_table = [...matrix];\n    \n    let [h, w]=[matrix.length, matrix[0].length];\n    \n    // counter of square submatrices with all ones\n    let counter = 0;\n    \n    // Visit each matrix cell, except for row_0 and column_0\n    for( let y=0 ; y < h ; y++){\n        for( let x=0 ; x < w ; x++){\n            \n            if( y && x && matrix[y][x] ){\n                // Make sure matrix[y][x] is 1, thus square can cover current matrix cell.\n                // Update largest edge length of sqaure, whose bottom right point is [y][x]\n                dp_table[y][x] = 1 + Math.min( dp_table[y][x-1], dp_table[y-1][x],dp_table[y-1][x-1] );\n            } \n            \n            counter += matrix[y][x];\n        }\n    }\n    \n    return counter;\n\n};\n\n```\n\n---\n\nC++:\n\n```\nclass Solution {\npublic:\n    int countSquares(vector<vector<int>>& matrix) {\n        \n         // DP[y][x] denotes the largest edge length of square, whose bootom right point is [y][x]\n        vector< vector<int> > dp_table(matrix);\n        \n        int h=matrix.size(), w=matrix[0].size();\n        \n        // counter of square submatrices with all ones\n        int counter = 0;\n        \n        // Visit each matrix cell, except for row_0 and column_0\n        for(size_t y = 0 ; y < h ; y++){\n            for(size_t x = 0 ; x < w ; x++){\n                \n                if( y && x && dp_table[y][x] ){\n                    \n                    // Make sure matrix[y][x] is 1, thus square can cover current matrix cell.\n                    // Update largest edge length of sqaure, whose bottom right point is [y][x]\n                    dp_table[y][x] = 1 + min( { dp_table[y][x-1], dp_table[y-1][x],dp_table[y-1][x-1] }  );\n                }\n                \n                counter += dp_table[y][x];\n            }\n        }\n        \n        return counter;\n    }\n};\n\n```\n\n---\n\nAdvanced **follow-up**:\n\nSince the update direction is from top to bottom, and from left to right in row-major,\nwe can update in-place in matrix without losing needed informaion.\n\nTherefore, we can reduce space cost from O( m * n ) down to O( 1 ) by in-place update.\n\n---\n**Implementation**:\nIn-place update, with O( 1 ) space, O( m * n ) time\n\nPython:\n\n```\nfrom itertools import chain\n\nclass Solution:\n    def countSquares(self, matrix: List[List[int]]) -> int:\n        \n        # DP[y][x] denotes the largest edge length of square, whose bootom right point is [y][x]\n        dp_table = matrix\n        \n        h, w = len(matrix), len(matrix[0])\n        \n        # Visit each matrix cell, except for row_0 and column_0\n        for y in range(1, h):\n            for x in range(1, w):\n                \n                if matrix[y][x]:\n                    \n                    # Make sure matrix[y][x] is 1, thus square can cover current matrix cell.\n                    # Update largest edge length of sqaure, whose bottom right point is [y][x]\n                    \n                    dp_table[y][x] = 1 + min(dp_table[y][x-1],dp_table[y-1][x-1],dp_table[y-1][x])\n        \n        return sum( chain(*dp_table) )\n        \n```\n\n---\n\nJavascript:\n\n```\nvar countSquares = function(matrix) {\n    \n    \n    // DP[y][x] denotes the largest edge length of square, whose bootom right point is [y][x]\n    let dp_table = matrix;\n    \n    let [h, w]=[matrix.length, matrix[0].length];\n    \n    // counter of square submatrices with all ones\n    let counter = 0;\n    \n    // Visit each matrix cell, except for row_0 and column_0\n    for( let y=0 ; y < h ; y++){\n        for( let x=0 ; x < w ; x++){\n            \n            if( y && x && matrix[y][x] ){\n                // Make sure matrix[y][x] is 1, thus square can cover current matrix cell.\n                // Update largest edge length of sqaure, whose bottom right point is [y][x]\n                dp_table[y][x] = 1 + Math.min( dp_table[y][x-1], dp_table[y-1][x],dp_table[y-1][x-1] );\n            } \n            \n            counter += dp_table[y][x];\n        }\n    }\n\n    return counter;\n\n};\n```\n\n---\n\nC++\n\n```\nclass Solution {\npublic:\n    int countSquares(vector<vector<int>>& matrix) {\n        \n         // DP[y][x] denotes the largest edge length of square, whose bootom right point is [y][x]\n        auto& dp_table = matrix;;\n        \n        int h=matrix.size(), w=matrix[0].size();\n        \n        // counter of square submatrices with all ones\n        int counter = 0;\n        \n        // Visit each matrix cell, except for row_0 and column_0\n        for(size_t y = 0 ; y < h ; y++){\n            for(size_t x = 0 ; x < w ; x++){\n                \n                if( y && x && dp_table[y][x] ){\n                    \n                    // Make sure matrix[y][x] is 1, thus square can cover current matrix cell.\n                    // Update largest edge length of sqaure, whose bottom right point is [y][x]\n                    dp_table[y][x] = 1 + min( { dp_table[y][x-1], dp_table[y-1][x],dp_table[y-1][x-1] }  );\n                }\n                \n                counter += dp_table[y][x];\n            }\n        }\n        \n        return counter;\n    }\n};\n```\n\n---\n\nRelated leetcode challenge:\n\n[Leetcode #221 Maximal Square](https://leetcode.com/problems/maximal-square/)\n\n[Leetcode #304 Range Sum Query 2D - Immutable](https://leetcode.com/problems/range-sum-query-2d-immutable/)\n\n[Leetcode #661 Image Smoother](https://leetcode.com/problems/image-smoother/)\n\n[Leetcode #1314 Matrix Block Sum](https://leetcode.com/problems/matrix-block-sum/)\n\n---\n\nReference:\n\n[1] [Wiki: Dynamic programming algorithm framework](https://en.wikipedia.org/wiki/Dynamic_programming#Examples:_Computer_algorithms)\n\n[2] [GfG: Introduction to dynamic programming](https://bit.ly/3bSY3hP)\n\n[3] [Python official docs about list comprehension](https://docs.python.org/3.8/tutorial/datastructures.html?highlight=list%20comprehension#list-comprehensions)\n\n[4] [Python official docs about itertools.chain()](https://docs.python.org/3.8/library/itertools.html#itertools.chain)\n\n---\n\nThanks for your reading.\n\nWish you have a nice day.\n\nMeow~\uD83D\uDE3A
['Dynamic Programming', 'C', 'Python', 'C++', 'JavaScript']