Don't be ashamed of N^4 (well, in some cases)

Polynomial solutions are of course exponentially better than non-polynomial solutions (pun-intended). Comparing an N^2 with a 2^N is a no brainer, same for LogN with a SQRT(N) (the former is way better than the latter). The value of N clearly matters, though. The problem below is solved with an N^4 solution, where N=100. Now it is pushing the limits of LC, which won't ever accept a 10^9 solution (billion), but in some cases 100M is tractable. That's the case here. Best way to solve it IMO is to have a function to check whether the boundaries of the sub-matrix form a valid square. That one is tricky, requires some careful calculations. It runs in O(N). Once you have it, then you still need an N^3 nested-loops to check each sub-matrix. If N is relatively small, don't be ashamed of N^4. There must be a way to do it faster, but this is the best that your friend here could come up with. Cheers, ACC.

Largest 1-Bordered Square - LeetCode

1139. Largest 1-Bordered Square

Medium

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

Accepted

24,869

Submissions

49,582

public int Largest1BorderedSquare(int[][] grid)
{
    int retVal = 0;
    for (int r = 0; r < grid.Length; r++)
    {
        for (int c = 0; c < grid[r].Length; c++)
        {
            int cDelta = 0;
            int len = 0;
            while (c + cDelta < grid[r].Length && grid[r][c + cDelta] == 1)
            {
                len++;
                if (IsSquare(grid, r, c + cDelta, len))
                    retVal = Math.Max(retVal, len * len);
                cDelta++;
            }
        }
    }

    return retVal;
}

private bool IsSquare(int[][] grid, int initRow, int endCol, int len)
{
    //Down
    bool isSquare = true;
    for (int r = 0; r < len; r++)
    {
        if (initRow + r >= grid.Length || 
            grid[initRow + r][endCol] != 1)
        {
            isSquare = false;
            break;
        }
    }
    if (!isSquare) return false;

    //Left
    for (int c = 0; c < len; c++)
    {
        if (initRow + len - 1 >= grid.Length ||
            endCol - c < 0 ||
            grid[initRow + len - 1][endCol - c] != 1)
        {
            isSquare = false;
            break;
        }
    }
    if (!isSquare) return false;

    //Up
    for (int r = 0; r < len; r++)
    {
        if (initRow + r >= grid.Length ||
            endCol - len + 1 < 0 ||
            grid[initRow + r][endCol - len + 1] != 1)
        {
            isSquare = false;
            break;
        }
    }

    return isSquare;
}