Number Of Corner Rectangles - Video Solutions

Problem Overview: You are given a binary grid. A corner rectangle exists when four cells form the corners of a rectangle and all four values are 1. The task is to count how many such rectangles exist in the matrix.

Approach 1: Brute Force Corner Enumeration (O(m^2 * n^2) time, O(1) space)

The most direct idea is to choose two distinct rows and two distinct columns, then check whether the four corner cells contain 1. You iterate through every pair of rows and every pair of columns and verify the corners individually. This works but quickly becomes expensive since a matrix with m rows and n columns produces O(m^2 * n^2) possible rectangles. The approach is useful for reasoning about the problem but rarely passes strict constraints.

Approach 2: Column Pair Counting with Hash Table (O(m * n^2) time, O(n^2) space)

A rectangle is fully defined by two rows and two columns where all four positions are 1. Instead of selecting rows first, iterate row by row and look for pairs of columns that both contain 1. Every time a row has 1 at columns c1 and c2, treat that column pair as a potential rectangle side. Use a hash table to count how many previous rows had the same pair. If the pair appeared k times before, the current row forms k new rectangles with those rows.

This works because each repeated column pair closes rectangles vertically. The hash table maps a column pair to its frequency. For each row, enumerate all column pairs containing 1 and update the count. The approach leverages arrays and efficient pair tracking using a hash map.

Approach 3: Column Pair Counting Without Hash Map (O(m * n^2) time, O(n^2) space)

You can also maintain a 2D counter array where count[c1][c2] stores how many previous rows had 1 in both columns. When processing a new row, enumerate column pairs with value 1. Add the existing counter to the answer, then increment it. This avoids hash overhead but requires allocating a matrix sized by column pairs. The logic remains identical: repeated column pairs correspond to rectangles.

This pattern appears frequently in matrix counting problems and sometimes overlaps with ideas from dynamic programming where partial counts accumulate across rows.

Recommended for interviews: The hash table column-pair approach is what interviewers expect. It reduces the brute-force search from four nested loops to three by exploiting the fact that rectangles share column pairs across rows. Explaining the brute-force idea first demonstrates understanding of the geometry, while the optimized counting technique shows strong problem-solving and data structure skills.