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.

Description Hints 1 Solution Video 12:10

764. Largest Plus Sign

Medium49.7% acceptance2 companies

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.

Asked at 2 companies

Twitter Meta

Topics

Array Dynamic Programming

Hints open one at a time

Hint 1

For each direction such as "left", find left[r][c] = the number of 1s you will see before a zero starting at r, c and walking left. You can find this in N^2 time with a dp. The largest plus sign at r, c is just the minimum of left[r][c], up[r][c] etc.

12:10

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution