Largest Plus Sign

Hard
0/120
0 upvote
Asked in company
Uber

Problem statement

You are given an integer n, which defines an n x n binary grid. Initially, all values in the grid are 1s. You are also given an array mines, where each element mines[i] = [row, col] indicates that the cell grid[row][col] should be a 0.


Your task is to find the order of the largest axis-aligned plus sign of 1s contained in the final grid. If no plus sign of 1s exists (i.e., the grid contains no 1s), you should return 0.


An axis-aligned plus sign of order k is defined by:

  A center cell grid[r][c] which must be 1.
  Four "arms" of 1s extending up, down, left, and right from the center.
  The length of each arm must be at least k-1.


This means the order k is determined by the shortest arm extending from the center. For a plus sign centered at (r, c), the order is 1 + min(up, down, left, right), where up is the number of consecutive 1s above the center, down is the number below, and so on.


Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains a single integer n, the size of the grid.

The second line contains an integer m, the number of mines.

The next m lines each contain two space-separated integers, r and c, representing the coordinates of a mine.


Output Format: 
Your function should return a single integer representing the order of the largest plus sign.


Note: 
A brute-force approach that checks every cell as a potential center and expands outwards would be O(n^3), which is too slow. A more efficient O(n^2) dynamic programming approach is required.
Sample Input 1:
5
1
4 2


Sample Output 1:
2


Explanation for Sample 1:
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 0 1 1

The largest plus sign is centered at (3,1) or (2,2) etc., but the one with the largest order can be centered at (3,1). From (3,1), you can go up 3 steps, down 1, left 1, right 3. The shortest arm length is 1, so the order is 1+1=2.


Sample Input 2:
1
1
0 0


Sample Output 2:
0


Explanation for Sample 2:
The 1x1 grid contains a single 0. There are no 1s, so no plus sign can be formed.


Expected Time Complexity:
The expected time complexity is O(N^2).


Constraints:
1 <= n <= 500
1 <= mines.length <= 5000
0 <= r, c < n
All mine coordinates are unique.

Time limit: 1 sec
Approaches (1)
Time Complexity
Space Complexity
Code Solution
(100% EXP penalty)
Largest Plus Sign
Full screen
Console