Largest Plus Sign Python Solution with Tests

Tested Python solution for LeetCode 764 with 17 pytest cases. Generate a practice environment with lcpy.

LeetCode 764, Medium. Topics: Array, Dynamic Programming. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 17 parametrized pytest cases, and a playground notebook:

lcpy gen -n 764   # by problem number
lcpy gen -s largest_plus_sign   # by problem name

​

Problem

You are given an integer n. You have an n x n binary grid grid with all values initially 1’s except for some indices given in the array mines. The i^th element of the array mines is defined as mines[i] = [x_i, y_i] where grid[x_i][y_i] == 0.

Return the order of the largest axis-aligned plus sign of 1*‘s contained in* grid. If there is none, return 0.

An axis-aligned plus sign of 1’s of order k has some center grid[r][c] == 1 along with four arms of length k - 1 going up, down, left, and right, and made of 1’s. Note that there could be 0’s or 1’s beyond the arms of the plus sign, only the relevant area of the plus sign is checked for 1’s.

​

Examples

Input: n = 5, mines = [[4,2]]
Output: 2
Explanation: In the above grid, the largest plus sign can only be of order 2. One of them is shown.

Input: n = 1, mines = [[0,0]]
Output: 0
Explanation: There is no plus sign, so return 0.

​

Constraints

• 1 <= n <= 500
• 1 <= mines.length <= 5000
• 0 <= xi, yi < n
• All the pairs (xi, yi) are unique.

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(n^2)
    # Space: O(n^2)
    def order_of_largest_plus_sign(self, n: int, mines: list[list[int]]) -> int:
        blocked = {(x, y) for x, y in mines}

        # dp[r][c] = length of the run of 1s ending at (r, c) in the current direction
        dp = [[n] * n for _ in range(n)]

        for r in range(n):
            # left to right
            run = 0
            for c in range(n):
                run = 0 if (r, c) in blocked else run + 1
                dp[r][c] = min(dp[r][c], run)
            # right to left
            run = 0
            for c in range(n - 1, -1, -1):
                run = 0 if (r, c) in blocked else run + 1
                dp[r][c] = min(dp[r][c], run)

        for c in range(n):
            # top to bottom
            run = 0
            for r in range(n):
                run = 0 if (r, c) in blocked else run + 1
                dp[r][c] = min(dp[r][c], run)
            # bottom to top
            run = 0
            for r in range(n - 1, -1, -1):
                run = 0 if (r, c) in blocked else run + 1
                dp[r][c] = min(dp[r][c], run)

        return max(max(row) for row in dp)

​

Complexity

Time	Space
O(n^2)	O(n^2)

​

Tags