Python find the largest square in the matrix dynamic programming

I have a matrix as follows (Python) :

matrix = """
   ...o..o.o
   ...oo....
   ...o....o
   ..o.ooo..
   o...o....
   .oo......
   ..o....o.
   .oo......
   .........
"""

where “o” is an obstacle and I need to find the biggest square in this matrix. and replace corresponding ‘.’ with ‘x’ like below

"""
   xxxo..o.o
   xxxoo....
   xxxo....o
   ..o.ooo..
   o...o....
   .ooxxxx..
   ..oxxxxo.
   .ooxxxx..
   ...xxxx..
""

found similar questions here(SO), but nothing helped.

Answer

It can be done with a complexity of O(n²) using dynamic programming. The idea is that you have a bigger square only when the up, the left and the up-left squares have the same dimension. Otherwise the max square of the current cell is just the smallest square among the squares considered above, increased by 1. Here is the code:

matrix = """
   ...o..o.o
   ...oo....
   ...o....o
   ..o.ooo..
   o........
   .oo......
   ..o....o.
   .oo......
   .........
"""

matrix = [list(r) for r in matrix.split()]
        
dp = [[0] * len(matrix) for _ in range(len(matrix))]
# max_square_dim, row, column
max_squares = [(0, None, None)]

for ri, r in enumerate(matrix):
    for ci, c in enumerate(r):
        dp[ri][ci] = 0 if c == 'o' 
            else (1 if ri == 0 or ci == 0 
            else min(dp[ri - 1][ci], dp[ri][ci - 1], dp[ri - 1][ci - 1]) + 1)
        
        max_squares = [(dp[ri][ci], ri, ci)] if dp[ri][ci] > max_squares[0][0] 
            else (max_squares + [(dp[ri][ci], ri, ci)] if dp[ri][ci] == max_squares[0][0]
            else max_squares)
            

for max_square in max_squares:
    for r in matrix[max_square[1] - max_square[0] + 1:max_square[1] + 1]:
        r[max_square[2] - max_square[0] + 1:max_square[2] + 1] = ['x'] * max_square[0]
      
result = 'n'.join([''.join(r) for r in matrix])
        
print(result)

In the end, when you have to replace the biggest square with all xs, you simply retrieve the indexes of the bottom-right vertex of the max square (stored in max_square) and do a list substitution.

---

EDIT: in case you have multiple biggest square, instead of declaring a single max_square, you have a list of them (in the update code I renamed it to max_squares). Then, every time you encounter a square with the same dimension as the max one, you just append it to the max_squares. However, consider the possibility of overlapping squares.