Largest Plus Sign - Leetcode Solution

Problem Statement:

You are given an integer n. You have an n x n binary grid grid with all values initially 0 and an array mines of k < n * n non-negative integers where mines[i] = [xi, yi] indicates that the cell (xi, yi) has been set to 1 (i.e., is a mine).

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

An axis-aligned plus sign of 1s of order k has some center grid[i][j] == 1 along with four arms of length k - 1 going up, down, left, and right, and made of 1s. Note that there could be 0s or mines anywhere in the arms of the plus sign, and that the center of the plus sign needs to be a 1.

Example:

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 above.

Solution:

For solving this problem, we will use dynamic programming. Firstly, we have to find the largest plus sign at each cell of the grid. For that, we have to calculate the maximum length of a continuous sequence of 1s in each of the four directions (up, down, left, and right) from each cell of the grid. After computing these maximum lengths, we will take the minimum of them, which will give us the order of the largest axis-aligned plus sign of 1s centered at that cell.

Algorithm:

1. Initialize a 2D matrix dp of size nxn, where dp[x][y] will store the maximum length of a continuous sequence of 1s in each of the four directions (up, down, left, and right) starting from the cell (x,y) of the grid.
2. Set each value of dp to n.
3. For each mine in the mines array, set dp[x][y] to 0.
4. For each cell of the grid, do the following: a. Calculate the maximum length of a continuous sequence of 1s going up starting from the current cell (x,y) and store it in dp[x][y]. b. Calculate the maximum length of a continuous sequence of 1s going down starting from the current cell (x,y) and store it in dp[x][y]. c. Calculate the maximum length of a continuous sequence of 1s going left starting from the current cell (x,y) and store it in dp[x][y]. d. Calculate the maximum length of a continuous sequence of 1s going right starting from the current cell (x,y) and store it in dp[x][y]. e. Take the minimum of the four values calculated above and store it in dp[x][y]. This will give us the order of the largest axis-aligned plus sign of 1s centered at the current cell.
5. Initialize a variable maxOrder to 0.
6. For each cell of the grid, do the following: a. Update maxOrder with the minimum value of dp[x][y] and maxOrder itself.
7. Return maxOrder.

Time Complexity:

The time complexity of the algorithm is O(n^2), as we are iterating over each cell of the nxn grid and performing constant time operations.

Space Complexity:

The space complexity of the algorithm is also O(n^2), as we are using the 2D matrix dp to store the maximum length of a continuous sequence of 1s in each of the four directions.

1