Number Of Corner Rectangles

medium array matrix counting

Problem

Given a binary grid, count the number of corner rectangles formed by four 1s located at the corners of an axis-aligned rectangle.

Inputgrid=[[1,0,0,1,0],[0,0,1,0,1],[0,0,0,1,0],[1,0,1,0,1]]

Output1

Only one axis-aligned rectangle uses 1s at all four corners.

input

def countCornerRectangles(grid):
    from collections import Counter
    pair_count = Counter()
    res = 0
    for row in grid:
        cols = [i for i, v in enumerate(row) if v == 1]
        for i in range(len(cols)):
            for j in range(i + 1, len(cols)):
                p = (cols[i], cols[j])
                res += pair_count[p]
                pair_count[p] += 1
    return res

function countCornerRectangles(grid) {
  const pairs = new Map(); let res = 0;
  for (const row of grid) {
    const cols = [];
    for (let i = 0; i < row.length; i++) if (row[i] === 1) cols.push(i);
    for (let i = 0; i < cols.length; i++) for (let j = i + 1; j < cols.length; j++) {
      const k = cols[i] * 256 + cols[j];
      res += pairs.get(k) || 0;
      pairs.set(k, (pairs.get(k) || 0) + 1);
    }
  }
  return res;
}

class Solution {
  public int countCornerRectangles(int[][] grid) {
    Map<Long, Integer> pairs = new HashMap<>(); int res = 0;
    for (int[] row : grid) {
      List<Integer> cols = new ArrayList<>();
      for (int i = 0; i < row.length; i++) if (row[i] == 1) cols.add(i);
      for (int i = 0; i < cols.size(); i++) for (int j = i + 1; j < cols.size(); j++) {
        long k = ((long)cols.get(i) << 16) | cols.get(j);
        res += pairs.getOrDefault(k, 0);
        pairs.merge(k, 1, Integer::sum);
      }
    }
    return res;
  }
}

class Solution {
public:
  int countCornerRectangles(vector<vector<int>>& grid) {
    unordered_map<long, int> pairs; int res = 0;
    for (auto& row : grid) {
      vector<int> cols;
      for (int i = 0; i < (int)row.size(); i++) if (row[i] == 1) cols.push_back(i);
      for (int i = 0; i < (int)cols.size(); i++) for (int j = i + 1; j < (int)cols.size(); j++) {
        long k = ((long)cols[i] << 16) | cols[j];
        res += pairs[k];
        pairs[k]++;
      }
    }
    return res;
  }
};

Explanation

A rectangle in the grid is defined by its two side columns and its two rows, with a 1 at all four corners. The neat insight is that a rectangle is really just two different rows that both have a 1 in the same pair of columns.

So we walk through the rows one at a time and, for the current row, look at every pair of columns that both hold a 1. We keep a counter pair_count that remembers how many earlier rows already shared that exact column pair.

For each pair on the current row, every earlier row that shared it forms one rectangle with this row. So we do res += pair_count[p] first, then increment pair_count[p] so future rows can pair with this row too.

Example: if rows 0 and 3 both have 1s in columns (0, 3), then when we process row 3 and look at pair (0, 3), the counter already shows 1 (from row 0), so we add one rectangle. That single shared pair across two rows is the corner rectangle.

Counting pairs this way means we never have to test all four corners by brute force; each shared column pair instantly tells us how many rectangles it completes.

Time: O(R * C^2) Space: O(C^2)