Number Of Corner Rectangles

Number Of Corner Rectangles

What is this problem about?

The Number Of Corner Rectangles problem gives you a binary matrix. Count the number of rectangles that can be formed where all four corners are cells with value 1. The sides of the rectangle must be aligned with the grid rows and columns. This coding problem uses a combinatorial pair-counting technique on rows.

Why is this asked in interviews?

Meta asks this because the naive O(n²m²) approach (check all rectangle combinations) is too slow, but the O(m²n) approach — counting pairs of 1-columns shared between rows — is elegant and efficient. The array, matrix, math, and dynamic programming interview pattern is exercised.

Algorithmic pattern used

Row-pair DP. For each pair of rows (r1, r2), count the number of columns where both rows have a 1. Call this count k. The number of rectangles with these two rows as top/bottom = k * (k-1) / 2 (choose 2 from k columns). Sum this across all row pairs. Use a hash map of (r1, r2) column-pair counts for O(m * n) overall.

Example explanation

Matrix:

1 0 1
1 0 1
1 1 1

Rows 0 and 1: both have 1s at columns 0, 2. k=2. Rectangles = C(2,2)=1. Rows 0 and 2: columns 0, 2. k=2. Rectangles = 1. Rows 1 and 2: columns 0, 2. k=2. Rectangles = 1. Total = 3.

Common mistakes candidates make

• Brute-forcing all four-corner combinations (O(n²m²), too slow).
• Computing C(k,2) as k*(k+1)/2 instead of k*(k-1)/2.
• Not iterating all pairs of rows efficiently.
• Double-counting rectangles by processing row pairs in both orders.

Interview preparation tip

Corner rectangle counting is a "fix two rows, count common columns" technique. This same "fix two of three dimensions" approach appears in counting submatrices with all 1s, counting rectangles in point sets, and 3D counting problems. Practice the combinatorial formula C(k,2) = k*(k-1)/2 for counting pairs from a group. When you see a counting problem on 2D grids, think about fixing one dimension and counting in the other.