Practice/Amazon/Leetcode 764. Largest Plus Sign

Leetcode 764. Largest Plus Sign

CodingMust

Problem

You are given an integer n representing the size of an n × n grid. Initially, all cells in the grid contain the value 1. You are also given a list of mines, where each mine is represented as a coordinate [row, col] that sets the cell at that position to 0.

An axis-aligned plus sign of order k consists of a center cell and exactly k - 1 consecutive cells extending in each of the four cardinal directions (up, down, left, right) from the center, all containing the value 1.

Your task is to find the maximum order of any plus sign that can be formed in the grid.

Requirements

1. Return the order of the largest plus sign that exists in the grid
2. A plus sign of order 1 is just a single cell containing 1
3. All cells of the plus sign (center and arms) must contain 1
4. The plus sign must be axis-aligned (not diagonal)

Constraints

• 1 ≤ n ≤ 500
• 0 ≤ mines.length ≤ 5000
• 0 ≤ mines[i][0], mines[i][1] < n
• All mine coordinates are unique
• Time complexity should be O(n²)
• Space complexity should be O(n²)

Examples

Example 1:

` Input: n = 5, mines = [[4, 2]] Output: 2 Explanation: The grid looks like: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1

A plus sign of order 2 can be centered at (2, 2): 1 1 1 1 1 Each arm has 1 cell extending from the center. `

Example 2:

Input: n = 1, mines = [] Output: 1 Explanation: A single cell forms a plus sign of order 1.

Example 3:

` Input: n = 3, mines = [[1, 1]] Output: 1 Explanation: The grid is: 1 1 1 1 0 1 1 1 1

The center is blocked, so the best we can do is order 1 at any corner. `