[LeetCode] 764. Largest Plus Sign

 Problem : https://leetcode.com/problems/largest-plus-sign/

To solve this problem with brute force approach, we need to check length of the 4 arms of each cell and use the shortest arm as the length of the axis-aligned plus sign which be centered by current cell.

To avoid repeatedly calculating arm length, we can use prefix-sum to accelerate.

Time complexity = O ( N * N )

class Solution:
    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:
        
        dp1 = [[0] * n for _ in range(n)]
        dp2 = [[0] * n for _ in range(n)]
        
        mineSet = {(y,x) for y, x in mines}
        
        for y in range(n):
            # left to right
            dp1[y][0] = 0
            for x in range(1, n):
                if (y, x) in mineSet or (y, x-1) in mineSet:
                    dp1[y][x] = 0
                else:
                    dp1[y][x] = dp1[y][x-1] + 1
        
            dp1[y][-1] = 0 
            # right to left
            for x in reversed(range(n-1)):
                if (y, x) in mineSet or (y, x+1) in mineSet:
                    dp1[y][x] = 0
                else:
                    dp1[y][x] = min(dp1[y][x], dp1[y][x+1] + 1)
        
        for x in range(n):
            # top to bottom
            dp2[0][x] = 0
            for y in range(1, n):
                if (y, x) in mineSet or (y-1, x) in mineSet:
                    dp2[y][x] = 0
                else:
                    dp2[y][x] = dp2[y-1][x] + 1
            
            dp2[-1][x] = 0
            # bottom to top
            for y in reversed(range(n-1)):
                if (y, x) in mineSet or (y+1, x) in mineSet:
                    dp2[y][x] = 0
                else:
                    dp2[y][x] = min(dp2[y][x], dp2[y+1][x] + 1)
        
        result = 0
        
        for y in range(n):
            for x in range(n):
                if (y, x) not in mineSet: 
                    result = max(result, min(dp1[y][x], dp2[y][x]) + 1)
        
        return result