750. Number Of Corner Rectangles

Given a grid where each entry is only 0 or 1, find the number of corner rectangles.

A corner rectangle is 4 distinct 1s on the grid that form an axis-aligned rectangle. Note that only the corners need to have the value 1. Also, all four 1s used must be distinct.

 

Example 1:

Input: grid = 
[[1, 0, 0, 1, 0],
 [0, 0, 1, 0, 1],
 [0, 0, 0, 1, 0],
 [1, 0, 1, 0, 1]]
Output: 1
Explanation: There is only one corner rectangle, with corners grid[1][2], grid[1][4], grid[3][2], grid[3][4].

 

Example 2:

Input: grid = 
[[1, 1, 1],
 [1, 1, 1],
 [1, 1, 1]]
Output: 9
Explanation: There are four 2x2 rectangles, four 2x3 and 3x2 rectangles, and one 3x3 rectangle.

 

Example 3:

Input: grid = 
[[1, 1, 1, 1]]
Output: 0
Explanation: Rectangles must have four distinct corners.

 

Note:

  1. The number of rows and columns of grid will each be in the range [1, 200].
  2. Each grid[i][j] will be either 0 or 1.
  3. The number of 1s in the grid will be at most 6000.

 

Rust Solution

struct Solution;

impl Solution {
    fn count_corner_rectangles(grid: Vec<Vec<i32>>) -> i32 {
        let m = grid[0].len();
        let mut res = 0;
        let mut dp = vec![vec![0; m]; m];
        for row in grid {
            for l in 0..m - 1 {
                if row[l] == 1 {
                    for r in l + 1..m {
                        if row[r] == 1 {
                            res += dp[l][r];
                            dp[l][r] += 1;
                        }
                    }
                }
            }
        }
        res
    }
}

#[test]
fn test() {
    let grid = vec_vec_i32![
        [1, 0, 0, 1, 0],
        [0, 0, 1, 0, 1],
        [0, 0, 0, 1, 0],
        [1, 0, 1, 0, 1]
    ];
    let res = 1;
    assert_eq!(Solution::count_corner_rectangles(grid), res);
    let grid = vec_vec_i32![[1, 1, 1], [1, 1, 1], [1, 1, 1]];
    let res = 9;
    assert_eq!(Solution::count_corner_rectangles(grid), res);
    let grid = vec_vec_i32![[1, 1, 1, 1]];
    let res = 0;
    assert_eq!(Solution::count_corner_rectangles(grid), res);
}

Having problems with this solution? Click here to submit an issue on github.