Number of corner rectangles

Array Math Dynamic Programming Matrix

67.9% acceptance

Mar 31, 2026

633

Given an m x n integer matrix grid where each entry is only 0 or 1, return the number of corner rectangles. A corner rectangle is four distinct 1's on the grid that forms an axis-aligned rectangle. Note that only the corners need to have the value 1. Also, all four 1's used must be distinct.

Solution

Rust

Time O(n³)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn count_corner_rectangles(grid: Vec<Vec<i32>>) -> i32 {
    let m = grid.len();
    let n = grid[0].len();
    let mut result = 0;
    for r1 in 0..m {
      for r2 in (r1 + 1)..m {
        let mut common = 0i32;
        for c in 0..n {
          if grid[r1][c] == 1 && grid[r2][c] == 1 {
            common += 1;
          }
        }
        result += common * (common - 1) / 2;
      }
    }
    result
  }
}