Find the size of the largest sqaure matrix composed only of ones within the 2-dimentional matrix table

To solve the problem of finding the largest square submatrix composed only of 1s within a given 2D matrix, we can use Dynamic Programming.

✅ Algorithm Summary:

• We'll create a DP table where each cell dp[i,j] represents the size of the largest square ending at position (i,j) in the matrix.

• If matrix[i,j] == 1, then:

  dp[i,j] = min(dp[i-1,j], dp[i,j-1], dp[i-1,j-1]) + 1
  

• If matrix[i,j] == 0, then:

  dp[i,j] = 0
  

• We'll track the maximum value in the dp table to get the size of the largest square.

🧠 Time and Space Complexity:

• Time: O(n²)

• Space: O(n²), but it can be optimized to O(n) if needed

---

✅ C# Implementation

public class MatrixHelper
{
    public static int FindLargestSquare(int[,] matrix)
    {
        int n = matrix.GetLength(0);
        if (n == 0) return 0;

        int[,] dp = new int[n, n];
        int maxSize = 0;

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (matrix[i, j] == 1)
                {
                    if (i == 0 || j == 0)
                        dp[i, j] = 1;
                    else
                        dp[i, j] = Math.Min(Math.Min(dp[i - 1, j], dp[i, j - 1]), dp[i - 1, j - 1]) + 1;

                    maxSize = Math.Max(maxSize, dp[i, j]);
                }
            }
        }

        return maxSize;
    }
}

---

✅ Example Test Case

int[,] matrix = new int[,]
{
    {1, 0, 1, 1},
    {1, 1, 1, 1},
    {1, 1, 1, 0},
    {0, 1, 1, 1}
};

int result = MatrixHelper.FindLargestSquare(matrix); // Output: 3
Console.WriteLine(result);