Largest Plus Sign

Problem Statement

In this scenario, we are provided with an integer n which defines the dimensions of an n x n binary grid where each cell initially contains the value 1. We are also given an array mines, where each element represents coordinates in the grid that should be set to 0. The coordinates are provided in the format [xi, yi], meaning the value at grid position (xi, yi) needs to be changed to 0.

Our task is to determine the order of the largest "axis-aligned" plus sign made up entirely out of 1s that can be formed within this grid. The order of a plus sign, denoted as k, indicates a center with a value of 1 (grid[r][c] == 1) and four arms extending from the center, each of length k-1. The arms extend upwards, downwards, to the left, and to the right. If no plus sign can be formed, the function should return 0.

Examples

Example 1

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.

Example 2

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.

Approach and Intuition

The task involves forming the largest possible plus sign in a given grid with potential obstacles (indicated by 0s). Here's the step-by-step reasoning for solving the problem:

1. Initial Setup:

   • Construct the grid with default values of 1. Use the mines list to set specific coordinates to 0.

2. Compute Arm Lengths:

   • For each cell in the grid that contains a 1, compute the maximum possible length of arms extending in each direction (up, down, left, right) while avoiding 0s.
   • This can be done by scanning each row and each column in both directions:
     • Calculate and store consecutive 1s distance for every cell for each direction.

3. Calculate Largest Order:

   • For each potential center (1 in the grid), determine the minimal arm length from the four calculated directions. This will ensure that a plus can actually be formed.
   • The smallest of these four lengths determines the largest possible order k for the plus sign centered at that cell.

4. Record the Maximum Found:

   • As you compute the possible plus sign for each center, keep track of the largest value of k found throughout the entire grid.

5. Edge Cases and Constraints Handling:

   • If n is 1 and it has a mine, the largest order is immediately 0.
   • Given the constraints where n can go up to 500 and up to 5000 mines, efficient calculation and storage of potential arm lengths for each cell is necessary for performance.

By employing this methodical approach, we ensure that we traverse each cell optimally and calculate the maximum order of the plus sign, keeping in mind obstructions due to zeroes introduced by the mines.

Solutions

class Solution {
    public int largestPlusSign(int size, int[][] mines) {
        Set<Integer> blocked = new HashSet();
        int[][] grid = new int[size][size];
        
        for (int[] mine: mines)
            blocked.add(mine[0] * size + mine[1]);
        int result = 0, span;
        
        for (int row = 0; row < size; ++row) {
            span = 0;
            for (int col = 0; col < size; ++col) {
                span = blocked.contains(row * size + col) ? 0 : span + 1;
                grid[row][col] = span;
            }
            
            span = 0;
            for (int col = size - 1; col >= 0; --col) {
                span = blocked.contains(row * size + col) ? 0 : span + 1;
                grid[row][col] = Math.min(grid[row][col], span);
            }
        }
        
        for (int col = 0; col < size; ++col) {
            span = 0;
            for (int row = 0; row < size; ++row) {
                span = blocked.contains(row * size + col) ? 0 : span + 1;
                grid[row][col] = Math.min(grid[row][col], span);
            }
            
            span = 0;
            for (int row = size - 1; row >= 0; --row) {
                span = blocked.contains(row * size + col) ? 0 : span + 1;
                grid[row][col] = Math.min(grid[row][col], span);
                result = Math.max(result, grid[row][col]);
            }
        }
        
        return result;
    }
}