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.

Description Hints 1 Solution Video 6:09

750. Number Of Corner Rectangles

Medium67.8% acceptance1 companyPremium elsewhere, free here

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].

Asked at 1 company

Topics

Hints open one at a time

Hint 1

For each pair of 1s in the new row (say at `new_row[i]` and `new_row[j]`), we could create more rectangles where that pair forms the base. The number of new rectangles is the number of times some previous row had `row[i] = row[j] = 1`.

6:09

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[[1,0,0,1,0],[0,0,1,0,1],[0,0,0,1,0],[1,0,1,0,1]]

Input

[[1,1,1],[1,1,1],[1,1,1]]

Input

[[1,1,1,1]]

Your code is saved on this device.Solution