Simple python3 solution | Dynamic Programming
Complexity\n- Time complexity: O(m \cdot n \cdot \min(n, m))\n Add your time complexity here, e.g. O(n) \n\n- Space complexity: O(m \cdot n)\n Add your space co
# Complexity\n- Time complexity: $$O(m \\cdot n \\cdot \\min(n, m))$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(m \\cdot n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n# Code\n``` python3 []\nclass Solution:\n    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n        def get_dp(iter_lines):\n            result = {}\n            for i, line in enumerate(iter_lines):\n                j = 0\n                for elem, it in groupby(line):\n                    length = sum(1 for _ in it)\n                    if elem == 0:  # skip zeros\n                        j += length\n                        continue\n                    for minus in range(length):\n                        result[(i, j)] = length - minus\n                        j += 1\n            return result\n\n        dp_lines = get_dp(grid)\n        if len(dp_lines) == 0:\n            return 0\n\n        n = len(grid)\n        m = len(grid[0])\n        dp_rows = get_dp(\n            (grid[i][j] for i in range(n))\n            for j in range(m)\n        )\n\n        def get_square_side(i, j):\n            max_length = min(\n                dp_lines[(i, j)],\n                dp_rows[(j, i)],\n            )\n            for size in range(max_length, 1, -1):\n                if (\n                    dp_lines[(i + size - 1, j)] >= size\n                    and dp_rows[(j + size - 1, i)] >= size\n                ):\n                    return size\n            return 1\n        \n        result = max(\n            get_square_side(i, j)\n            for i, line in enumerate(grid)\n            for j, elem in enumerate(line)\n            if elem != 0\n        )\n        return result ** 2\n```
['Dynamic Programming', 'Matrix', 'Iterator', 'Prefix Sum', 'Python3']