python - find max square with black border -

for square matrix, each cell either black (1) or white (0), trying find max sub-square border black. here code python 2.7, wondering if logically correct? , performance improvements? thanks.

my major ideas is, keep track of how many black nodes on top (continuously) , on left (continuously), left , top matrix represents. then, based on left , top tracking, node, try find minimal value of top , left continuous black node, base minimal value see if square formed.

a=[[1,1,0,0,0],    [1,1,1,1,1],    [0,0,1,0,1],    [0,0,1,1,1],    [0,0,0,0,0]]  top=[[0] * len(a[0]) in range(len(a))] left=[[0] * len(a[0]) in range(len(a))] result = 0  in range(len(a)):     j in range(len(a[0])):         if a[i][j] == 1:             top[i][j] = top[i-1][j] + 1 if > 0 else 1             left[i][j] = left[i][j-1] + 1 if j > 0 else 1 print top print left  in range(len(a)):     j in range(len(a[0])):         if a[i][j] == 1:             top[i][j] = top[i-1][j] + 1 if > 0 else 1             left[i][j] = left[i][j-1] + 1 if j > 0 else 1              x = min(top[i][j], left[i][j])             if x > 1:                 y = min(left[i-x+1][j], top[i][j-x+1])                 result = max(result, y)  print result 

edit 1, fix issue, pointed j_random_hacker.

a = [[1, 1, 0, 0, 0],      [1, 1, 1, 1, 1],      [0, 0, 1, 0, 1],      [0, 0, 1, 1, 1],      [0, 0, 0, 0, 0]]  = [[0,1,1],      [1,0,1],      [1,1,1]]  top = [[0] * len(a[0]) in range(len(a))] left = [[0] * len(a[0]) in range(len(a))] result = 0  in range(len(a)):     j in range(len(a[0])):         if a[i][j] == 1:             top[i][j] = top[i - 1][j] + 1 if > 0 else 1             left[i][j] = left[i][j - 1] + 1 if j > 0 else 1 print top print left  in range(len(a)):     j in range(len(a[0])):         if a[i][j] == 1:             top[i][j] = top[i - 1][j] + 1 if > 0 else 1             left[i][j] = left[i][j - 1] + 1 if j > 0 else 1              x = min(top[i][j], left[i][j])             if x > 1:                 y = min(left[i - x + 1][j], top[i][j - x + 1])                 if x == y:                     result = max(result, y)  print result 

edit 2, address issue j_random_hacker.

a = [[0,1,0,0],      [1,1,1,1],      [0,1,0,1],      [0,1,1,1]]  = [[0,1,1],      [1,0,1],      [1,1,1]]  = [[1, 1, 0, 0, 0],      [1, 1, 1, 1, 1],      [0, 0, 1, 0, 1],      [0, 0, 1, 1, 1],      [0, 0, 0, 0, 0]]   top = [[0] * len(a[0]) in range(len(a))] left = [[0] * len(a[0]) in range(len(a))] result = 0  in range(len(a)):     j in range(len(a[0])):         if a[i][j] == 1:             top[i][j] = top[i - 1][j] + 1 if > 0 else 1             left[i][j] = left[i][j - 1] + 1 if j > 0 else 1 print top print left  in range(len(a)):     j in range(len(a[0])):         if a[i][j] == 1:             top[i][j] = top[i - 1][j] + 1 if > 0 else 1             left[i][j] = left[i][j - 1] + 1 if j > 0 else 1              x = min(top[i][j], left[i][j])             while x > 1:                 y = min(left[i - x + 1][j], top[i][j - x + 1])                 if x == y:                     result = max(result, y)                     break                 x -= 1  print result 

edit 3, new fix

a = [[0,1,0,0],      [1,1,1,1],      [0,1,0,1],      [0,1,1,1]]  = [[1, 1, 0, 0, 0],      [1, 1, 1, 1, 1],      [0, 0, 1, 0, 1],      [0, 0, 1, 1, 1],      [0, 0, 0, 0, 0]]  = [[0,1,1],      [1,0,1],      [1,1,1]]  top = [[0] * len(a[0]) in range(len(a))] left = [[0] * len(a[0]) in range(len(a))] result = 0  in range(len(a)):     j in range(len(a[0])):         if a[i][j] == 1:             top[i][j] = top[i - 1][j] + 1 if > 0 else 1             left[i][j] = left[i][j - 1] + 1 if j > 0 else 1 print top print left  in range(len(a)):     j in range(len(a[0])):         if a[i][j] == 1:             top[i][j] = top[i - 1][j] + 1 if > 0 else 1             left[i][j] = left[i][j - 1] + 1 if j > 0 else 1              x = min(top[i][j], left[i][j])             while x > 1:                 y = min(left[i - x + 1][j], top[i][j - x + 1])                 if x <= y:                     result = max(result, x)                     break                 x -= 1  print result 

this isn't logically correct, following simple counterexample shows:

011 101 111 

this array contains no bordered square, code reports contains square of edge length 3. need either third nested loop through all candidate square sizes down x 1 (making solution o(n^3)-time) or, possibly, more sophisticated data structure enables equivalent check performed faster.

[edit address updated algorithm]

the new algorithm thinks there no bordered square in either

0100 1111      1111 0101  or  0101 0111      0111 

despite there being 3x3 1 in each.

stop guessing @ fixes , think how break down set of all possible locations of bordered squares sets can efficiently (or not-so-efficiently) check. tried @ top: each possible bottom-right corner of bordered square, code checking one rectangle. many more rectangles have (i, j) bottom-right corner -- tests them?