Largest Plus Sign solution and explanation
9 more videos on this problem
Largest Plus Sign | Leetcode 764 | Live coding session 🔥🔥🔥Coding Decoded · 12:10 · 3K views
Largest Plus Sign | LeetCode 764 | Matrix | UberNaresh Gupta · 9:09 · 3K views
LeetCode 764. Largest Plus SignHappy Coding · 14:07 · 1K views
Largest Plus Sign | Array | Dynamic Programming | 764 LeetCode | Day 09CodeWithSunny · 20:47 · 1K views
Leetcode 764 - Largest plus sign - Thought processZero 2 Quant · 33:38 · 1K views
Largest Plus Sign | A Detailed Explanation of the SolutionTanishq Chaudhary · 20:08 · 1K views
Leetcode - Largest Plus Sign (Python)Timothy H Chang · 9:03 · 911 views
764. Largest Plus Sign (Leetcode Medium)Programming Live with Larry · 27:51 · 904 views
Daily Leetcode #527: Sep 09, 2021 - 764. Largest Plus SignProgramming Live with Larry · 29:43 · 517 views
Problem Analysis 764 leetcode.com Largest Plus Sign. C++ Solution3.5 задачи в неделю · 43:20 · 480 views
The problem
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- All the pairs
(xi, yi)are unique.
Approach overview
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.
Approach 1: Dynamic Programming Approach
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.
def orderOfLargestPlusSign(n, mines):
grid = [[n] * n for _ in range(n)]
for mine in mines:
grid[mine[0]][mine[1]] = 0
for r in range(n):
count = 0
for c in range(n): # left
count = 0 if grid[r][c] == 0 else count + 1
grid[r][c] = min(grid[r][c], count)
count = 0
for c in range(n - 1, -1, -1): # right
count = 0 if grid[r][c] == 0 else count + 1
grid[r][c] = min(grid[r][c], count)
for c in range(n):
count = 0
for r in range(n): # up
count = 0 if grid[r][c] == 0 else count + 1
grid[r][c] = min(grid[r][c], count)
count = 0
for r in range(n - 1, -1, -1): # down
count = 0 if grid[r][c] == 0 else count + 1
grid[r][c] = min(grid[r][c], count)
return max(max(row) for row in grid) - 1
# Example usage:
mines = [[4, 2]]
print(orderOfLargestPlusSign(5, mines)) # Output: 2import java.util.Arrays;
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 r = 0; r < n; r++) {
for (int c = 0, l = 0; c < n; c++) { // left
l = (grid[r][c] == 0) ? 0 : l + 1;
grid[r][c] = Math.min(grid[r][c], l);
}
for (int c = n - 1, r = 0; c >= 0; c--) { // right
r = (grid[r][c] == 0) ? 0 : r + 1;
grid[r][c] = Math.min(grid[r][c], r);
}
}
for (int c = 0; c < n; c++) {
for (int r = 0, u = 0; r < n; r++) { // up
u = (grid[r][c] == 0) ? 0 : u + 1;
grid[r][c] = Math.min(grid[r][c], u);
}
for (int r = n - 1, d = 0; r >= 0; r--) { // down
d = (grid[r][c] == 0) ? 0 : d + 1;
grid[r][c] = Math.min(grid[r][c], d);
}
}
int maxOrder = 0;
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
maxOrder = Math.max(maxOrder, grid[r][c]);
}
}
return maxOrder - 1;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[][] mines = {{4, 2}};
int result = sol.orderOfLargestPlusSign(5, mines);
System.out.println(result); // Output: 2
}
}#include <vector>
#include <algorithm>
using namespace std;
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 r = 0; r < n; ++r) {
for (int c = 0, l = 0; c < n; ++c) { // left
l = (grid[r][c] == 0) ? 0 : l + 1;
grid[r][c] = min(grid[r][c], l);
}
for (int c = n - 1, r = 0; c >= 0; --c) { // right
r = (grid[r][c] == 0) ? 0 : r + 1;
grid[r][c] = min(grid[r][c], r);
}
}
for (int c = 0; c < n; ++c) {
for (int r = 0, u = 0; r < n; ++r) { // up
u = (grid[r][c] == 0) ? 0 : u + 1;
grid[r][c] = min(grid[r][c], u);
}
for (int r = n - 1, d = 0; r >= 0; --r) { // down
d = (grid[r][c] == 0) ? 0 : d + 1;
grid[r][c] = min(grid[r][c], d);
}
}
int maxOrder = 0;
for (int r = 0; r < n; ++r) {
for (int c = 0; c < n; ++c) {
maxOrder = max(maxOrder, grid[r][c]);
}
}
return maxOrder - 1;
}
int main() {
// Example usage:
int n = 5;
vector<vector<int>> mines = {{4, 2}};
int result = orderOfLargestPlusSign(n, mines);
cout << result << endl; // Output: 2
return 0;
}function orderOfLargestPlusSign(n, mines) {
const grid = Array.from({length: n}, () => Array(n).fill(n));
for (const [x, y] of mines) {
grid[x][y] = 0;
}
for (let r = 0; r < n; r++) {
for (let c = 0, l = 0; c < n; c++) { // left
l = grid[r][c] === 0 ? 0 : l + 1;
grid[r][c] = Math.min(grid[r][c], l);
}
for (let c = n - 1, r = 0; c >= 0; c--) { // right
r = grid[r][c] === 0 ? 0 : r + 1;
grid[r][c] = Math.min(grid[r][c], r);
}
}
for (let c = 0; c < n; c++) {
for (let r = 0, u = 0; r < n; r++) { // up
u = grid[r][c] === 0 ? 0 : u + 1;
grid[r][c] = Math.min(grid[r][c], u);
}
for (let r = n - 1, d = 0; r >= 0; r--) { // down
d = grid[r][c] === 0 ? 0 : d + 1;
grid[r][c] = Math.min(grid[r][c], d);
}
}
return Math.max(...grid.flat()) - 1;
}
// Example usage:
console.log(orderOfLargestPlusSign(5, [[4, 2]])); // Output: 2#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int orderOfLargestPlusSign(int n, int** mines, int minesSize, int* minesColSize) {
int grid[n][n];
memset(grid, 1, sizeof(grid));
for (int i = 0; i < minesSize; i++) {
grid[mines[i][0]][mines[i][1]] = 0;
}
int left[n][n], right[n][n], up[n][n], down[n][n];
memset(left, 0, sizeof(left));
memset(right, 0, sizeof(right));
memset(up, 0, sizeof(up));
memset(down, 0, sizeof(down));
// Fill left and up
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j]) {
left[i][j] = (j == 0 ? 0 : left[i][j-1]) + 1;
up[i][j] = (i == 0 ? 0 : up[i-1][j]) + 1;
}
}
}
// Fill right and down
for (int i = n - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
if (grid[i][j]) {
right[i][j] = (j == n - 1 ? 0 : right[i][j+1]) + 1;
down[i][j] = (i == n - 1 ? 0 : down[i+1][j]) + 1;
}
}
}
// Find the order of the largest plus sign
int maxOrder = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j]) {
int order = left[i][j];
if (up[i][j] < order)
order = up[i][j];
if (right[i][j] < order)
order = right[i][j];
if (down[i][j] < order)
order = down[i][j];
if (order > maxOrder)
maxOrder = order;
}
}
}
return maxOrder;
}
int main() {
// Example usage:
int n = 5;
int *mines[1];
int mine1[] = {4, 2};
mines[0] = mine1;
int result = orderOfLargestPlusSign(n, mines, 1, NULL);
printf("%d\n", result); // Output: 2
return 0;
}using System;
using System.Linq;
class Solution {
public int OrderOfLargestPlusSign(int n, int[][] mines) {
int[][] grid = new int[n][];
for (int i = 0; i < n; i++) {
grid[i] = Enumerable.Repeat(n, n).ToArray();
}
foreach (var mine in mines) {
grid[mine[0]][mine[1]] = 0;
}
for (int r = 0; r < n; r++) {
for (int c = 0, l = 0; c < n; c++) { // left
l = grid[r][c] == 0 ? 0 : l + 1;
grid[r][c] = Math.Min(grid[r][c], l);
}
for (int c = n - 1, r = 0; c >= 0; c--) { // right
r = grid[r][c] == 0 ? 0 : r + 1;
grid[r][c] = Math.Min(grid[r][c], r);
}
}
for (int c = 0; c < n; c++) {
for (int r = 0, u = 0; r < n; r++) { // up
u = grid[r][c] == 0 ? 0 : u + 1;
grid[r][c] = Math.Min(grid[r][c], u);
}
for (int r = n - 1, d = 0; r >= 0; r--) { // down
d = grid[r][c] == 0 ? 0 : d + 1;
grid[r][c] = Math.Min(grid[r][c], d);
}
}
int maxOrder = 0;
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
maxOrder = Math.Max(maxOrder, grid[r][c]);
}
}
return maxOrder - 1;
}
static void Main(string[] args) {
Solution sol = new Solution();
int[][] mines = { new int[]{ 4, 2 } };
Console.WriteLine(sol.OrderOfLargestPlusSign(5, mines)); // Output: 2
}
}In this Python solution, the grid is updated with the minimum consecutive 1s from the current direction iteratively during the multiple passes over the grid. The grid acts both as a tracker for zeros (from mines) and for potential plus sign orders at each cell.
Time Complexity: O(n^2) from the multiple directional passes.
Space Complexity: O(n^2) as the grid is used for calculations but incurs no additional overhead.
Approach 2: Greedy Scanning with Set Usage
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.
def orderOfLargestPlusSign(n, mines):
zeroSet = set(tuple(mine) for mine in mines)
grid = [[n] * n for _ in range(n)]
maxOrder = 0
for r in range(n):
count = 0
for c in range(n): # left
count = count + 1 if (r, c) not in zeroSet else 0
grid[r][c] = count
count = 0
for c in range(n - 1, -1, -1): # right
count = count + 1 if (r, c) not in zeroSet else 0
grid[r][c] = min(grid[r][c], count)
for c in range(n):
count = 0
for r in range(n): # up
count = count + 1 if (r, c) not in zeroSet else 0
grid[r][c] = min(grid[r][c], count)
count = 0
for r in range(n - 1, -1, -1): # down
count = count + 1 if (r, c) not in zeroSet else 0
grid[r][c] = min(grid[r][c], count)
maxOrder = max(maxOrder, grid[r][c])
return maxOrder
# Example usage:
mines = [[4, 2]]
print(orderOfLargestPlusSign(5, mines)) # Output: 2import java.util.HashSet;
class Solution {
public int orderOfLargestPlusSign(int n, int[][] mines) {
HashSet<String> zeroSet = new HashSet<>();
for (int[] mine : mines) {
zeroSet.add(mine[0] + "," + mine[1]);
}
int[][] grid = new int[n][n];
int maxOrder = 0;
for (int r = 0; r < n; r++) {
int count = 0;
for (int c = 0; c < n; c++) { // left
count = zeroSet.contains(r + "," + c) ? 0 : count + 1;
grid[r][c] = count;
}
count = 0;
for (int c = n - 1; c >= 0; c--) { // right
count = zeroSet.contains(r + "," + c) ? 0 : count + 1;
grid[r][c] = Math.min(grid[r][c], count);
}
}
for (int c = 0; c < n; c++) {
int count = 0;
for (int r = 0; r < n; r++) { // up
count = zeroSet.contains(r + "," + c) ? 0 : count + 1;
grid[r][c] = Math.min(grid[r][c], count);
}
count = 0;
for (int r = n - 1; r >= 0; r--) { // down
count = zeroSet.contains(r + "," + c) ? 0 : count + 1;
grid[r][c] = Math.min(grid[r][c], count);
maxOrder = Math.max(maxOrder, grid[r][c]);
}
}
return maxOrder;
}
public static void main(String[] args) {
Solution s = new Solution();
int[][] mines = {{4, 2}};
System.out.println(s.orderOfLargestPlusSign(5, mines)); // Output: 2
}
}#include <vector>
#include <unordered_set>
using namespace std;
int orderOfLargestPlusSign(int n, vector<vector<int>>& mines) {
unordered_set<int> zeroSet;
for (auto& mine : mines) {
zeroSet.insert(mine[0] * n + mine[1]);
}
vector<vector<int>> grid(n, vector<int>(n, n));
for (int r = 0; r < n; ++r) {
int count = 0;
for (int c = 0; c < n; ++c) { // left
grid[r][c] = (zeroSet.count(r * n + c) ? count = 0 : grid[r][c] = ++count);
}
count = 0;
for (int c = n - 1; c >= 0; --c) { // right
grid[r][c] = min(grid[r][c], zeroSet.count(r * n + c) ? count = 0 : ++count);
}
}
int maxOrder = 0;
for (int c = 0; c < n; ++c) {
int count = 0;
for (int r = 0; r < n; ++r) { // up
grid[r][c] = min(grid[r][c], zeroSet.count(r * n + c) ? count = 0 : ++count);
}
count = 0;
for (int r = n - 1; r >= 0; --r) { // down
grid[r][c] = min(grid[r][c], zeroSet.count(r * n + c) ? count = 0 : ++count);
maxOrder = max(maxOrder, grid[r][c]);
}
}
return maxOrder;
}
int main() {
vector<vector<int>> mines = {{4,2}};
int result = orderOfLargestPlusSign(5, mines);
cout << result << endl; // Output: 2
return 0;
}function orderOfLargestPlusSign(n, mines) {
const zeroSet = new Set(mines.map(mine => mine[0] + ',' + mine[1]));
const grid = Array.from({ length: n }, () => Array(n).fill(n));
for (let r = 0; r < n; r++) {
let count = 0;
for (let c = 0; c < n; c++) { // left
count = zeroSet.has(`${r},${c}`) ? 0 : count + 1;
grid[r][c] = count;
}
count = 0;
for (let c = n-1; c >= 0; c--) { // right
count = zeroSet.has(`${r},${c}`) ? 0 : count + 1;
grid[r][c] = Math.min(grid[r][c], count);
}
}
let maxOrder = 0;
for (let c = 0; c < n; c++) {
let count = 0;
for (let r = 0; r < n; r++) { // up
count = zeroSet.has(`${r},${c}`) ? 0 : count + 1;
grid[r][c] = Math.min(grid[r][c], count);
}
count = 0;
for (let r = n-1; r >= 0; r--) { // down
count = zeroSet.has(`${r},${c}`) ? 0 : count + 1;
grid[r][c] = Math.min(grid[r][c], count);
maxOrder = Math.max(maxOrder, grid[r][c]);
}
}
return maxOrder;
}
// Example usage:
console.log(orderOfLargestPlusSign(5, [[4, 2]])); // Output: 2#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
bool **createBoolGrid(int size) {
bool **grid = (bool **)malloc(sizeof(bool *) * size);
for (int i = 0; i < size; i++) {
grid[i] = (bool *)calloc(size, sizeof(bool));
}
return grid;
}
void freeBoolGrid(bool **grid, int size) {
for (int i = 0; i < size; i++) {
free(grid[i]);
}
free(grid);
}
int orderOfLargestPlusSign(int n, int** mines, int minesSize, int* minesColSize) {
bool **zeros = createBoolGrid(n);
for (int i = 0; i < minesSize; i++) {
zeros[mines[i][0]][mines[i][1]] = true;
}
int maxOrder = 0;
for (int r = 0; r < n; r++) {
int count = 0;
for (int c = 0; c < n; c++) { // left
count = zeros[r][c] ? 0 : count + 1;
if (count > maxOrder/2) maxOrder = 2 * count;
}
}
for (int c = 0; c < n; c++) {
int count = 0;
for (int r = 0; r < n; r++) { // up
count = zeros[r][c] ? 0 : count + 1;
if (count > maxOrder/2) maxOrder = 2 * count;
}
}
freeBoolGrid(zeros, n);
return maxOrder / 2;
}
int main() {
int n = 5;
int *mines[1];
int mine1[] = {4, 2};
mines[0] = mine1;
int result = orderOfLargestPlusSign(n, mines, 1, NULL);
printf("%d\n", result); // Output: 2
return 0;
}using System;
using System.Collections.Generic;
class Solution {
public int OrderOfLargestPlusSign(int n, int[][] mines) {
HashSet<(int, int)> zeroSet = new HashSet<(int, int)>(mine => (mine[0], mine[1]));
int[][] grid = new int[n][];
for (int i = 0; i < n; i++) {
grid[i] = new int[n];
for (int j = 0; j < n; j++) {
grid[i][j] = n;
}
}
int maxOrder = 0;
for (int r = 0; r < n; r++) {
int count = 0;
for (int c = 0; c < n; c++) { // left
count = zeroSet.Contains((r, c)) ? 0 : count + 1;
grid[r][c] = count;
}
count = 0;
for (int c = n - 1; c >= 0; c--) { // right
count = zeroSet.Contains((r, c)) ? 0 : count + 1;
grid[r][c] = Math.Min(grid[r][c], count);
}
}
for (int c = 0; c < n; c++) {
int count = 0;
for (int r = 0; r < n; r++) { // up
count = zeroSet.Contains((r, c)) ? 0 : count + 1;
grid[r][c] = Math.Min(grid[r][c], count);
}
count = 0;
for (int r = n - 1; r >= 0; r--) { // down
count = zeroSet.Contains((r, c)) ? 0 : count + 1;
grid[r][c] = Math.Min(grid[r][c], count);
maxOrder = Math.Max(maxOrder, grid[r][c]);
}
}
return maxOrder;
}
static void Main() {
int[][] mines = new int[][] {new int[]{4, 2}};
Solution sol = new Solution();
Console.WriteLine(sol.OrderOfLargestPlusSign(5, mines)); // Output: 2
}
}Using Python's set, this solution tracks zero occurrences efficiently. The grid is quickly updated with each pass given the drastic speed boost from early exits, and iterative reset of count values upon the presence of zeroes from the hash set.
Time Complexity: O(n^2) based on grid traversal, complemented by fast membership checks within `set`.
Space Complexity: O(n^2) assigned to grid memory, reduced by efficient zero position tracking.
Approach 3: Default Approach
func orderOfLargestPlusSign(n int, mines [][]int) (ans int) {
dp := make([][]int, n)
for i := range dp {
dp[i] = make([]int, n)
for j := range dp[i] {
dp[i][j] = n
}
}
for _, e := range mines {
dp[e[0]][e[1]] = 0
}
for i := 0; i < n; i++ {
var left, right, up, down int
for j, k := 0, n-1; j < n; j, k = j+1, k-1 {
left, right, up, down = left+1, right+1, up+1, down+1
if dp[i][j] == 0 {
left = 0
}
if dp[i][k] == 0 {
right = 0
}
if dp[j][i] == 0 {
up = 0
}
if dp[k][i] == 0 {
down = 0
}
dp[i][j] = min(dp[i][j], left)
dp[i][k] = min(dp[i][k], right)
dp[j][i] = min(dp[j][i], up)
dp[k][i] = min(dp[k][i], down)
}
}
for _, e := range dp {
ans = max(ans, slices.Max(e))
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: Space Complexity: |
| Greedy Scanning with Set Usage | Time Complexity: Space Complexity: |
| Default Approach | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Largest Plus Sign easy or hard?
Largest Plus Sign is considered a medium difficulty problem on LeetCode. The brute force idea is easy to understand, but recognizing the directional dynamic programming optimization requires stronger problem-solving experience.
Largest Plus Sign Python/Java solution
Most implementations use the same dynamic programming idea across languages. Python, Java, C++, and JavaScript solutions all perform four directional scans over the grid while updating a DP matrix with minimum streak lengths.
How to solve Largest Plus Sign in O(n^2)?
Use directional dynamic programming. Initialize a grid and perform four scans: left-to-right, right-to-left, top-to-bottom, and bottom-to-top. Maintain running counts of consecutive non-mine cells and store the minimum count at each position. The maximum value in the grid after these scans is the largest plus sign order.
What is the best approach for Largest Plus Sign?
The best approach uses dynamic programming with four directional scans. For each cell, compute the number of consecutive non-mine cells in the left, right, up, and down directions. The minimum of these values determines the order of the plus sign centered at that cell. This reduces the complexity to O(n^2) time and O(n^2) space.
Is Largest Plus Sign asked at Google/Amazon/Meta?
Largest Plus Sign is a common medium-level matrix and dynamic programming problem similar to questions asked at companies like Amazon, Google, and Meta. It tests grid traversal, directional preprocessing, and optimization from brute force to dynamic programming.
What data structure is used in Largest Plus Sign?
The main solution uses a 2D array for dynamic programming to store directional streak counts. Many implementations also use a hash set to store mine coordinates for constant-time checks when building or initializing the grid.
What is the time complexity of Largest Plus Sign?
The optimal dynamic programming solution runs in O(n^2) time because each grid cell is processed during four directional passes. A simpler greedy expansion approach can take up to O(n^3) time since each cell may expand up to n steps in four directions.