Number Of Corner Rectangles - Practice Coding Problems

Number Of Corner Rectangles - Problem

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.

Input & Output

Example 1 — Basic Grid

$ Input: grid = [[1,0,0,1],[0,0,1,0],[0,0,1,0]]

› Output: 1

💡 Note: There is 1 corner rectangle with corners at (0,0), (0,3), (2,0), and (2,3). Wait, (2,0)=0, so this is wrong. Let me recalculate: only valid rectangle is formed by rows 1 and 2 at columns 2, but we need 2 common columns. Actually grid[1][2]=1, grid[2][2]=1, but we need at least 2 columns with 1's in both rows.

Example 2 — Multiple Rectangles

$ Input: grid = [[1,1,1],[1,1,1],[1,1,1]]

› Output: 9

💡 Note: Each pair of rows has 3 common columns with 1's. For each of 3 row pairs: C(3,2) = 3 rectangles. Total: 3 × 3 = 9 rectangles.

Example 3 — No Rectangles

$ Input: grid = [[1,0],[0,1]]

› Output: 0

💡 Note: Only one pair of rows (0,1), but no columns have 1's in both rows, so no rectangles can be formed.

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]

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

Binary matrix with 0's and 1's

Find Rectangles

Identify valid corner rectangles

Count Result

Total number of corner rectangles

Key Takeaway

🎯 Key Insight: Count rectangles efficiently by examining row pairs and finding columns where both rows have 1's

Asked in

G Google 15 F Facebook 12 a Amazon 8

The key insight is that a rectangle is uniquely determined by choosing any 2 rows and any 2 columns where all 4 intersections have value 1. The optimal approach iterates through all pairs of rows and counts columns where both rows have 1's - if there are k such columns, we can form C(k,2) rectangles. Time: O(m²n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All 4-Point Combinations	O(m²n²)	O(1)	Check every combination of 4 cells to see if they form a valid corner rectangle
Row Pair Optimization	O(m²n)	O(1)	For each pair of rows, count columns where both rows have 1's

Brute Force - Check All 4-Point Combinations — Algorithm Steps

Generate all combinations of 4 positions
For each combination, check if they form a rectangle
Verify all 4 corners have value 1

Visualization

Tap to expand

Step-by-Step Walkthrough

Pick Corner 1

Start with top-left corner (r1,c1)

Try All Combinations

Test all valid (r1,c2), (r2,c1), (r2,c2)

Count Valid Rectangles

Increment count when all 4 corners are 1's

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int** grid, int gridSize, int* gridColSize) {
    if (gridSize == 0 || gridColSize[0] == 0) return 0;
    
    int m = gridSize, n = gridColSize[0];
    int count = 0;
    
    // Check all possible rectangles
    for (int r1 = 0; r1 < m; r1++) {
        for (int c1 = 0; c1 < n; c1++) {
            if (grid[r1][c1] == 1) {
                for (int r2 = r1 + 1; r2 < m; r2++) {
                    for (int c2 = c1 + 1; c2 < n; c2++) {
                        if (grid[r1][c2] == 1 && 
                            grid[r2][c1] == 1 && 
                            grid[r2][c2] == 1) {
                            count++;
                        }
                    }
                }
            }
        }
    }
    
    return count;
}

int main() {
    // Simple parsing for demonstration
    int grid[3][3] = {{1,0,0},{1,1,1},{0,1,0}};
    int* gridPtr[3] = {grid[0], grid[1], grid[2]};
    int colSizes[3] = {3, 3, 3};
    
    int result = solution(gridPtr, 3, colSizes);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m²n²)

Four nested loops to check all possible rectangle corners

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

18.5K Views

Medium Frequency

~25 min Avg. Time

456 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All 4-Point Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler