Largest Plus Sign — Medium Problem & Solution

Start with an n × n grid of 1s, then set every cell listed in mines to 0.

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 <= 500
1 <= mines.length <= 5000
0 <= mines[i][0], mines[i][1] < n
All the pairs in mines are unique.

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 × n grid and start dp at n everywhere.
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 1 has order 1.
All four directions must be swept; three is not enough.
Initialising dp to n matters — 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)

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue