Skip to main content
Talentd

Number Of Corner Rectangles - Solution & Explanation

MediumPremiumFree on FleetCodeArrayMathDynamic ProgrammingMatrix8 min readAsked at: Meta
Practice this problem

Problem Statement

Given an m x n integer matrix grid where each entry is only 0 or 1, return the number of corner rectangles.

A corner rectangle is four distinct 1's on the grid that forms an axis-aligned rectangle. Note that only the corners need to have the value 1. Also, all four 1's 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.

 

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • grid[i][j] is either 0 or 1.
  • The number of 1's in the grid is in the range [1, 6000].

Approach Overview

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.

Solution

We enumerate each row as the bottom of the rectangle. For the current row, if both column i and column j are 1, then we use a hash table to find out how many of the previous rows have both columns i and j as 1. This is the number of rectangles with (i, j) as the bottom right corner, and we add this number to the answer. Then we add (i, j) to the hash table and continue to enumerate the next pair (i, j).

The time complexity is O(m times n^2), and the space complexity is O(n^2). Here, m and n are the number of rows and columns of the matrix, respectively.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Corner EnumerationO(m^2 * n^2)O(1)Useful for understanding the rectangle definition or when matrix size is very small
Hash Table + Column Pair EnumerationO(m * n^2)O(n^2)Best general solution. Efficient for medium to large matrices and common in interviews
2D Pair Counter MatrixO(m * n^2)O(n^2)When avoiding hash maps or when column count is small enough to preallocate pair counters

Video Solution

Facebook Interview Question - Number Of Corner Rectangles- Leetcode 750- Python • Sephorus • 302 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Number Of Corner Rectangles easy or hard?
Number Of Corner Rectangles is considered a medium difficulty problem. The brute-force idea is straightforward, but the optimized solution requires recognizing that rectangles can be counted by tracking repeated column pairs across rows.
Number Of Corner Rectangles Python/Java solution
Python and Java implementations typically iterate through each row, collect column indices containing 1, generate all column pairs, and update a hash map that stores pair frequencies. Each previously seen pair contributes additional rectangles to the result.
How to solve Number Of Corner Rectangles in O(n)?
An O(n) solution is not possible for the general case because the algorithm must examine combinations of columns across rows. The practical optimal approach is O(m * n^2), where each row generates column pairs with value 1 and uses a hash table to accumulate rectangle counts.
What is the best approach for Number Of Corner Rectangles?
The most efficient approach counts pairs of columns that contain 1s in the same row and tracks how often each pair appears across rows. Using a hash table, each repeated column pair forms rectangles with previous rows. This reduces the complexity to O(m * n^2) time and O(n^2) space.
Is Number Of Corner Rectangles asked at Google/Amazon/Meta?
Matrix counting and combinatorial grid problems like this appear in interviews at companies such as Google, Amazon, and Meta. Interviewers use them to evaluate how candidates reduce brute-force search using hashing or counting techniques.
What data structure is used in Number Of Corner Rectangles?
The optimized solution relies on a hash table (or dictionary) that maps column pairs to the number of rows where both columns contained 1. Arrays and matrix traversal are also fundamental since the input is a binary grid.
What is the time complexity of Number Of Corner Rectangles?
The optimal solution runs in O(m * n^2) time where m is the number of rows and n is the number of columns. Each row enumerates all pairs of columns containing 1s, and a hash table tracks how many times each pair appeared before. Space complexity is O(n^2) for storing column pair counts.

Ready to solve this problem?

Practice Number Of Corner Rectangles with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays