Largest Plus Sign

MediumDynamic Programming2d dp

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Start with an n x n grid filled with 1s, then set to 0 every cell listed in mines (each entry is [row, col]). An axis-aligned plus sign of **order** k is a center cell of 1 with four arms of 1s extending k - 1 cells up, down, left, and right from it. Order 1 is a single 1. Cells outside the arms don't matter. Return the largest order of any plus sign in the grid, or 0 if the grid has no 1 at all.

Examples

Input: n = 5, mines = [[4,2]]
Output: 2
An order-2 plus fits around a center like (1,2). Order 3 would need center (2,2), but its lower arm hits the mine at (4,2).
Input: n = 1, mines = [[0,0]]
Output: 0
The only cell is a mine.

Constraints

  • `1 <= n <= 500`
  • `0 <= mines.length <= 5000`
  • `0 <= row, col < n`
  • All mine positions are distinct

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More 2d dp problems