find max square with black border
<p>For a square matrix, each cell is either black (1) or white (0), trying to find the max sub-square whose border is black. Here is my code with Python 2.7, wondering if logically correct? And any performance improvements? Thanks.</p>

<p>My major ideas is, keep track of how many black nodes are on top (continuously) and on left (continuously), which is <code>left</code> and <code>top</code> matrix represents. Then, based on the <code>left</code> and <code>top</code> tracking, for any node, I will try to find minimal value of top and left continuous black node, then I will base the minimal value to see if a square could be formed.</p>

<pre><code>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]) for i in range(len(A))]
left=[[0] * len(A[0]) for i in range(len(A))]
result = 0

for i in range(len(A)):
    for j in range(len(A[0])):
        if A[i][j] == 1:
            top[i][j] = top[i-1][j] + 1 if i &gt; 0 else 1
            left[i][j] = left[i][j-1] + 1 if j &gt; 0 else 1
print top
print left

for i in range(len(A)):
    for j in range(len(A[0])):
        if A[i][j] == 1:
            top[i][j] = top[i-1][j] + 1 if i &gt; 0 else 1
            left[i][j] = left[i][j-1] + 1 if j &gt; 0 else 1

            x = min(top[i][j], left[i][j])
            if x &gt; 1:
                y = min(left[i-x+1][j], top[i][j-x+1])
                result = max(result, y)

print result
</code></pre>

<p><strong>Edit 1</strong>, fix an issue, which is pointed by j_random_hacker.</p>

<pre><code>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]]

A = [[0,1,1],
     [1,0,1],
     [1,1,1]]

top = [[0] * len(A[0]) for i in range(len(A))]
left = [[0] * len(A[0]) for i in range(len(A))]
result = 0

for i in range(len(A)):
    for j in range(len(A[0])):
        if A[i][j] == 1:
            top[i][j] = top[i - 1][j] + 1 if i &gt; 0 else 1
            left[i][j] = left[i][j - 1] + 1 if j &gt; 0 else 1
print top
print left

for i in range(len(A)):
    for j in range(len(A[0])):
        if A[i][j] == 1:
            top[i][j] = top[i - 1][j] + 1 if i &gt; 0 else 1
            left[i][j] = left[i][j - 1] + 1 if j &gt; 0 else 1

            x = min(top[i][j], left[i][j])
            if x &gt; 1:
                y = min(left[i - x + 1][j], top[i][j - x + 1])
                if x == y:
                    result = max(result, y)

print result
</code></pre>

<p><strong>Edit 2</strong>, address the issue by j_random_hacker.</p>

<pre><code>A = [[0,1,0,0],
     [1,1,1,1],
     [0,1,0,1],
     [0,1,1,1]]

A = [[0,1,1],
     [1,0,1],
     [1,1,1]]

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]) for i in range(len(A))]
left = [[0] * len(A[0]) for i in range(len(A))]
result = 0

for i in range(len(A)):
    for j in range(len(A[0])):
        if A[i][j] == 1:
            top[i][j] = top[i - 1][j] + 1 if i &gt; 0 else 1
            left[i][j] = left[i][j - 1] + 1 if j &gt; 0 else 1
print top
print left

for i in range(len(A)):
    for j in range(len(A[0])):
        if A[i][j] == 1:
            top[i][j] = top[i - 1][j] + 1 if i &gt; 0 else 1
            left[i][j] = left[i][j - 1] + 1 if j &gt; 0 else 1

            x = min(top[i][j], left[i][j])
            while x &gt; 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
</code></pre>

<p><strong>Edit 3</strong>, new fix</p>

<pre><code>A = [[0,1,0,0],
     [1,1,1,1],
     [0,1,0,1],
     [0,1,1,1]]

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]]

A = [[0,1,1],
     [1,0,1],
     [1,1,1]]

top = [[0] * len(A[0]) for i in range(len(A))]
left = [[0] * len(A[0]) for i in range(len(A))]
result = 0

for i in range(len(A)):
    for j in range(len(A[0])):
        if A[i][j] == 1:
            top[i][j] = top[i - 1][j] + 1 if i &gt; 0 else 1
            left[i][j] = left[i][j - 1] + 1 if j &gt; 0 else 1
print top
print left

for i in range(len(A)):
    for j in range(len(A[0])):
        if A[i][j] == 1:
            top[i][j] = top[i - 1][j] + 1 if i &gt; 0 else 1
            left[i][j] = left[i][j - 1] + 1 if j &gt; 0 else 1

            x = min(top[i][j], left[i][j])
            while x &gt; 1:
                y = min(left[i - x + 1][j], top[i][j - x + 1])
                if x &lt;= y:
                    result = max(result, x)
                    break
                x -= 1

print result
</code></pre>

<p>This isn't logically correct, as the following simple counterexample shows:</p>

<pre><code>011
101
111
</code></pre>

<p>This array contains no bordered square, but your code reports that it contains a square of edge length 3.  You need either a third nested loop through <em>all</em> candidate square sizes down from <code>x</code> to 1 (making the solution O(n^3)-time) or, possibly, some more sophisticated data structure that enables an equivalent check to be performed faster.</p>

<p><strong>[EDIT to address updated algorithm]</strong></p>

<p>The new algorithm thinks there is no bordered square in either</p>

<pre><code>0100
1111      1111
0101  or  0101
0111      0111
</code></pre>

<p>despite there being a 3x3 one in each.</p>

<p>Stop guessing at fixes and think about how to break down the set of <em>all possible</em> locations of bordered squares into sets that you can efficiently (or even not-so-efficiently) check.  As I tried to say at the top: For each possible bottom-right corner of a bordered square, your code is currently only checking <em>one</em> rectangle.  But many more rectangles could have (i, j) as a bottom-right corner -- where are the tests for them?</p>

python algorithm python-2.7