Largest Plus Sign

Med

#0718Time: 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).1 company

Patterns

Dynamic Programming

Data structures

Array

Companies

Intuit

Prompt

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 i^th element of the array mines is defined as mines[i] = [x_i, y_i] where grid[x_i][y_i] == 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 <= 500
1 <= mines.length <= 5000
0 <= x_i, y_i < n
All the pairs (x_i, y_i) are unique.

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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

1java\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

Complexity

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).

Trade-offs

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).

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.

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.

Walkthrough

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

1java\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

Complexity

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).

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int orderOfLargestPlusSign(int n, int[][] mines) {4    int[][] dp = new int[n][n];5    for (var e : dp) {6      Arrays.fill(e, n);7    }8    for (var e : mines) {9      dp[e[0]][e[1]] = 0;10    }11    for (int i = 0; i < n; ++i) {12      int left = 0, right = 0, up = 0, down = 0;13      for (int j = 0, k = n - 1; j < n; ++j, --k) {14        left = dp[i][j] > 0 ? left + 1 : 0;15        right = dp[i][k] > 0 ? right + 1 : 0;16        up = dp[j][i] > 0 ? up + 1 : 0;17        down = dp[k][i] > 0 ? down + 1 : 0;18        dp[i][j] = Math.min(dp[i][j], left);19        dp[i][k] = Math.min(dp[i][k], right);20        dp[j][i] = Math.min(dp[j][i], up);21        dp[k][i] = Math.min(dp[k][i], down);22      }23    }24    return Arrays.stream(dp).flatMapToInt(Arrays : : stream).max().getAsInt();25  }26}

1class Solution {2public:3  int orderOfLargestPlusSign(int n, vector<vector<int>> &mines) {4    vector<vector<int>> dp(n, vector<int>(n, n));5    for (auto &e : mines)6      dp[e[0]][e[1]] = 0;7    for (int i = 0; i < n; ++i) {8      int left = 0, right = 0, up = 0, down = 0;9      for (int j = 0, k = n - 1; j < n; ++j, --k) {10        left = dp[i][j] ? left + 1 : 0;11        right = dp[i][k] ? right + 1 : 0;12        up = dp[j][i] ? up + 1 : 0;13        down = dp[k][i] ? down + 1 : 0;14        dp[i][j] = min(dp[i][j], left);15        dp[i][k] = min(dp[i][k], right);16        dp[j][i] = min(dp[j][i], up);17        dp[k][i] = min(dp[k][i], down);18      }19    }20    int ans = 0;21    for (auto &e : dp)22      ans = max(ans, *max_element(e.begin(), e.end()));23    return ans;24  }25};

1class Solution:2    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)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem