Largest Plus (+) Formed by All Ones in a Binary Square Matrix

In the world of matrix problems in computer science, one interesting challenge is to find the largest "plus" or '+' shape formed by all ones in a binary square matrix. This problem has applications in various fields such as image processing (where we might be looking for certain symmetric patterns in binary images) and data analysis (identifying symmetric regions in binary - structured data). In this blog, we will explore the problem in detail, understand the common approaches to solve it, and look at best practices and example usage.

Table of Content#

  1. Problem Statement
  2. Brute - Force Approach
    • Explanation
    • Time and Space Complexity
  3. Dynamic Programming Approach
    • Intuition
    • Implementation Steps
    • Time and Space Complexity
  4. Example Usage
  5. Best Practices
  6. References

1. Problem Statement#

Given a binary square matrix mat of size n x n (where each element is either 0 or 1), find the size of the largest plus sign ('+') formed by all ones. The '+' is formed by a central cell and four arms (up, down, left, right) of equal length. For example, in the matrix:

1 1 1
1 1 1
1 1 1

The largest '+' has a size of 3 (the central cell and arms of length 1 on each side).

2. Brute - Force Approach#

Explanation#

The brute - force approach involves checking each cell in the matrix as a potential center of the '+' sign. For each cell (i,j) that has a value of 1, we check how far we can go up, down, left, and right while still encountering 1s. The minimum of these four distances (plus 1 for the central cell) gives the size of the '+' centered at (i,j).

Time and Space Complexity#

  • Time Complexity: $O(n^3)$
    • For each of the $n^2$ cells, we may have to traverse up to $n$ cells in each of the four directions (up, down, left, right).
  • Space Complexity: $O(1)$ (assuming we are not using any additional data structures for this approach)

3. Dynamic Programming Approach#

Intuition#

We can pre - compute two matrices: one for the left - to - right and top - to - bottom passes (to store the number of consecutive 1s to the left and above each cell respectively), and another for the right - to - left and bottom - to - top passes (to store the number of consecutive 1s to the right and below each cell respectively). Then, for each cell, the size of the '+' is determined by the minimum of the four pre - computed values (left, right, up, down) at that cell.

Implementation Steps#

  1. Left and Up Pass:
    • Create two matrices left and up of size n x n.
    • Initialize left[0][0] and up[0][0] as mat[0][0].
    • For the first row (i = 0), left[0][j] = left[0][j - 1]+1 if mat[0][j] == 1 (else 0).
    • For the first column (j = 0), up[i][0] = up[i - 1][0]+1 if mat[i][0] == 1 (else 0).
    • For other cells (i,j), left[i][j] = left[i][j - 1]+1 if mat[i][j] == 1 (else 0), and up[i][j] = up[i - 1][j]+1 if mat[i][j] == 1 (else 0).
  2. Right and Down Pass:
    • Create two matrices right and down of size n x n.
    • Initialize right[n - 1][n - 1] and down[n - 1][n - 1] as mat[n - 1][n - 1].
    • For the last row (i = n - 1), right[n - 1][j] = right[n - 1][j+1]+1 if mat[n - 1][j] == 1 (else 0).
    • For the last column (j = n - 1), down[i][n - 1] = down[i+1][n - 1]+1 if mat[i][n - 1] == 1 (else 0).
    • For other cells (i,j), right[i][j] = right[i][j+1]+1 if mat[i][j] == 1 (else 0), and down[i][j] = down[i+1][j]+1 if mat[i][j] == 1 (else 0).
  3. Calculate the Size of the '+':
    • Iterate through each cell (i,j) in the matrix.
    • The size of the '+' at (i,j) is min(left[i][j], right[i][j], up[i][j], down[i][j]).
    • Keep track of the maximum value found.

Time and Space Complexity#

  • Time Complexity: $O(n^2)$
    • We perform four passes (left, up, right, down) over the matrix, each of which is $O(n^2)$.
  • Space Complexity: $O(n^2)$
    • We use four additional matrices (left, up, right, down) of size n x n each. However, we can optimize the space complexity by reusing the same matrix for different passes (e.g., using a single matrix for left and right passes in a clever way).

4. Example Usage#

Let's consider the following matrix:

mat = [[1, 1, 1],
       [1, 1, 1],
       [1, 1, 1]]
  • Left Pass:
    • left[0][0]=1, left[0][1]=2, left[0][2]=3
    • left[1][0]=1, left[1][1]=2, left[1][2]=3
    • left[2][0]=1, left[2][1]=2, left[2][2]=3
  • Up Pass:
    • up[0][0]=1, up[1][0]=2, up[2][0]=3
    • up[0][1]=1, up[1][1]=2, up[2][1]=3
    • up[0][2]=1, up[1][2]=2, up[2][2]=3
  • Right Pass:
    • right[0][2]=1, right[0][1]=2, right[0][0]=3
    • right[1][2]=1, right[1][1]=2, right[1][0]=3
    • right[2][2]=1, right[2][1]=2, right[2][0]=3
  • Down Pass:
    • down[2][0]=1, down[1][0]=2, down[0][0]=3
    • down[2][1]=1, down[1][1]=2, down[0][1]=3
    • down[2][2]=1, down[1][2]=2, down[0][2]=3

For each cell (i,j), the size of the '+' is min(left[i][j], right[i][j], up[i][j], down[i][j]) = 3. So the largest '+' has a size of 3.

5. Best Practices#

  • Space Optimization: As mentioned earlier, try to reuse matrices for different passes to reduce the space complexity. For example, we can use a single matrix to store the left and right values (by first filling it with left values and then overwriting it with right values in a way that we don't lose the necessary information).
  • Input Validation: Always check if the input matrix is empty or has an incorrect size (not a square matrix).
  • Edge Cases: Consider matrices with all 0s (the result should be 0), matrices with only one row or column (the result is 1 if the single cell is 1), and matrices with a single '+' in a corner.

6. References#

  • LeetCode Problem - Largest Plus Sign
  • "Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (for general algorithmic concepts and matrix traversal techniques).
2026-07