Problem

Given a 2D binary matrix mat (values 0 or 1), find the area (number of cells) of the largest axis-aligned rectangle whose border cells are all 1. The interior of the rectangle may contain 0s.

Examples

Example 1

$$ \begin{array}{|c|c|c|c|c|} \hline 0 & {1} & 0 & 0 & 0 \\ \hline 0 & {1} & 0 & 0 & 0 \\ \hline {1} & {\color{green}1} & {\color{green}1} & {\color{green}1} & 0 \\ \hline 0 & {\color{green}1} & 0 & {\color{green}1} & 0 \\ \hline 0 & {\color{green}1} & {\color{green}1} & {\color{green}1} & 0 \\ \hline \end{array} $$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Input:mat = 
[
	[0, 1, 0, 0, 0],
	[0, 1, 0, 0, 0],
	[1, 1, 1, 1, 0],
	[0, 1, 0, 1, 0],
	[0, 1, 1, 1, 0],
]
Output: 9
Explanation: The bolded rectangle (3x3) has border of all 1s.
Similar Problems

Solution

Method 1 — Brute force (enumerate all rectangles)

Intuition

Try every pair of rows r1 <= r2 and columns c1 <= c2 and explicitly check the four borders for 1s.

Approach

  • For each r1 in 0..n-1 and each r2 in r1..n-1.
  • For each c1 in 0..m-1 and each c2 in c1..m-1.
  • Check the top row mat[r1][c1..c2], bottom row mat[r2][c1..c2], left column mat[r1..r2][c1] and right column mat[r1..r2][c2] are all 1s.
  • If valid, update ans = max(ans, (r2-r1+1)*(c2-c1+1)).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
 public:
  int largest1BorderedRectangle(std::vector<std::vector<int>>& mat) {
    int n = mat.size();
    int m = mat[0].size();
    int ans = 0;
    for (int r1 = 0; r1 < n; ++r1) {
      for (int r2 = r1; r2 < n; ++r2) {
        for (int c1 = 0; c1 < m; ++c1) {
          for (int c2 = c1; c2 < m; ++c2) {
            bool ok = true;
            for (int j = c1; j <= c2 && ok; ++j) {
              if (!mat[r1][j] || !mat[r2][j]) ok = false;
            }
            for (int i = r1; i <= r2 && ok; ++i) {
              if (!mat[i][c1] || !mat[i][c2]) ok = false;
            }
            if (ok) ans = std::max(ans, (r2 - r1 + 1) * (c2 - c1 + 1));
          }
        }
      }
    }
    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

package main

func largest1BorderedRectangle(mat [][]int) int {
    n := len(mat)
    m := len(mat[0])
    ans := 0
    for r1 := 0; r1 < n; r1++ {
        for r2 := r1; r2 < n; r2++ {
            for c1 := 0; c1 < m; c1++ {
                for c2 := c1; c2 < m; c2++ {
                    ok := true
                    for j := c1; j <= c2 && ok; j++ {
                        if mat[r1][j] == 0 || mat[r2][j] == 0 { ok = false }
                    }
                    for i := r1; i <= r2 && ok; i++ {
                        if mat[i][c1] == 0 || mat[i][c2] == 0 { ok = false }
                    }
                    if ok {
                        area := (r2 - r1 + 1) * (c2 - c1 + 1)
                        if area > ans { ans = area }
                    }
                }
            }
        }
    }
    return ans
}

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
  public int largest1BorderedRectangle(int[][] mat) {
    int n = mat.length, m = mat[0].length;
    int ans = 0;
    for (int r1 = 0; r1 < n; ++r1) {
      for (int r2 = r1; r2 < n; ++r2) {
        for (int c1 = 0; c1 < m; ++c1) {
          for (int c2 = c1; c2 < m; ++c2) {
            boolean ok = true;
            for (int j = c1; j <= c2 && ok; ++j) {
              if (mat[r1][j] == 0 || mat[r2][j] == 0) ok = false;
            }
            for (int i = r1; i <= r2 && ok; ++i) {
              if (mat[i][c1] == 0 || mat[i][c2] == 0) ok = false;
            }
            if (ok) ans = Math.max(ans, (r2 - r1 + 1) * (c2 - c1 + 1));
          }
        }
      }
    }
    return ans;
  }
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def largest1BorderedRectangle(self, mat: list[list[int]]) -> int:
        n = len(mat)
        m = len(mat[0])
        ans = 0
        for r1 in range(n):
            for r2 in range(r1, n):
                for c1 in range(m):
                    for c2 in range(c1, m):
                        ok = True
                        for j in range(c1, c2+1):
                            if mat[r1][j] == 0 or mat[r2][j] == 0:
                                ok = False
                                break
                        if not ok:
                            continue
                        for i in range(r1, r2+1):
                            if mat[i][c1] == 0 or mat[i][c2] == 0:
                                ok = False
                                break
                        if ok:
                            ans = max(ans, (r2 - r1 + 1) * (c2 - c1 + 1))
        return ans

Complexity

  • ⏰ Time complexity: O(n^4) — four nested loops enumerating rows and columns and border checks in O(n) are subsumed by the enumeration worst-case; for an n x n matrix this is quartic.
  • 🧺 Space complexity: O(1) additional space.

Method 2 — Precompute horizontal/vertical run-lengths

Intuition

Precompute at each cell hor[i][j] = number of consecutive 1s ending at (i,j) horizontally, and ver[i][j] = number of consecutive 1s ending at (i,j) vertically. For a candidate bottom-right corner (i,j), any rectangle of width w and height h ending at (i,j) is valid if hor[i][j] >= w, ver[i][j] >= h, ver[i][j-w+1] >= h and hor[i-h+1][j] >= w — each check is O(1).

Approach

  • Build hor and ver arrays in O(n*m).
  • For each cell (i,j) as bottom-right corner, iterate possible heights h = 1..ver[i][j] and widths w = 1..hor[i][j] (or iterate w/h in nested loops). For each pair check the four O(1) conditions above; update ans.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
 public:
  int largest1BorderedRectangle(std::vector<std::vector<int>>& mat) {
    int n = mat.size();
    int m = mat[0].size();
    std::vector<std::vector<int>> hor(n, std::vector<int>(m));
    std::vector<std::vector<int>> ver(n, std::vector<int>(m));
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        if (mat[i][j] == 1) {
          hor[i][j] = (j ? hor[i][j-1] : 0) + 1;
          ver[i][j] = (i ? ver[i-1][j] : 0) + 1;
        }
      }
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        for (int h = 1; h <= ver[i][j]; ++h) {
          for (int w = 1; w <= hor[i][j]; ++w) {
            int r1 = i - h + 1;
            int c1 = j - w + 1;
            if (ver[i][c1] >= h && hor[r1][j] >= w) {
              ans = std::max(ans, h * w);
            }
          }
        }
      }
    }
    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

package main

func largest1BorderedRectangle(mat [][]int) int {
    n := len(mat)
    m := len(mat[0])
    hor := make([][]int, n)
    ver := make([][]int, n)
    for i := range hor { hor[i] = make([]int, m); ver[i] = make([]int, m) }
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            if mat[i][j] == 1 {
                if j > 0 { hor[i][j] = hor[i][j-1] + 1 } else { hor[i][j] = 1 }
                if i > 0 { ver[i][j] = ver[i-1][j] + 1 } else { ver[i][j] = 1 }
            }
        }
    }
    ans := 0
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            for h := 1; h <= ver[i][j]; h++ {
                for w := 1; w <= hor[i][j]; w++ {
                    r1 := i - h + 1
                    c1 := j - w + 1
                    if ver[i][c1] >= h && hor[r1][j] >= w {
                        area := h * w
                        if area > ans { ans = area }
                    }
                }
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
  public int largest1BorderedRectangle(int[][] mat) {
    int n = mat.length, m = mat[0].length;
    int[][] hor = new int[n][m], ver = new int[n][m];
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        if (mat[i][j] == 1) {
          hor[i][j] = (j > 0 ? hor[i][j-1] : 0) + 1;
          ver[i][j] = (i > 0 ? ver[i-1][j] : 0) + 1;
        }
      }
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        for (int h = 1; h <= ver[i][j]; ++h) {
          for (int w = 1; w <= hor[i][j]; ++w) {
            int r1 = i - h + 1;
            int c1 = j - w + 1;
            if (ver[i][c1] >= h && hor[r1][j] >= w) ans = Math.max(ans, h * w);
          }
        }
      }
    }
    return ans;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def largest1BorderedRectangle(self, mat: list[list[int]]) -> int:
        n = len(mat)
        m = len(mat[0])
        hor = [[0]*m for _ in range(n)]
        ver = [[0]*m for _ in range(n)]
        for i in range(n):
            for j in range(m):
                if mat[i][j] == 1:
                    hor[i][j] = (hor[i][j-1] if j>0 else 0) + 1
                    ver[i][j] = (ver[i-1][j] if i>0 else 0) + 1
        ans = 0
        for i in range(n):
            for j in range(m):
                for h in range(1, ver[i][j]+1):
                    for w in range(1, hor[i][j]+1):
                        r1 = i - h + 1
                        c1 = j - w + 1
                        if ver[i][c1] >= h and hor[r1][j] >= w:
                            ans = max(ans, h * w)
        return ans

Complexity

  • ⏰ Time complexity: O(n^4) worst-case — preprocessing is O(n*m), but enumerating bottom-right corners and all possible h,w yields quartic behavior for dense 1 matrices.
  • 🧺 Space complexity: O(n*m) to store hor and ver.