[JavaScript] Easy to understand - 2 solutions
SOLUTION 1\n\nIt\'s the brute force solution. We traversal the matrix and find out all squares which begin from the current point.\nYou could use a function ins
### SOLUTION 1\n\nIt\'s the brute force solution. We traversal the matrix and find out all squares which begin from the current point.\nYou could use a function instead of that label break.\n\n```js\nconst countSquares = matrix => {\n  const row = matrix.length;\n  const col = matrix[0].length;\n  let count = 0;\n  for (let x = 0; x < row; ++x) {\n    for (let y = 0; y < col; ++y) {\n      checkMatrix: for (let i = 0; x + i < row && y + i < col; ++i, ++count) {\n        for (let j = 0; j <= i; ++j) {\n          if (matrix[x + i][y + j] === 0 || matrix[x + j][y + i] === 0) break checkMatrix;\n        }\n      }\n    }\n  }\n  return count;\n};\n```\n\nTime complexity: O(row * col * min(row, col))\nSpace complexity: O(1)\n\n### SOLUTION 2\n\nFor solution 1, we may find out that we\'ve done lots of repeated checking.\nFor example, we check the value of [0, 1] for the square starts from [0, 0]. And we check it again for square starts from [0, 1]. The later the point, the more repeated times it may be checked.\nSo how about we use the previous data to calculate the current situation.\n\n1. Traversal the matrix.\n2. For every point, we need to find out the squares which are ends to this point.\n\t- we could use the result of `[x,y-1]`, `[x-1,y]` and `[x-1,y-1]` since we\'ve have them already\n3. Finally, we get the answer.\n\n```js\nconst countSquares = matrix => {\n  let count = 0;\n  for (let i = 0; i < matrix.length; ++i) {\n    for (let j = 0; j < matrix[0].length; ++j) {\n      if (matrix[i][j] === 0) continue;\n      if (i > 0 && j > 0) {\n        matrix[i][j] += Math.min(matrix[i - 1][j], matrix[i][j - 1], matrix[i - 1][j - 1]);\n      }\n      count += matrix[i][j];\n    }\n  }\n  return count;\n};\n```\n\nTime complexity: O(row * col)\nSpace complexity: O(1)
['JavaScript']