Python find the largest square in the matrix dynamic programming

Question

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 1

As I suggested earlier, it's easier to work out the solution if you could build up a right data structure to contain all number of consecutive dots first, then work from there. Here is the sample code to show this: (part1 answer here, part 2- leave as your exercise) This code is adopted from another S/O posts (@AlainT), and modify to suite this question/format accordingly. (BTW - your code sample did not work at all, maybe the format issue?)

def bigSquare(matrix):
    spanSize = [ list(map(len,row.split("o"))) for row in matrix ]
    
    # print([s for ss in spanSize for s in ss if s>0]) # your array of numbers
    spans    = [ [c for s in ss
                    for c in range(s,-1,-1)]
                 for ss in spanSize
                ]
    
    #print(f' spans: {spans} ')
    
    result   = (0,0,0,0,0) # area, height, width, top, left
    
    for r,row in enumerate(spans):
        for c in range(len(row)):
            nextSpans = accumulate( (spanRow[c] for spanRow in spans[r:]),min)
            rectSize  = max( [(w*h,h,w) for h,w in enumerate(nextSpans,1)] )
            print(r, c, rectSize)
            
            result    = max(result,rectSize+(r,c))
    return result[0]   # return the Square Area


if __name__ == '__main__':
    matrix =['...o..o.o',
             '...oo....',
             '...o....o',
             '..o.ooo..',
             'o...o....',
             '.oo......',  # <--- start
             '..o....o.',
             '.oo......',
             '.........']
   
    print(bigSquare(matrix))   # Output: 16 

Answer 2

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.