Problem statement

https://leetcode.com/problems/largest-1-bordered-square/submissions/

Solution 1

For each cell calculate the biggest number of cells with 1 in each direction. Then check all O(n^3) squares, each in O(1).

Complexity

It is O(n^2) for time and O(n^3) for space. Notice, that we can make code faster, if we find not min of 4 values, but check for each if it is >= k + 1.

Code

class Solution:
    def largest1BorderedSquare(self, M):
        m, n = len(M), len(M[0])
        @lru_cache(None)
        def dp(i, j, dx, dy):
            if not 0 <= i < m or not 0 <= j < n or M[i][j] == 0: return 0
            return dp(i + dx, j + dy, dx, dy) + 1
        
        ans = 0
        for i in range(m):
            for j in range(n):
                for k in range(min(m - i, n - j)):
                    if min(dp(i,j,1,0), dp(i,j,0,1), dp(i+k,j+k,-1,0), dp(i+k,j+k,0,-1))>=k+1:
                        ans = max(ans, (k+1)*(k+1))
                    
        return ans

Solution 2

There is solution with better complexity. Let us use similar idea as CF0628E. We will look at diagonals and for each element of fixed diagonal calculate values for left upper corner and for right down corner, which we denote by l and r. No, we want to process one diagonal in time O(n log n). For this notice that if we have element i, then it will reach elements upty i + l[i], calculate these elements for each element of diagonal. Then when we have r[i], we need to look at interval [i - r[i] + 1, i] and find the first element in this range, which is bigger than i: for this element and element i we can create bordered square. So, we need to use segment tree with the following properties:

  1. We need to update elements. In fact we do it only once.
  2. Given range, find the first element, which is bigger than given value i.

What we use is segment tree with maximum operation in the end.

Complexity

It is O(n^2 log n) for time and O(n^2) for space.

Code

class SegmentTree:
    def __init__(self, n, arr):
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.T = [0] * (2 * self.size - 1)
        self.arr = arr

    def _build(self, x, lx, rx):
        if rx - lx == 1:
            if lx < len(self.arr):
                self.T[x] = self.arr[lx]
        else:
            mx = (lx + rx) // 2
            self._build(2 * x + 1, lx, mx)
            self._build(2 * x + 2, mx, rx)
            self.T[x] = max(self.T[2 * x + 1], self.T[2 * x + 2])

    def build(self):
        self._build(0, 0, self.size)

    def _set(self, i, v, x, lx, rx):
        if rx - lx == 1:
            self.T[x] = v
            return
        mx = (lx + rx) // 2
        if i < mx:
            self._set(i, v, 2 * x + 1, lx, mx)
        else:
            self._set(i, v, 2 * x + 2, mx, rx)
        self.T[x] = max(self.T[2 * x + 1], self.T[2 * x + 2])

    def set(self, i, v):
        self._set(i, v, 0, 0, self.size)

    def first_above_(self, v, l, x, lx, rx):
        if self.T[x] < v or rx <= l:
            return -1
        if rx - lx == 1:
            return lx
        mx = (lx + rx) // 2
        res = self.first_above_(v, l, 2 * x + 1, lx, mx)
        if res == -1:
            res = self.first_above_(v, l, 2 * x + 2, mx, rx)
        return res

    def first_above(self, v, l):
        return self.first_above_(v, l, 0, 0, self.size) 

class Solution:
    def largest1BorderedSquare(self, M):
        m, n = len(M), len(M[0])
        @lru_cache(None)
        def dp(i, j, dx, dy):
            if not 0 <= i < m or not 0 <= j < n or M[i][j] == 0: return 0
            return dp(i + dx, j + dy, dx, dy) + 1
        
        ans = 0
        for i, j in [(0, a) for a in range(n)] + [(b, 0) for b in range(1, m)]:
            lend = min(m-i, n-j)
            l = [min(dp(i+p,j+p,1,0), dp(i+p,j+p,0,1)) for p in range(lend)]
            r = [min(dp(i+p,j+p,-1,0), dp(i+p,j+p,0,-1)) for p in range(lend)]
            
            STree = SegmentTree(lend, [i + l[i] for i in range(lend)])
            STree.build()
            for i in range(lend):
                idx = STree.first_above(i, i - r[i] + 1)
                if 0 <= idx <= i:
                    ans = max(ans, i - idx + 1)
        
        return ans*ans

Remark

There seems to be O(n^2) solution, using monotonic deque, but I am not sure of it.