Ph.D. Qual Study Assistant

1. The Problem

Given an `n x n` array `A` containing only zeros and ones, we need to design an algorithm to find the side length of the largest contiguous square subgrid that is composed entirely of ones. The algorithm must have a time complexity of O(n²).

2. The Idea: Dynamic Programming

This problem has an elegant solution using dynamic programming. The key is to define a DP state that builds upon previously computed subproblems.

Let `dp[i][j]` be the side length of the largest all-ones square whose bottom-right corner is at cell `A[i][j]`.

• Base Cases: The first row and column are straightforward. A square of size 1 can end at `A[i][j]` if `A[i][j]` itself is 1. So, for the first row, `dp[0][j] = A[0][j]`, and for the first column, `dp[i][0] = A[i][0]`.
• Recurrence Relation: For any other cell `(i, j)`:
  • If `A[i][j]` is 0, no square can end there, so `dp[i][j] = 0`.
  • If `A[i][j]` is 1, a square can end there. Its size is limited by its neighbors. A square of side `k` at `(i,j)` requires all-ones squares of at least side `k-1` ending at its neighbors to the left `(i, j-1)`, above `(i-1, j)`, and diagonally up-left `(i-1, j-1)`. The size is therefore constrained by the smallest of these three squares.

The final answer is the maximum value found anywhere in the `dp` table, as the largest square can end at any position.

3. The Algorithm

1. Create a new `n x n` array, `dp`. Initialize a variable `max_size = 0`.
2. Iterate through each cell `(i, j)` from `(0, 0)` to `(n-1, n-1)`.
3. Handle Base Cases (first row/col): If `i=0` or `j=0`, set `dp[i][j] = A[i][j]`.
4. Apply Recurrence: If `i > 0` and `j > 0`:
   • If `A[i][j] == 1`, calculate `dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])`.
   • If `A[i][j] == 0`, set `dp[i][j] = 0`.
5. After calculating each `dp[i][j]`, update `max_size = max(max_size, dp[i][j])`.
6. After iterating through all cells, return `max_size`.

4. Complexity Analysis

Time Complexity: O(n²)

The algorithm requires a single pass through the `n x n` grid. We visit each cell `(i, j)` exactly once to compute `dp[i][j]`. The calculation at each cell takes constant time. Thus, the total time complexity is O(n²).

Space Complexity: O(n²)

We use an auxiliary `n x n` array `dp` to store the intermediate results. This requires O(n²) space. (Note: This can be optimized to O(n) space, but O(n²) is a direct and valid solution).