Largest Plus Sign - Practice Coding Problems

Largest Plus Sign - Problem

You are given an integer n. You have an n x n binary grid grid with all values initially 1's except for some indices given in the array mines.

The i-th element of the array mines is defined as mines[i] = [x_i, y_i] where grid[x_i][y_i] == 0.

Return the order of the largest axis-aligned plus sign of 1's contained in grid. If there is none, return 0.

An axis-aligned plus sign of 1's of order k has some center grid[r][c] == 1 along with four arms of length k - 1 going up, down, left, and right, and made of 1's. Note that there could be 0's or 1's beyond the arms of the plus sign, only the relevant area of the plus sign is checked for 1's.

Input & Output

Example 1 — Basic Grid

$ Input: n = 5, mines = [[4,2]]

› Output: 2

💡 Note: Grid is 5×5 with all 1's except mines at (4,2). The largest plus sign has order 2, can be centered at multiple positions like (1,2), (2,2), etc.

Example 2 — Single Cell

$ Input: n = 1, mines = []

› Output: 1

💡 Note: 1×1 grid with single cell containing 1. The plus sign order is 1 (just the center, no arms).

Example 3 — All Mines

$ Input: n = 1, mines = [[0,0]]

› Output: 0

💡 Note: Only cell is a mine (0), so no plus sign can be formed.

Constraints

1 ≤ n ≤ 500
1 ≤ mines.length ≤ 5000
0 ≤ x_i, y_i < n
All the pairs (x_i, y_i) are unique.

Visualization

Tap to expand

Understanding the Visualization

Input Grid

n×n grid with 1's except at mine positions

Find Plus Signs

Check each cell as potential plus center

Calculate Order

Order = min(arm lengths in 4 directions) + 1

Key Takeaway

🎯 Key Insight: Pre-compute consecutive 1's from each direction to avoid O(n⁴) redundant checking

Asked in

G Google 15 F Facebook 8

The key insight is to pre-compute consecutive 1's from each direction using dynamic programming to avoid redundant calculations. Best approach uses 2D DP with 4 arrays storing arm lengths. Time: O(n²), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check Every Center	O(n⁴)	O(n²)	For each cell, check if it can be center of plus sign by extending arms in 4 directions
Dynamic Programming - Pre-compute Arm Lengths	O(n²)	O(n²)	Pre-calculate consecutive 1's from each direction for all cells to avoid redundant work

Brute Force - Check Every Center — Algorithm Steps

Create grid and mark mines as 0
For each cell (r,c), try as plus center
Extend arms in 4 directions until hitting 0 or boundary
Order = min(up, down, left, right) + 1
Track maximum order found

Visualization

Tap to expand

Step-by-Step Walkthrough

Try Center

Test each cell as potential plus center

Extend Arms

Count consecutive 1's in up/down/left/right directions

Calculate Order

Order = min(arm lengths) + 1 for the center

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int min(int a, int b) {
    return a < b ? a : b;
}

int solution(int n, int mines[][2], int minesSize) {
    // Create grid with all 1's
    int** grid = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        grid[i] = (int*)malloc(n * sizeof(int));
        for (int j = 0; j < n; j++) {
            grid[i][j] = 1;
        }
    }
    
    // Mark mines as 0
    for (int i = 0; i < minesSize; i++) {
        grid[mines[i][0]][mines[i][1]] = 0;
    }
    
    int maxOrder = 0;
    
    // Try each cell as center
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == 0) continue;
            
            // Check arms in 4 directions
            int up = 0, down = 0, left = 0, right = 0;
            
            // Up
            for (int i = r - 1; i >= 0; i--) {
                if (grid[i][c] == 1) up++;
                else break;
            }
            
            // Down
            for (int i = r + 1; i < n; i++) {
                if (grid[i][c] == 1) down++;
                else break;
            }
            
            // Left
            for (int i = c - 1; i >= 0; i--) {
                if (grid[r][i] == 1) left++;
                else break;
            }
            
            // Right
            for (int i = c + 1; i < n; i++) {
                if (grid[r][i] == 1) right++;
                else break;
            }
            
            // Order is min arm length + 1 (for center)
            int order = min(min(up, down), min(left, right)) + 1;
            if (order > maxOrder) maxOrder = order;
        }
    }
    
    // Free memory
    for (int i = 0; i < n; i++) {
        free(grid[i]);
    }
    free(grid);
    
    return maxOrder;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[10000];
    scanf(" %s", line);
    
    // Parse mines array - simplified for basic cases
    int mines[500][2];
    int minesSize = 0;
    
    if (strcmp(line, "[]") != 0) {
        // Simple parsing for format [[x,y],[x,y],...]
        char* ptr = line + 1; // Skip first [
        while (*ptr && *ptr != ']') {
            if (*ptr == '[') {
                ptr++;
                mines[minesSize][0] = atoi(ptr);
                while (*ptr && *ptr != ',') ptr++;
                ptr++;
                mines[minesSize][1] = atoi(ptr);
                minesSize++;
                while (*ptr && *ptr != ']') ptr++;
                ptr++;
            }
            ptr++;
        }
    }
    
    printf("%d\n", solution(n, mines, minesSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n⁴)

For each of n² cells, we potentially check up to n cells in 4 directions

✓ Linear Growth

Space Complexity

O(n²)

Grid storage to mark mines as 0

⚠ Quadratic Space

28.0K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check Every Center — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler