grid47 Exploring patterns and algorithms
Aug 22, 2024
7 min read
Solution to LeetCode 764: Largest Plus Sign Problem
You are given an integer n, which represents the size of an n x n binary grid. Initially, all the values in the grid are set to 1, except for some indices that are specified in the array mines. Your task is to find the order of the largest axis-aligned plus sign of 1’s in the grid. A plus sign of order k has a center grid[r][c] == 1 with arms extending in all four directions (up, down, left, right) of length k - 1.
Problem
Approach
Steps
Complexity
Input: The input consists of an integer n and an array mines where each element is a pair of integers [xi, yi] indicating the grid coordinates that are 0.
Example: Input: n = 6, mines = [[3, 2], [1, 3]]
Constraints:
• 1 <= n <= 500
• 1 <= mines.length <= 5000
• 0 <= xi, yi < n
• All the pairs (xi, yi) are unique.
Output: Return the order of the largest plus sign of 1's contained in the grid. If there is no such plus sign, return 0.
Example: Output: 2
Constraints:
• The returned order will be an integer representing the largest possible order of the plus sign.
Goal: The goal is to compute the largest order of a plus sign in the binary grid considering the mines at the specified positions.
Steps:
• Initialize a grid of size n x n with all 1's.
• Set the specified mines in the grid to 0.
• For each cell, compute the maximum length of the plus sign arms in all four directions.
• Track the maximum possible order of the plus sign.
Goal: The grid has a size of n x n, and we need to handle up to 5000 mines.
Steps:
• Handle grids with a size up to 500 x 500.
• Ensure all mine positions are valid (unique and within bounds).
Assumptions:
• The grid initially contains all 1's, and mines are specified as 0's.
• Input: Example 1: Input: n = 6, mines = [[3, 2], [1, 3]]
• Explanation: In this case, the grid can form a plus sign of order 2, with arms extending in all four directions.
Approach: We can solve the problem by first marking the positions of the mines and then calculating the largest possible plus sign by examining the grid's arms in each direction.
Observations:
• The size of the grid is manageable, but we need to handle up to 5000 mines.
• The plus sign is formed from the center, so we need to compute the possible length of arms in each direction.
• A dynamic approach can help by computing the maximum arm lengths as we iterate over the grid.
Steps:
• Create a grid of size n x n initialized with 1's.
• For each mine, set the corresponding grid cell to 0.
• Iterate through the grid and compute the maximum arm length for each cell in the four directions.
• Return the maximum order of the plus sign.
Empty Inputs:
• If n is 1 and the only cell is a mine, return 0.
Large Inputs:
• Ensure that the solution works efficiently for the largest possible grid size and number of mines.
Special Values:
• If no mines are specified, the entire grid may form a plus sign.
Constraints:
• Handle edge cases like small grid sizes and grids with multiple mines.
intorderOfLargestPlusSign(int n, vector<vector<int>>& mines) {
vector<vector<int>> grid(n, vector<int>(n, n));
for(auto&m: mines)
grid[m[0]][m[1]] =0;
for(int i =0; i < n; i++)
for(int j =0, k = n -1, l =0, r =0, u =0, d =0; j < n; j++, k--) {
grid[i][j] = min(grid[i][j], l = (grid[i][j] ==0?0: l +1));
grid[i][k] = min(grid[i][k], r = (grid[i][k] ==0?0: r +1));
grid[j][i] = min(grid[j][i], u = (grid[j][i] ==0?0: u +1));
grid[k][i] = min(grid[k][i], d = (grid[k][i] ==0?0: d +1));
}
int res =0;
for(int i =0; i < n; i++)
for(int j =0; j < n; j++)
res = max(grid[i][j], res);
return res;
}
1 : Function Declaration
intorderOfLargestPlusSign(int n, vector<vector<int>>& mines) {
This line declares the function `orderOfLargestPlusSign`, which takes the size of the grid (`n`) and a list of mines as inputs, and returns an integer representing the order of the largest plus sign.
2 : Grid Initialization
vector<vector<int>> grid(n, vector<int>(n, n));
This line initializes a 2D grid of size `n x n` with all values set to `n`, indicating the largest possible size of a plus sign at each point initially.
3 : Mines Loop
for(auto&m: mines)
This loop iterates over the list of `mines`, where each mine represents a blocked cell in the grid.
4 : Marking Mines
grid[m[0]][m[1]] =0;
For each mine, this line sets the corresponding grid cell to 0, marking it as a blocked cell.
5 : Grid Processing Start
for(int i =0; i < n; i++)
This outer loop iterates through each row of the grid.
6 : Grid Processing Inner Loop
for(int j =0, k = n -1, l =0, r =0, u =0, d =0; j < n; j++, k--) {
This inner loop processes each column of the grid. It also initializes variables for left, right, up, and down direction counts.
7 : Left Direction Calculation
grid[i][j] = min(grid[i][j], l = (grid[i][j] ==0?0: l +1));
This line updates the grid value in the left direction, setting the number of consecutive non-zero cells.
8 : Right Direction Calculation
grid[i][k] = min(grid[i][k], r = (grid[i][k] ==0?0: r +1));
This line updates the grid value in the right direction, counting consecutive non-zero cells.
9 : Up Direction Calculation
grid[j][i] = min(grid[j][i], u = (grid[j][i] ==0?0: u +1));
This line updates the grid value in the upward direction, counting consecutive non-zero cells.
10 : Down Direction Calculation
grid[k][i] = min(grid[k][i], d = (grid[k][i] ==0?0: d +1));
This line updates the grid value in the downward direction, counting consecutive non-zero cells.
11 : Result Initialization
int res =0;
This line initializes a variable `res` to keep track of the maximum order of the plus sign.
12 : Outer Loop
for(int i =0; i < n; i++)
This outer loop iterates through each row of the grid again.
13 : Inner Loop
for(int j =0; j < n; j++)
This inner loop iterates through each column of the grid.
14 : Finding Maximum
res = max(grid[i][j], res);
This line updates `res` with the maximum value from the grid, which represents the largest order of the plus sign.
15 : Return Result
return res;
This line returns the result, which is the order of the largest plus sign found.
Best Case: O(n^2) where n is the size of the grid, as we need to process each cell in the grid.
Average Case: O(n^2) for grids of typical size with up to 5000 mines.
Worst Case: O(n^2) in the worst case, as we need to check every cell for the largest plus sign.
Description: Time complexity is quadratic due to the two nested loops required to process each cell.
Best Case: O(n^2) as we store the grid and the arms information for each cell.
Worst Case: O(n^2) due to the space used by the grid.
Description: Space complexity is quadratic because we maintain an n x n grid and additional variables for calculating arm lengths.
