Largest Plus Sign

Medium
918.

Largest Plus Sign

Largest Plus Sign is a medium coding problem on arrays, dynamic programming and matrix, asked in Amazon, Google and Uber interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} mines
 * @return {number}
 */
var orderOfLargestPlusSign = function(n, mines) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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.

Hints for Largest Plus Sign

  1. Hint 1

    The order at a cell is the shortest of its four runs of consecutive 1s.

  2. Hint 2

    Each of the four run lengths can be filled in with one linear sweep per row or column.

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

  1. Mark the mines in an n × n grid and start dp at n everywhere.
  2. 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.
  3. Do the same down and up each column.
  4. 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)

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