LeetCode 764: Largest Plus Sign

Problem Restatement

We are given an integer n.

There is an n x n grid where every cell is initially 1.

Some cells are mines. Each mine is given as:

[x, y]

That means:

grid[x][y] = 0

We need to find the largest axis-aligned plus sign made only of 1s.

A plus sign of order k has:

1. one center cell
2. an upward arm of length k - 1
3. a downward arm of length k - 1
4. a left arm of length k - 1
5. a right arm of length k - 1

The center is included in the order.

So a single 1 cell is a plus sign of order 1.

If there is no plus sign, return 0.

Input and Output

Example function shape:

def orderOfLargestPlusSign(n: int, mines: list[list[int]]) -> int:
    ...

Examples

Example 1:

n = 5
mines = [[4, 2]]

Output:

2

The grid is mostly 1s, except cell (4, 2).

A plus sign of order 2 needs one cell in each direction from its center.

One possible center is (2, 2):

    1
    1
1 1 1 1 1
    1

But an order 3 plus sign would need two cells in every direction. The mine at (4, 2) blocks the downward arm for center (2, 2), so the largest order is 2.

Example 2:

n = 1
mines = [[0, 0]]

Output:

0

The only cell is a mine, so there is no plus sign.

First Thought: Try Every Center and Every Size

A direct solution is to try every cell as a center.

For each center, we try to grow a plus sign outward.

For every possible order, check whether the four arms are all 1s.

This works logically, but it is too slow.

There are n^2 possible centers. For each center, checking arms can take up to O(n) time. With repeated checks, the solution can become too expensive.

We need to precompute useful information.

Key Insight

For a cell (r, c) to be the center of a plus sign of order k, it needs at least k consecutive 1s in all four directions, counting the center itself.

That means we need:

left_count[r][c]  >= k
right_count[r][c] >= k
up_count[r][c]    >= k
down_count[r][c]  >= k

So the largest plus sign centered at (r, c) is:

min(left_count, right_count, up_count, down_count)

Then the answer is the maximum of this value over all cells.

Directional Counts

For each cell, compute how many consecutive 1s end at that cell from each direction.

Example row:

1 1 0 1 1 1

Left-to-right counts are:

1 2 0 1 2 3

Right-to-left counts are:

2 1 0 3 2 1

We do the same vertically for top-to-bottom and bottom-to-top.

Instead of storing four separate matrices, we can store one matrix dp.

Initialize every non-mine cell to n.

Then each directional scan updates:

dp[r][c] = min(dp[r][c], count)

After all four scans, dp[r][c] stores the smallest directional count, which is the largest plus order centered at that cell.

Algorithm

1. Create an n x n matrix dp, initially filled with n.
2. Mark all mines as 0.
3. For each row:
   1. scan left to right
   2. scan right to left
4. For each column:
   1. scan top to bottom
   2. scan bottom to top
5. During each scan, keep a count of consecutive 1s.
6. If a cell is a mine, reset the count to 0.
7. Otherwise, increase the count and update dp.
8. Return the maximum value in dp.

Correctness

For any cell (r, c), a plus sign of order k centered there exists exactly when there are at least k consecutive 1s including (r, c) in all four directions.

The left-to-right scan computes the number of consecutive 1s ending at each cell from the left. The right-to-left scan computes the same quantity from the right. The vertical scans compute the corresponding upward and downward counts.

Each scan updates dp[r][c] with the minimum count seen so far. After all four scans, dp[r][c] equals the minimum of the four arm counts. Therefore, it is exactly the largest order of a plus sign centered at (r, c).

The algorithm takes the maximum value over all cells. Since every valid plus sign has some center, and every center’s largest possible order is represented in dp, the returned value is exactly the order of the largest plus sign in the grid.

Complexity

Let n be the grid size.

Implementation

class Solution:
    def orderOfLargestPlusSign(self, n: int, mines: list[list[int]]) -> int:
        dp = [[n] * n for _ in range(n)]

        for r, c in mines:
            dp[r][c] = 0

        for r in range(n):
            count = 0
            for c in range(n):
                if dp[r][c] == 0:
                    count = 0
                else:
                    count += 1
                    dp[r][c] = min(dp[r][c], count)

            count = 0
            for c in range(n - 1, -1, -1):
                if dp[r][c] == 0:
                    count = 0
                else:
                    count += 1
                    dp[r][c] = min(dp[r][c], count)

        for c in range(n):
            count = 0
            for r in range(n):
                if dp[r][c] == 0:
                    count = 0
                else:
                    count += 1
                    dp[r][c] = min(dp[r][c], count)

            count = 0
            for r in range(n - 1, -1, -1):
                if dp[r][c] == 0:
                    count = 0
                else:
                    count += 1
                    dp[r][c] = min(dp[r][c], count)

        answer = 0

        for row in dp:
            answer = max(answer, max(row))

        return answer

Code Explanation

We create the matrix:

dp = [[n] * n for _ in range(n)]

Using n means every cell starts with the largest possible count. Directional scans will reduce it.

Then mines are marked as zero:

for r, c in mines:
    dp[r][c] = 0

A mine cannot be part of any plus sign.

For each row, we scan from left to right:

count = 0

for c in range(n):
    if dp[r][c] == 0:
        count = 0
    else:
        count += 1
        dp[r][c] = min(dp[r][c], count)

The variable count tells how many consecutive non-mine cells we have seen so far.

When we hit a mine, the streak resets.

The right-to-left scan does the same thing from the other side.

Then the column scans do the same thing vertically:

for c in range(n):

After all four scans, each dp[r][c] contains the smallest arm length available in any direction.

Finally, we take the maximum:

answer = 0

for row in dp:
    answer = max(answer, max(row))

That value is the largest plus sign order.

Testing

def run_tests():
    s = Solution()

    assert s.orderOfLargestPlusSign(5, [[4, 2]]) == 2

    assert s.orderOfLargestPlusSign(1, [[0, 0]]) == 0

    assert s.orderOfLargestPlusSign(1, []) == 1

    assert s.orderOfLargestPlusSign(2, []) == 1

    assert s.orderOfLargestPlusSign(3, []) == 2

    assert s.orderOfLargestPlusSign(
        3,
        [[1, 0], [1, 1], [1, 2]],
    ) == 1

    print("all tests passed")

run_tests()

Test meaning: