C# Coding Test Course, Finding the Largest Square

1. Problem Description

This problem is to find the largest single square in a given binary matrix and return its size.
A binary matrix consists of elements that are either 0 or 1.
We need to find the largest square composed of 1s, where the size is defined as the length of the square’s side.

Example

  • Input: matrix = [[0,1,1,1,0],[0,1,1,1,1],[0,1,1,1,1],[0,0,0,0,0]]
  • Output: 3 (length of the side of the largest square)

2. Approach to Solve the Problem

To solve this problem, we can use the Dynamic Programming technique.
The basic idea is to use the information from the left, above, and diagonally above positions (minimum size) to determine
the size of the square that can be formed at the current position.

2.1 State Definition

dp[i][j] is defined as the maximum size of the square that can be formed at row i and column j.
That is, the value of dp[i][j] is set to 1 plus the minimum of dp[i-1][j], dp[i][j-1], dp[i-1][j-1] when matrix[i][j] is 1.
If matrix[i][j] is 0, then dp[i][j] becomes 0.

2.2 Recurrence Relation

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

2.3 Initial Conditions

For the first row and the first column, if matrix[i][j] is 1, then dp[i][j] is also set to 1,
and if it is 0, it is initialized to 0.

3. Algorithm Implementation

Below is the C# code based on the above approach. 

C#
public class Solution {
    public int MaximalSquare(char[][] matrix) {
        if (matrix.Length == 0) return 0;
        
        int maxSide = 0;
        int rows = matrix.Length;
        int cols = matrix[0].Length;
        int[][] dp = new int[rows][];
        
        for (int i = 0; i < rows; i++) {
            dp[i] = new int[cols];
        }

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == '1') {
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1; // Set directly to 1 for edge cases
                    } else {
                        dp[i][j] = Math.Min(Math.Min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
                    }
                    maxSide = Math.Max(maxSide, dp[i][j]); // Update maximum size
                }
            }
        }
        
        return maxSide * maxSide; // Return area of the square
    }
}

4. Complexity Analysis

The time complexity of this algorithm is O(m * n), where m is the number of rows in the matrix and n is the number of columns.
This complexity arises because each element is checked only once.
The space complexity is also O(m * n) due to the use of a dynamic array.

5. Conclusion

This problem showcases a powerful application of dynamic programming.
Through this problem of finding squares in a binary matrix, we learned how to think in terms of dynamic programming and how to design algorithms effectively.
It is important to gain a thorough understanding of how to solve such problems in C#.

6. Additional Learning Resources