Leetcode 769 Solution

This article provides solution to leetcode question 769 (largest-plus-sign)
Categories:
Tags:
Access this page by simply typing in "lcs 769" in your browser address bar if you have bunnylol configured.

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

Solution

class Solution:
    def orderOfLargestPlusSign(self, N: int, mines: List[List[int]]) -> int:
        mines_set = set([tuple(mine) for mine in mines])

        left_mines = [[0] * N for _ in range(N)]
        right_mines = [[0] * N for _ in range(N)]
        top_mines = [[0] * N for _ in range(N)]
        bottom_mines = [[0] * N for _ in range(N)]

        for i in range(N):
            length = 0
            for j in range(N):
                if (i, j) not in mines_set:
                    length += 1
                else:
                    length = 0
                left_mines[i][j] = length

        for i in range(N):
            length = 0
            for j in reversed(range(N)):
                if (i, j) not in mines_set:
                    length += 1
                else:
                    length = 0
                right_mines[i][j] = length

        for j in range(N):
            length = 0
            for i in range(N):
                if (i, j) not in mines_set:
                    length += 1
                else:
                    length = 0
                top_mines[i][j] = length

        for j in range(N):
            length = 0
            for i in reversed(range(N)):
                if (i, j) not in mines_set:
                    length += 1
                else:
                    length = 0
                bottom_mines[i][j] = length

        ans = 0
        for i in range(N):
            for j in range(N):
                local_opt = min(
                    left_mines[i][j],
                    right_mines[i][j],
                    top_mines[i][j],
                    bottom_mines[i][j],
                )

                ans = max(local_opt, ans)
        return ans