You are given an integer N representing the size of an N x N grid. The grid initially contains all 1s. You are also given a list of positions called mines, where each mine is a cell containing 0 instead of 1.
A plus sign of order k is defined as a center cell and four arms (up, down, left, right) of length k-1, where all involved cells must have value 1 (not a mine). The order is the minimum number of continuous 1s from the center to the edge of the arms (including the center itself).
Your task is to find the largest possible order of a plus sign that can be formed in the grid after placing the mines. If no plus sign can be formed, return 0.
N (integer), mines (list of [row, col] integer pairs)
The brute-force approach would be to consider every cell as a potential center and check in all four directions (up, down, left, right) how far we can go before hitting a mine or the edge. For each cell, we would calculate the minimum distance to a mine in each direction, and the smallest among them determines the order of the plus sign centered at that cell.
However, this approach is inefficient because it requires checking up to O(N) cells in each direction for every cell, leading to O(N^3) time complexity.
To optimize, we can precompute, for every cell, the maximum length of continuous 1s in all four directions. By storing these values, we can compute the order of the plus sign at each cell in constant time. This reduces the overall complexity significantly.
N x N grid, initializing all values to N (the maximum possible order).
0 (since you cannot build a plus sign through a mine).
1s in each direction (left, right, up, down) up to that cell.
0 when a mine is encountered.
0.
Example Input:
N = 5, mines = [[4, 2]]
The initial grid is all 1s except for cell (4, 2), which is 0.
For each cell, we calculate the number of consecutive 1s in each direction:
(2, 2) (center), the arms can extend up to 2 cells in each direction before hitting the edge or a mine.(4, 2), it is a mine, so its value is 0.
After processing, the largest value found in the grid is 2, which means the largest plus sign has order 2.
O(N) cells in each direction, leading to O(N^3) time complexity.
O(N^2) for the grid.
O(N^2), so total time is O(N^2).
O(N^2) for the grid.
The key insight is to precompute the arm lengths in all directions for each cell, allowing us to efficiently determine the largest possible plus sign order in the grid. This dynamic programming approach reduces the time complexity from cubic to quadratic, making it scalable for large grids. By updating each cell with the minimum arm length, we ensure that only valid plus signs are considered, resulting in an elegant and efficient solution.
class Solution:
def orderOfLargestPlusSign(self, N: int, mines: List[List[int]]) -> int:
banned = { (i,j) for i,j in mines }
grid = [[0]*N for _ in range(N)]
for i in range(N):
for j in range(N):
grid[i][j] = 0 if (i,j) in banned else N
for i in range(N):
count = 0
for j in range(N):
count = 0 if grid[i][j]==0 else count+1
grid[i][j] = min(grid[i][j], count)
count = 0
for j in range(N-1,-1,-1):
count = 0 if grid[i][j]==0 else count+1
grid[i][j] = min(grid[i][j], count)
for j in range(N):
count = 0
for i in range(N):
count = 0 if grid[i][j]==0 else count+1
grid[i][j] = min(grid[i][j], count)
count = 0
for i in range(N-1,-1,-1):
count = 0 if grid[i][j]==0 else count+1
grid[i][j] = min(grid[i][j], count)
return max(max(row) for row in grid)
class Solution {
public:
int orderOfLargestPlusSign(int N, vector<vector<int>>& mines) {
vector<vector<int>> grid(N, vector<int>(N, N));
for (auto& mine : mines) {
grid[mine[0]][mine[1]] = 0;
}
for (int i = 0; i < N; ++i) {
int count = 0;
for (int j = 0; j < N; ++j) {
count = (grid[i][j] == 0) ? 0 : count + 1;
grid[i][j] = min(grid[i][j], count);
}
count = 0;
for (int j = N - 1; j >= 0; --j) {
count = (grid[i][j] == 0) ? 0 : count + 1;
grid[i][j] = min(grid[i][j], count);
}
}
for (int j = 0; j < N; ++j) {
int count = 0;
for (int i = 0; i < N; ++i) {
count = (grid[i][j] == 0) ? 0 : count + 1;
grid[i][j] = min(grid[i][j], count);
}
count = 0;
for (int i = N - 1; i >= 0; --i) {
count = (grid[i][j] == 0) ? 0 : count + 1;
grid[i][j] = min(grid[i][j], count);
}
}
int ans = 0;
for (auto& row : grid)
for (int v : row)
ans = max(ans, v);
return ans;
}
};
class Solution {
public int orderOfLargestPlusSign(int N, int[][] mines) {
int[][] grid = new int[N][N];
for (int[] row : grid)
Arrays.fill(row, N);
for (int[] mine : mines)
grid[mine[0]][mine[1]] = 0;
for (int i = 0; i < N; ++i) {
int count = 0;
for (int j = 0; j < N; ++j) {
count = grid[i][j] == 0 ? 0 : count + 1;
grid[i][j] = Math.min(grid[i][j], count);
}
count = 0;
for (int j = N - 1; j >= 0; --j) {
count = grid[i][j] == 0 ? 0 : count + 1;
grid[i][j] = Math.min(grid[i][j], count);
}
}
for (int j = 0; j < N; ++j) {
int count = 0;
for (int i = 0; i < N; ++i) {
count = grid[i][j] == 0 ? 0 : count + 1;
grid[i][j] = Math.min(grid[i][j], count);
}
count = 0;
for (int i = N - 1; i >= 0; --i) {
count = grid[i][j] == 0 ? 0 : count + 1;
grid[i][j] = Math.min(grid[i][j], count);
}
}
int ans = 0;
for (int[] row : grid)
for (int v : row)
ans = Math.max(ans, v);
return ans;
}
}
var orderOfLargestPlusSign = function(N, mines) {
let grid = Array.from({length: N}, () => Array(N).fill(N));
for (let [x, y] of mines) {
grid[x][y] = 0;
}
for (let i = 0; i < N; ++i) {
let count = 0;
for (let j = 0; j < N; ++j) {
count = grid[i][j] == 0 ? 0 : count + 1;
grid[i][j] = Math.min(grid[i][j], count);
}
count = 0;
for (let j = N - 1; j >= 0; --j) {
count = grid[i][j] == 0 ? 0 : count + 1;
grid[i][j] = Math.min(grid[i][j], count);
}
}
for (let j = 0; j < N; ++j) {
let count = 0;
for (let i = 0; i < N; ++i) {
count = grid[i][j] == 0 ? 0 : count + 1;
grid[i][j] = Math.min(grid[i][j], count);
}
count = 0;
for (let i = N - 1; i >= 0; --i) {
count = grid[i][j] == 0 ? 0 : count + 1;
grid[i][j] = Math.min(grid[i][j], count);
}
}
let ans = 0;
for (let row of grid)
for (let v of row)
ans = Math.max(ans, v);
return ans;
};