Largest 1-Bordered Square - Practice Coding Problems

Largest 1-Bordered Square - Problem

Given a 2D grid of 0s and 1s, return the number of elements in the largest square subgrid that has all 1s on its border, or 0 if such a subgrid doesn't exist in the grid.

A square subgrid has all 1s on its border if all the cells on the top, bottom, left, and right edges are 1s. The interior of the square can contain any values.

Input & Output

Example 1 — Perfect Border Square

$ Input: grid = [[1,1,1],[1,0,1],[1,1,1]]

› Output: 9

💡 Note: The entire 3×3 grid has all 1s on its border (edges), with interior cell [1][1] = 0. This forms a valid 1-bordered square of size 9.

Example 2 — Multiple Small Squares

$ Input: grid = [[1,1,0,0],[1,1,0,0],[0,0,1,1],[0,0,1,1]]

› Output: 4

💡 Note: We can find 2×2 squares at positions (0,0) and (2,2), each having all border cells as 1s. Maximum area is 2×2 = 4.

Example 3 — No Valid Square

$ Input: grid = [[1,0,1],[0,1,0],[1,0,1]]

› Output: 1

💡 Note: No square larger than 1×1 has all 1s on its border. The maximum valid square has area 1.

Constraints

1 ≤ grid.length, grid[i].length ≤ 15
grid[i][j] is either 0 or 1

Visualization

Tap to expand

Understanding the Visualization

Input Grid

2D grid with 0s and 1s

Find Borders

Check if square borders contain only 1s

Output Size

Return area of largest valid square

Key Takeaway

🎯 Key Insight: Only the border cells need to be 1s - interior cells can have any values

Asked in

G Google 12 a Amazon 8 M Microsoft 6 Apple 4

The key insight is that only border cells matter - interior can contain any values. Best approach uses Dynamic Programming to precompute consecutive 1s, enabling O(1) border validation. Time: O(n³), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming - Precompute Consecutive 1s	O(n³)	O(n²)	Precompute horizontal and vertical runs of 1s to quickly validate square borders
Brute Force - Check All Squares	O(n⁴)	O(1)	For each position, try all possible square sizes and check if border is all 1s

Dynamic Programming - Precompute Consecutive 1s — Algorithm Steps

Build horizontal DP table: consecutive 1s extending right from each cell
Build vertical DP table: consecutive 1s extending down from each cell
For each position and size, use DP tables to validate borders in O(1)
Track maximum valid square found

Visualization

Tap to expand

Step-by-Step Walkthrough

Build DP Tables

Compute horizontal and vertical runs from each cell

Check Square

Use DP values to validate border in O(1)

Fast Validation

Compare DP values with required square size

Code -

solution.c — C

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

int isValidSquare(int** grid, int** horizontal, int** vertical, int row, int col, int size) {
    // Check if we can form a square of given size at (row, col)
    // Top and bottom edges need horizontal runs of 'size'
    if (horizontal[row][col] < size || 
        horizontal[row + size - 1][col] < size) {
        return 0;
    }
    
    // Left and right edges need vertical runs of 'size'
    if (vertical[row][col] < size || 
        vertical[row][col + size - 1] < size) {
        return 0;
    }
    
    return 1;
}

int solution(int** grid, int rows, int cols) {
    if (grid == NULL || rows == 0 || cols == 0) {
        return 0;
    }
    
    // Allocate DP tables
    int** horizontal = (int**)malloc(rows * sizeof(int*));
    int** vertical = (int**)malloc(rows * sizeof(int*));
    for (int i = 0; i < rows; i++) {
        horizontal[i] = (int*)calloc(cols, sizeof(int));
        vertical[i] = (int*)calloc(cols, sizeof(int));
    }
    
    // Build horizontal DP table (right to left)
    for (int i = 0; i < rows; i++) {
        for (int j = cols - 1; j >= 0; j--) {
            if (grid[i][j] == 1) {
                horizontal[i][j] = 1 + (j + 1 < cols ? horizontal[i][j + 1] : 0);
            }
        }
    }
    
    // Build vertical DP table (bottom to top)
    for (int i = rows - 1; i >= 0; i--) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == 1) {
                vertical[i][j] = 1 + (i + 1 < rows ? vertical[i + 1][j] : 0);
            }
        }
    }
    
    int maxSize = 0;
    
    // Try every possible top-left corner and size
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            int maxPossible = (rows - i) < (cols - j) ? (rows - i) : (cols - j);
            for (int size = 1; size <= maxPossible; size++) {
                if (isValidSquare(grid, horizontal, vertical, i, j, size)) {
                    int currentSize = size * size;
                    if (currentSize > maxSize) {
                        maxSize = currentSize;
                    }
                }
            }
        }
    }
    
    // Free DP tables
    for (int i = 0; i < rows; i++) {
        free(horizontal[i]);
        free(vertical[i]);
    }
    free(horizontal);
    free(vertical);
    
    return maxSize;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Simple parsing for demo - in practice would need robust JSON parsing
    int rows = 3, cols = 3; // Assuming 3x3 for demo
    int** grid = (int**)malloc(rows * sizeof(int*));
    for (int i = 0; i < rows; i++) {
        grid[i] = (int*)malloc(cols * sizeof(int));
    }
    
    // Parse simple case [[1,1,1],[1,0,1],[1,1,1]]
    grid[0][0] = 1; grid[0][1] = 1; grid[0][2] = 1;
    grid[1][0] = 1; grid[1][1] = 0; grid[1][2] = 1;
    grid[2][0] = 1; grid[2][1] = 1; grid[2][2] = 1;
    
    int result = solution(grid, rows, cols);
    printf("%d\n", result);
    
    for (int i = 0; i < rows; i++) {
        free(grid[i]);
    }
    free(grid);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

O(n²) to build DP tables, then O(n²) positions × O(n) sizes with O(1) validation

⚠ Quadratic Growth

Space Complexity

O(n²)

Two DP tables of size n×m for horizontal and vertical runs

⚠ Quadratic Space

23.5K Views

Medium Frequency

~25 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

Dynamic Programming - Precompute Consecutive 1s — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler