Given a 2D binary matrix filled with 0's and 1's, return the area of the largest square containing only 1's.

Example (Taken from leetcode):

Input: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

Approach: Using DP. We can maintain a 2D table where Table[i][j] will tell the the side length of the maximum square whose bottom right corner is the cell with index (i, j) in the input matrix. We can maintain a maxSquareLength variable which will store the max length i.e. Max(maxSquareLength, Table[i][j]). Obviously maxSquareLength^2 will be our answer. Here is how we will fill the table:

Table[i][j] = Min ( Table[i][j - 1], Table[i - 1][j], Table[i-1][j-1]) + 1

We just need to take care of corner conditions while filling the table. 

Implementation in C#:

        public int MaximalSquare(char[][] matrix)

        {

            int[,] table = new int[matrix.Length, matrix[0].Length];

            int maxSquareLength = 0;

            for (int i = 0; i < matrix.Length; ++i)

            {

                for (int j = 0; j < matrix[0].Length; ++j)

                {

                    if (i == 0 || j == 0)

                    {

                        table[i, j] = matrix[i][j] == '1' ? 1 : 0;

                    }

                    else if (matrix[i][j] == '1')

                    {

                        table[i, j] = Min(table[i - 1, j], table[i, j - 1], table[i - 1, j - 1]) + 1;

                    }

                    maxSquareLength = Math.Max(maxSquareLength, table[i, j]);

                }

            }

            return maxSquareLength * maxSquareLength;

        }

        

        public static int Min(params int[] values)

        {

            return Enumerable.Min(values);

        }

Complexity: O(m*n)