Largest Plus Sign — Solution in Python, Java & C++
Largest Plus Sign solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Largest Plus Sign is a medium coding problem on arrays, dynamic programming and matrix, asked in Amazon, Google and Uber interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Matrix
- Asked at: Amazon, Google, Uber
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Start with an n × n grid of 1s, then set every cell listed in mines to 0.
A plus sign of order k centred at a cell consists of that cell plus k - 1 consecutive 1s going up, down, left and right from it — all inside the grid. Return the order of the largest plus sign of 1s, or 0 if none exists.
Example 1
Input: n = 5, mines = [[4,2]]
Output: 2
Explanation: A plus of order 2 fits; order 3 would need arms of length 2 that the mine blocks.
Example 2
Input: n = 1, mines = [[0,0]]
Output: 0
Explanation: The only cell is a mine.
Example 3
Input: n = 3, mines = [[0,0]]
Output: 2
Explanation: The centre cell has clear arms of length 1 in all four directions.
Constraints
1 <= n <= 5001 <= mines.length <= 50000 <= mines[i][0], mines[i][1] < nAll the pairs in mines are unique.
Hints for Largest Plus Sign
Hint 1
The order at a cell is the shortest of its four runs of consecutive
1s.Hint 2
Each of the four run lengths can be filled in with one linear sweep per row or column.
Hint 3
Take the minimum of the four at every cell, then the maximum over the grid.
How to solve Largest Plus Sign
For each cell compute how many consecutive 1s extend left, right, up and down, including the cell itself. The plus order centred there is the smallest of those four; the answer is the largest such value.
Approach
- Mark the mines in an
n × ngrid and startdpatneverywhere. - Sweep each row left-to-right and right-to-left, keeping a run length that resets to 0 at a mine, and take the minimum into
dp. - Do the same down and up each column.
- Return the maximum entry of
dp.
Why it works
The four sweeps are independent, and min is applied in place, so after all four dp[i][j] holds exactly the shortest arm. That is precisely the largest order centred there — an arm one longer would run into a mine or the border — and the maximum over all centres answers the question. Four O(n²) passes replace the O(n³) of measuring each arm on demand.
Complexity
- Time —
O(n²) - Space —
O(n²)
Pitfalls
- The run length includes the centre cell, so a lone
1has order 1. - All four directions must be swept; three is not enough.
- Initialising
dptonmatters — the minimum is taken, not the maximum.
Reference solution
Python
from typing import List
def orderOfLargestPlusSign(n: int, mines: List[List[int]]) -> int:
blocked = [[False] * n for _ in range(n)]
for r, c in mines:
blocked[r][c] = True
dp = [[n] * n for _ in range(n)]
for i in range(n):
cnt = 0
for j in range(n):
cnt = 0 if blocked[i][j] else cnt + 1
dp[i][j] = min(dp[i][j], cnt)
cnt = 0
for j in range(n - 1, -1, -1):
cnt = 0 if blocked[i][j] else cnt + 1
dp[i][j] = min(dp[i][j], cnt)
for j in range(n):
cnt = 0
for i in range(n):
cnt = 0 if blocked[i][j] else cnt + 1
dp[i][j] = min(dp[i][j], cnt)
cnt = 0
for i in range(n - 1, -1, -1):
cnt = 0 if blocked[i][j] else cnt + 1
dp[i][j] = min(dp[i][j], cnt)
return max(max(row) for row in dp)Java
public static int orderOfLargestPlusSign(int n, int[][] mines) {
boolean[][] blocked = new boolean[n][n];
int[][] dp = new int[n][n];
for (int[] row : dp) Arrays.fill(row, n);
for (int[] mine : mines) blocked[mine[0]][mine[1]] = true;
for (int i = 0; i < n; i++) {
int cnt = 0;
for (int j = 0; j < n; j++) {
cnt = blocked[i][j] ? 0 : cnt + 1;
dp[i][j] = Math.min(dp[i][j], cnt);
}
cnt = 0;
for (int j = n - 1; j >= 0; j--) {
cnt = blocked[i][j] ? 0 : cnt + 1;
dp[i][j] = Math.min(dp[i][j], cnt);
}
}
for (int j = 0; j < n; j++) {
int cnt = 0;
for (int i = 0; i < n; i++) {
cnt = blocked[i][j] ? 0 : cnt + 1;
dp[i][j] = Math.min(dp[i][j], cnt);
}
cnt = 0;
for (int i = n - 1; i >= 0; i--) {
cnt = blocked[i][j] ? 0 : cnt + 1;
dp[i][j] = Math.min(dp[i][j], cnt);
}
}
int best = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) best = Math.max(best, dp[i][j]);
}
return best;
}C++
int orderOfLargestPlusSign(int n, vector<vector<int>>& mines) {
vector<vector<char>> blocked(n, vector<char>(n, 0));
vector<vector<int>> dp(n, vector<int>(n, n));
for (auto& mine : mines) blocked[mine[0]][mine[1]] = 1;
for (int i = 0; i < n; i++) {
int cnt = 0;
for (int j = 0; j < n; j++) {
cnt = blocked[i][j] ? 0 : cnt + 1;
dp[i][j] = min(dp[i][j], cnt);
}
cnt = 0;
for (int j = n - 1; j >= 0; j--) {
cnt = blocked[i][j] ? 0 : cnt + 1;
dp[i][j] = min(dp[i][j], cnt);
}
}
for (int j = 0; j < n; j++) {
int cnt = 0;
for (int i = 0; i < n; i++) {
cnt = blocked[i][j] ? 0 : cnt + 1;
dp[i][j] = min(dp[i][j], cnt);
}
cnt = 0;
for (int i = n - 1; i >= 0; i--) {
cnt = blocked[i][j] ? 0 : cnt + 1;
dp[i][j] = min(dp[i][j], cnt);
}
}
int best = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) best = max(best, dp[i][j]);
}
return best;
}JavaScript
var orderOfLargestPlusSign = function(n, mines) {
var i, j, cnt;
var blocked = [], dp = [];
for (i = 0; i < n; i++) {
var b = [], d = [];
for (j = 0; j < n; j++) { b.push(false); d.push(n); }
blocked.push(b);
dp.push(d);
}
for (i = 0; i < mines.length; i++) blocked[mines[i][0]][mines[i][1]] = true;
for (i = 0; i < n; i++) {
cnt = 0;
for (j = 0; j < n; j++) {
cnt = blocked[i][j] ? 0 : cnt + 1;
if (cnt < dp[i][j]) dp[i][j] = cnt;
}
cnt = 0;
for (j = n - 1; j >= 0; j--) {
cnt = blocked[i][j] ? 0 : cnt + 1;
if (cnt < dp[i][j]) dp[i][j] = cnt;
}
}
for (j = 0; j < n; j++) {
cnt = 0;
for (i = 0; i < n; i++) {
cnt = blocked[i][j] ? 0 : cnt + 1;
if (cnt < dp[i][j]) dp[i][j] = cnt;
}
cnt = 0;
for (i = n - 1; i >= 0; i--) {
cnt = blocked[i][j] ? 0 : cnt + 1;
if (cnt < dp[i][j]) dp[i][j] = cnt;
}
}
var best = 0;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) if (dp[i][j] > best) best = dp[i][j];
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming