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:
- The number of rows and columns of
gridwill each be in the range[1, 200]. - Each
grid[i][j]will be either0or1. - The number of
1s in the grid will be at most6000.
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.