# Largest Plus Sign
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/largest-plus-sign)
Canonical: https://scaleengineer.com/dsa/problems/largest-plus-sign
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [Intuit](https://scaleengineer.com/companies/intuit)
---
## 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:**

![](https://assets.glich.co/dsa/largest-plus-sign/image0.jpg) 

**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:**

![](https://assets.glich.co/dsa/largest-plus-sign/image1.jpg) 

**Input:** n = 1, mines = [[0,0]]
**Output:** 0
**Explanation:** There is no plus sign, so return 0.

**Constraints:**

* `1 <= n <= 500`
* `1 <= mines.length <= 5000`
* `0 <= xi, yi < n`
* All the pairs `(xi, yi)` are **unique**.

# Approaches
## Brute Force Iteration
The most straightforward approach is to treat every possible cell in the grid as a potential center for a plus sign. For each cell, we attempt to expand a plus sign outwards from it, checking how far the arms can extend before hitting a boundary or a mine.
**Time:** O(N^3), where N is the dimension of the grid. We iterate through N*N cells. For each cell, we expand outwards, which can take up to O(N) steps in the worst case. · **Space:** O(M), where M is the number of mines. This space is used to store the set of banned cells for efficient lookup. If we were to build the full grid, it would be O(N^2).
**Pros:** Conceptually simple and straightforward to implement.
**Cons:** Highly inefficient with a cubic time complexity.; Likely to result in a 'Time Limit Exceeded' error for the given constraints (`n` up to 500).
### Explanation
First, we need an efficient way to check if a cell is a mine. We can add all mine coordinates to a `HashSet` for O(1) lookup, encoding each coordinate `(r, c)` as a single integer `r * n + c`.\n\nThe core of the algorithm involves iterating through every cell `(r, c)` of the grid and treating it as a potential center. For each center, we try to find the largest plus sign it can support. We start with a potential order `k=0` and expand outwards. A `while` loop checks if arms of length `k` are valid. This means the four arm-tip cells `(r-k, c)`, `(r+k, c)`, `(r, c-k)`, and `(r, c+k)` must all be within the grid boundaries and must not be mines. If they are valid, we increment `k` and check for the next larger size. The loop stops when the arms are no longer valid. The final value of `k` represents the order of the largest plus sign for that center. We keep track of the maximum `k` found across all centers.\n\n```java\nimport java.util.HashSet;\nimport java.util.Set;\n\nclass Solution {\n    public int largestPlusSign(int n, int[][] mines) {\n        Set<Integer> banned = new HashSet<>();\n        for (int[] mine : mines) {\n            banned.add(mine[0] * n + mine[1]);\n        }\n\n        int maxOrder = 0;\n        for (int r = 0; r < n; r++) {\n            for (int c = 0; c < n; c++) {\n                int k = 0;\n                while (r - k >= 0 && r + k < n && c - k >= 0 && c + k < n &&\n                       !banned.contains((r - k) * n + c) &&\n                       !banned.contains((r + k) * n + c) &&\n                       !banned.contains(r * n + (c - k)) &&\n                       !banned.contains(r * n + (c + k))) {\n                    k++;\n                }\n                maxOrder = Math.max(maxOrder, k);\n            }\n        }\n        return maxOrder;\n    }\n}\n```
### Algorithm
- Create a `Set` of banned cells from the `mines` array for efficient `O(1)` lookups. The coordinates `(r, c)` can be encoded as `r * n + c`.\n- Initialize `maxOrder = 0` to store the size of the largest plus sign found.\n- Iterate through every cell `(r, c)` from `(0, 0)` to `(n-1, n-1)` to test it as a potential center.\n- For each cell `(r, c)`, find the maximum order `k` it can support. Initialize a potential order `k = 0`.\n- Use a `while` loop. The condition checks if arms of length `k` are valid (i.e., cells `(r-k, c)`, `(r+k, c)`, etc. are within bounds and not on a mine).\n- If they are valid, it means a plus of order `k+1` is possible. So we increment `k` and check the next level.\n- The loop terminates when arms of length `k` are invalid. The largest valid order for this center was the final value of `k`.\n- Update `maxOrder = max(maxOrder, k)`.\n- After checking all cells, return `maxOrder`.

## Dynamic Programming
This approach improves upon the brute-force method by avoiding redundant calculations. Instead of repeatedly checking the arm lengths for each potential center, we precompute the number of consecutive 1s extending from every cell in four directions: up, down, left, and right. The order of a plus sign centered at any cell `(r, c)` is then simply the minimum of these four precomputed lengths.
**Time:** O(N^2), where N is the dimension of the grid. We perform four passes over the grid, each taking O(N^2) time. Building the set of mines takes O(M), where M is the number of mines. The total time is dominated by the grid passes. · **Space:** O(N^2 + M). O(N^2) for the DP grid and O(M) for the set of banned cells. Since M can be up to N^2, this simplifies to O(N^2).
**Pros:** Highly efficient with a quadratic time complexity, making it suitable for the given constraints.; Represents the optimal time complexity for this problem.
**Cons:** Requires O(N^2) extra space for the DP grid, which can be significant for very large N.
### Explanation
We use an `n x n` DP grid, let's call it `dp`, where `dp[r][c]` will ultimately store the order of the largest plus sign that can be centered at `(r, c)`. The algorithm makes four passes over the grid to compute arm lengths from each of the four cardinal directions.\n\nFirst, we create a `HashSet` of banned cells for efficient lookups.\n\n1.  **Left Pass:** For each row, iterate from left to right. We maintain a running count of consecutive non-banned cells. `dp[r][c]` is set to this count, representing the length of the arm extending to the left (including the center).\n2.  **Right Pass:** For each row, iterate from right to left, again keeping a count. We update `dp[r][c]` to be the minimum of its current value (from the left pass) and this new count from the right.\n3.  **Up Pass:** For each column, iterate from top to bottom. We calculate the count of consecutive non-banned cells from above and update `dp[r][c]` with the minimum of its current value and this new 'up' count.\n4.  **Down Pass:** For each column, iterate from bottom to top. We calculate the 'down' count and update `dp[r][c]` one last time. At this point, `dp[r][c]` contains `min(left_arm, right_arm, up_arm, down_arm)`, which is the order of the plus sign centered at `(r, c)`.\n\nFinally, we find the maximum value in the `dp` grid, which gives the answer. This can be combined with the final pass to save an extra iteration.\n\n```java\nimport java.util.HashSet;\nimport java.util.Set;\n\nclass Solution {\n    public int largestPlusSign(int n, int[][] mines) {\n        Set<Integer> banned = new HashSet<>();\n        for (int[] mine : mines) {\n            banned.add(mine[0] * n + mine[1]);\n        }\n\n        int[][] dp = new int[n][n];\n        \n        // Pass 1: Left-to-Right\n        for (int r = 0; r < n; r++) {\n            int count = 0;\n            for (int c = 0; c < n; c++) {\n                count = banned.contains(r * n + c) ? 0 : count + 1;\n                dp[r][c] = count;\n            }\n        }\n\n        // Pass 2: Right-to-Left\n        for (int r = 0; r < n; r++) {\n            int count = 0;\n            for (int c = n - 1; c >= 0; c--) {\n                count = banned.contains(r * n + c) ? 0 : count + 1;\n                dp[r][c] = Math.min(dp[r][c], count);\n            }\n        }\n\n        // Pass 3: Top-to-Bottom\n        for (int c = 0; c < n; c++) {\n            int count = 0;\n            for (int r = 0; r < n; r++) {\n                count = banned.contains(r * n + c) ? 0 : count + 1;\n                dp[r][c] = Math.min(dp[r][c], count);\n            }\n        }\n\n        // Pass 4: Bottom-to-Top and find max\n        int maxOrder = 0;\n        for (int c = 0; c < n; c++) {\n            int count = 0;\n            for (int r = n - 1; r >= 0; r--) {\n                count = banned.contains(r * n + c) ? 0 : count + 1;\n                dp[r][c] = Math.min(dp[r][c], count);\n                maxOrder = Math.max(maxOrder, dp[r][c]);\n            }\n        }\n\n        return maxOrder;\n    }\n}\n```
### Algorithm
- Create a `Set` of banned cells from the `mines` array for `O(1)` lookups.\n- Create an `n x n` integer grid `dp`.\n- **Pass 1 (Left):** For each row `r`, iterate `c` from left to right. Maintain a `count` of consecutive non-banned cells. Set `dp[r][c] = count`.\n- **Pass 2 (Right):** For each row `r`, iterate `c` from right to left. Maintain a `count`. Update `dp[r][c] = min(dp[r][c], count)`.\n- **Pass 3 (Up):** For each column `c`, iterate `r` from top to bottom. Maintain a `count`. Update `dp[r][c] = min(dp[r][c], count)`.\n- **Pass 4 (Down):** For each column `c`, iterate `r` from bottom to top. Maintain a `count`. Update `dp[r][c] = min(dp[r][c], count)`.\n- During the final pass (or in a separate fifth pass), find the maximum value in the `dp` grid. This value is the result.

# Solutions
### Java

```java
class Solution {
public
  int orderOfLargestPlusSign(int n, int[][] mines) {
    int[][] dp = new int[n][n];
    for (var e : dp) {
      Arrays.fill(e, n);
    }
    for (var e : mines) {
      dp[e[0]][e[1]] = 0;
    }
    for (int i = 0; i < n; ++i) {
      int left = 0, right = 0, up = 0, down = 0;
      for (int j = 0, k = n - 1; j < n; ++j, --k) {
        left = dp[i][j] > 0 ? left + 1 : 0;
        right = dp[i][k] > 0 ? right + 1 : 0;
        up = dp[j][i] > 0 ? up + 1 : 0;
        down = dp[k][i] > 0 ? down + 1 : 0;
        dp[i][j] = Math.min(dp[i][j], left);
        dp[i][k] = Math.min(dp[i][k], right);
        dp[j][i] = Math.min(dp[j][i], up);
        dp[k][i] = Math.min(dp[k][i], down);
      }
    }
    return Arrays.stream(dp).flatMapToInt(Arrays : : stream).max().getAsInt();
  }
}

```

### CPP

```cpp
class Solution {
public:
  int orderOfLargestPlusSign(int n, vector<vector<int>> &mines) {
    vector<vector<int>> dp(n, vector<int>(n, n));
    for (auto &e : mines)
      dp[e[0]][e[1]] = 0;
    for (int i = 0; i < n; ++i) {
      int left = 0, right = 0, up = 0, down = 0;
      for (int j = 0, k = n - 1; j < n; ++j, --k) {
        left = dp[i][j] ? left + 1 : 0;
        right = dp[i][k] ? right + 1 : 0;
        up = dp[j][i] ? up + 1 : 0;
        down = dp[k][i] ? down + 1 : 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);
      }
    }
    int ans = 0;
    for (auto &e : dp)
      ans = max(ans, *max_element(e.begin(), e.end()));
    return ans;
  }
};

```

### Python

```python
class Solution:
    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int: dp = [[n] * n for _ in range(n)] for x, y in mines: dp[x][y] = 0 for i in range(n): left = right = up = down = 0 for j, k in zip(range(n), reversed(range(n))): left = left + 1 if dp[i][j] else 0 right = right + 1 if dp[i][k] else 0 up = up + 1 if dp[j][i] else 0 down = down + 1 if dp[k][i] else 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) return max(max(v) for v in dp)

```