Scale Engineer

Largest 1-Bordered Square

Med
#1074Time: 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: O(1), as no extra space proportional to the input size is used.3 companies
Patterns
Dynamic Programming
Data structures
ArrayMatrix
Companies
SamsungDE ShawZS Associates

Prompt

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

2 approaches with complexity analysis and trade-offs.

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

  1. Initialize maxLen = 0.
  2. Iterate through each cell (r, c) of the grid, treating it as a potential top-left corner of a square.
  3. 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)).
  4. 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.
  5. If all four sides consist of 1s, update maxLen = max(maxLen, len).
  6. After checking all possibilities, return maxLen * maxLen.

Walkthrough

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

Time

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

O(1), as no extra space proportional to the input size is used.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem