CODEWITHSUNDEEP
pythonalgorithmpython-2.7
Lin Ma
Lin Ma

Reputation: 10139

find max square with black border

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.

My major ideas is, keep track of how many black nodes are on top (continuously) and on left (continuously), which is left and top matrix represents. Then, based on the left and top 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.

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 > 0 else 1
            left[i][j] = left[i][j-1] + 1 if j > 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 > 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 an issue, which is pointed by 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]]

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 > 0 else 1
            left[i][j] = left[i][j - 1] + 1 if j > 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 > 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 the issue by j_random_hacker.

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 > 0 else 1
            left[i][j] = left[i][j - 1] + 1 if j > 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 > 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]]

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 > 0 else 1
            left[i][j] = left[i][j - 1] + 1 if j > 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 > 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

Upvotes: 0

Views: 161

Answers (1)

j_random_hacker
j_random_hacker

Reputation: 51226

This isn't logically correct, as the following simple counterexample shows:

011
101
111

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 all candidate square sizes down from x 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.

[EDIT to address updated algorithm]

The new algorithm thinks there is no bordered square in either

0100
1111      1111
0101  or  0101
0111      0111

despite there being a 3x3 one in each.

Stop guessing at fixes and think about how to break down the set of all possible 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 one rectangle. But many more rectangles could have (i, j) as a bottom-right corner -- where are the tests for them?

Upvotes: 1

Related Questions