Largest 1-Bordered Square

MEDIUM

Description

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.

Example 1:

Input: grid = [[1,1,1],[1,0,1],[1,1,1]]
Output: 9

Example 2:

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

Constraints:

1 <= grid.length <= 100
1 <= grid[0].length <= 100
grid[i][j] is 0 or 1

Approaches

Checkout 2 different approaches to solve Largest 1-Bordered Square. Click on different approaches to view the approach and algorithm in detail.

Brute Force Enumeration

This straightforward approach involves iterating through every possible top-left corner and every possible size for a square subgrid. For each potential square, it explicitly checks if all four borders consist of '1's.

Algorithm

Initialize maxLen = 0.
Iterate through each cell (r, c) of the grid, treating it as a potential top-left corner of a square.
For each (r, c), iterate through all possible side lengths len from 1 up to the maximum possible from that corner (min(rows - r, cols - c)).
For each potential square defined by (r, c) and len, check if its border is composed entirely of 1s.
- This involves checking four sides: the top row from c to c + len - 1 at row r, the bottom row at r + len - 1, the left column from r to r + len - 1 at column c, and the right column at c + len - 1.
If all four sides consist of 1s, update maxLen = max(maxLen, len).
After checking all possibilities, return maxLen * maxLen.

The algorithm uses three nested loops. The outer two loops select a cell (r, c) as the potential top-left corner of a square. The third loop iterates through possible side lengths len, starting from 1. For each combination of (r, c, len), a helper function is called to verify the border. This helper function iterates along the top, bottom, left, and right edges of the potential square. If it finds any '0', it invalidates the square. If the square is valid, we update our record of the maximum side length found so far. This process is repeated for all possible squares in the grid.

class Solution {
    public int largest1BorderedSquare(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        int maxLen = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                for (int len = 1; r + len <= rows && c + len <= cols; len++) {
                    if (isBordered(grid, r, c, len)) {
                        maxLen = Math.max(maxLen, len);
                    }
                }
            }
        }
        return maxLen * maxLen;
    }

    private boolean isBordered(int[][] grid, int r, int c, int len) {
        // Check top and bottom borders
        for (int j = c; j < c + len; j++) {
            if (grid[r][j] == 0 || grid[r + len - 1][j] == 0) {
                return false;
            }
        }
        // Check left and right borders
        for (int i = r; i < r + len; i++) {
            if (grid[i][c] == 0 || grid[i][c + len - 1] == 0) {
                return false;
            }
        }
        return true;
    }
}

Complexity Analysis

Time Complexity: O(m * n * min(m, n) * min(m, n)). For an N x N grid, this is O(N^4). There are O(N^3) possible squares, and verifying each takes O(N) time.Space Complexity: O(1), as no extra space proportional to the input size is used.

Pros and Cons

Pros:

Simple to understand and implement.
Uses constant extra space (O(1)).

Cons:

Extremely inefficient due to multiple nested loops and redundant checks.
The time complexity of O(N^4) makes it infeasible for the given constraints, likely leading to a 'Time Limit Exceeded' error.

Code Solutions

Checking out 3 solutions in different languages for Largest 1-Bordered Square. Click on different languages to view the code.

class Solution {
public
  int largest1BorderedSquare(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] down = new int[m][n];
    int[][] right = new int[m][n];
    for (int i = m - 1; i >= 0; --i) {
      for (int j = n - 1; j >= 0; --j) {
        if (grid[i][j] == 1) {
          down[i][j] = i + 1 < m ? down[i + 1][j] + 1 : 1;
          right[i][j] = j + 1 < n ? right[i][j + 1] + 1 : 1;
        }
      }
    }
    for (int k = Math.min(m, n); k > 0; --k) {
      for (int i = 0; i <= m - k; ++i) {
        for (int j = 0; j <= n - k; ++j) {
          if (down[i][j] >= k && right[i][j] >= k && right[i + k - 1][j] >= k &&
              down[i][j + k - 1] >= k) {
            return k * k;
          }
        }
      }
    }
    return 0;
  }
}

Video Solution

Watch the video walkthrough for Largest 1-Bordered Square

Patterns:

Dynamic Programming

Data Structures:

ArrayMatrix

Companies:

Samsung |DE Shaw |ZS Associates |