You are given an integer n. You have an n x n binary grid grid with all values initially 1's except for some indices given in the array mines. The ith element of the array mines is defined as mines[i] = [xi, yi] where grid[xi][yi] == 0.
Return the order of the largest axis-aligned plus sign of 1's contained in grid. If there is none, return 0.
An axis-aligned plus sign of 1's of order k has some center grid[r][c] == 1 along with four arms of length k - 1 going up, down, left, and right, and made of 1's. Note that there could be 0's or 1's beyond the arms of the plus sign, only the relevant area of the plus sign is checked for 1's.
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 <= 5001 <= mines.length <= 50000 <= xi, yi < n(xi, yi) are unique.Problem Overview: You are given an n x n grid where some cells contain mines. A plus sign consists of a center cell and four arms (up, down, left, right) of equal length made only of 1s. The goal is to return the order of the largest possible plus sign that can exist in the grid.
Approach 1: Greedy Scanning with Set Usage (O(n^3) time, O(m) space)
The straightforward solution checks every cell as a potential center of a plus sign. Store all mine positions inside a set for constant-time lookup. For each cell that is not a mine, expand outward in four directions while ensuring you don't hit a mine or the grid boundary. The smallest arm length across the four directions determines the order of the plus sign centered at that cell. This approach is simple to reason about but inefficient because every expansion can scan up to O(n) cells for each of the n^2 grid positions.
Approach 2: Dynamic Programming Directional Scan (O(n^2) time, O(n^2) space)
The optimized solution uses Dynamic Programming to precompute the number of consecutive non-mine cells in all four directions for every position. Start with a grid initialized to n, then mark mine positions as 0. Perform four directional scans: left-to-right, right-to-left, top-to-bottom, and bottom-to-top. During each scan, track the running streak of valid cells and update the current cell with the minimum value seen so far. The final value at each cell represents the maximum order of a plus sign centered there. The answer is the maximum value across the grid.
This technique works because a valid plus sign requires equal-length arms in all four directions. Taking the minimum of the directional counts guarantees the limiting arm length is respected. The algorithm touches each cell a constant number of times, which reduces the complexity from cubic to quadratic.
The grid manipulation relies heavily on sequential passes over a matrix, which is common in problems involving arrays and directional preprocessing.
Recommended for interviews: The dynamic programming directional scan is the expected solution. The greedy expansion approach demonstrates understanding of the problem but scales poorly. Interviewers typically look for the DP insight that precomputes directional streaks and combines them with a min operation to evaluate each center in constant time.
This approach involves using dynamic programming to store the maximum possible length of arms of a plus sign centered at each cell, checking in all four directions (left, right, up, down).
We initialize four matrices (left, right, up, down) that store the length of ones segment that ends at each cell in the corresponding direction. We update these matrices while iterating through the grid.
By iterating over the grid, first from top-left to bottom-right, and then from bottom-right to top-left, we can fill these matrices. The maximum order of the plus sign centered at any cell is the minimum value among the four directions at that cell.
The implementation starts by initializing a grid and converting the mines positions to zero. Four matrices (left, right, up, down) store the consecutive 1 segments up to that point from each direction respectively.
We iterate through the grid twice. The first pass, filling left and up, goes top-to-bottom and left-to-right; the second, filling right and down, goes bottom-to-top and right-to-left. Finally, we calculate the minimum of the maximum possible lengths at each point to determine the largest possible plus sign.
Time Complexity: O(n^2) since each cell is visited and calculated twice.
Space Complexity: O(n^2) due to the four direction matrices.
This approach uses a greedy algorithm with the aid of hash sets to track each encountered zero from the mines. By using sets, we quickly check if any particular cell disrupts a potential plus sign, and can avoid unnecessary calculations.
For every arm of each potential plus sign in the grid, checks are performed to determine continuation down an arm or reset due to zeroes from mines.
This C program uses a 2D boolean array to track where mines are located, to avoid recalculating grid states unnecessarily. It also checks for maximum arm lengths from prior initializations to limit the search scope while calculating potential plus signs.
Time Complexity: O(n^2) due to the requirement to scan both axes when looking for maximum stretches of ones.
Space Complexity: O(n^2) as the boolean grid requires space for each cell to track presence of mine locations.
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: Space Complexity: |
| Greedy Scanning with Set Usage | Time Complexity: Space Complexity: |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Expansion with Mine Set | O(n^3) | O(m) | Simple baseline approach or when grid size is small |
| Dynamic Programming Directional Scan | O(n^2) | O(n^2) | Optimal solution for large grids and expected interview approach |
Largest Plus Sign | Leetcode 764 | Live coding session 🔥🔥🔥 • Coding Decoded • 3,644 views views
Watch 9 more video solutions →Practice Largest Plus Sign with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor