750. Number Of Corner Rectangles
Problem Description
The given LeetCode problem asks us to count the number of distinct "corner rectangles" in a 2D grid. A "corner rectangle" is defined by four '1's that are placed in the grid in such a way that they form the corners of an axis-aligned rectangle. Importantly, the interior of this rectangle can contain any mix of '0's and '1's; the only requirement is that the four corners are '1's. The grid, grid
, is composed entirely of '0's and '1's, and its dimensions are m x n
where m
is the number of rows and n
is the number of columns. The task is to return the total count of such distinct corner rectangles.
Intuition
To solve this problem, we leverage the fact that a rectangle is defined by its two opposite corners. Here, we iterate over all potential corner pairs in the grid and try to determine if these pairs can form the upper two or lower two corners of a rectangle. We do this by checking if we picked two '1's in the same row. For each pair of '1's in the row, we check to see if the same pair of columns also have '1's in another row, forming a rectangle. To efficiently track this, we employ a counting strategy that uses a dictionary to remember how many times we've seen each pair of '1's in the same row.
Whenever we encounter a pair of '1's in the same row, we check the dictionary to see if this pair has been seen before. If it has, then for each previous occurrence, there is a distinct rectangle. Therefore, the count of rectangles is incremented by the number of times the pair has been seen before. Afterwards, we increment the counter for that pair, indicating that we've found another potential set of top corners for future rectangles.
The algorithm iterates over all rows and, within each row, all pairs of '1's. By using a counter dictionary that keeps track of pairs of indices where '1's are found, it ensures that the process of finding rectangular corners is efficient, avoiding checking every possible rectangle explicitly, which would be computationally expensive especially for large grids.
Learn more about Math and Dynamic Programming patterns.
Solution Approach
The solution employs a simple yet efficient approach using a hash table to keep track of the count of '1' pairs encountered so far. Here's a step-by-step walkthrough of how the code works:
-
Initialize Variables:
- Initialize a variable
ans
to 0, which will hold the final count of corner rectangles. - Create a
Counter
object namedcnt
from the Pythoncollections
module. This counter will map each pair of column indices(i, j)
to the number of times that pair has been observed ingrid
with '1's.
- Initialize a variable
-
Iterate Over the Grid:
- The first
for
loop iterates through each row of the grid.
- The first
-
Find Pairs of '1's in the Same Row:
- Within each row, use a nested
for
loop withenumerate
to get both the indexi
and valuec1
at that index. - If
c1
is '1', it means we have a potential top/left corner of a rectangle.
- Within each row, use a nested
-
Check for Potential Top/Right Corners:
- Another nested
for
loop is used to check to the right of the current '1' for another '1' at indexj
, forming a pair of top corners(i, j)
of a potential rectangle.
- Another nested
-
Count and Update Rectangles:
- For each such pair
(i, j)
, if they can form the top two corners of a rectangle, we incrementans
bycnt[(i, j)]
since each count represents another row where a rectangle with these top corners can be completed. - After counting the rectangles for
(i, j)
, updatecnt[(i, j)]
by incrementing by 1 which signifies that we have found another pair of '1's that can form the top corners of potential future rectangles.
- For each such pair
-
Return the Answer:
- After all rows and valid pairs are processed, return
ans
as the total count of corner rectangles found in the grid.
- After all rows and valid pairs are processed, return
This solution utilizes a smart counting approach to avoid checking each potential rectangle directly, which drastically reduces the time complexity. The main algorithmic techniques include iterating over array elements and using hash-based counters for an elegant and efficient solution. By checking only rows for pairs of '1's and then counting and updating the number of potential rectangles as more pairs are found, the solution effectively captures all corner rectangles without unnecessary computations.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate how the solution approach works. Consider the following grid
which is a 4x3 matrix containing both 0's
and 1's
.
grid = [ [1, 0, 1], [1, 1, 1], [1, 0, 0], [1, 0, 1] ]
-
Initialize Variables:
ans
starts at 0.cnt
is an emptyCounter
object.
-
Iterate Over the Grid:
- Start with the first row
[1, 0, 1]
.
- Start with the first row
-
Find Pairs of '1's in the Same Row:
- Identify two '1's in the row at index
i = 0
andj = 2
.
- Identify two '1's in the row at index
-
Check for Potential Top/Right Corners:
- These are the potential top corners of multiple rectangles.
-
Count and Update Rectangles:
- Since
cnt[(0, 2)]
is not incnt
,ans
remains 0, butcnt[(0, 2)]
becomes 1.
- Since
Repeat steps 2-5 for remaining rows:
- Second row
[1, 1, 1]
has '1's at indices0
,1
, and2
. - Pairs
(0, 1)
,(0, 2)
, and(1, 2)
each have the potential to form corner rectangles. cnt[(0, 1)]
becomes 1,cnt[(0, 2)]
is incremented to 2 (since we already have one from the first row), andcnt[(1, 2)]
becomes 1.
As we process this row, ans
gets updated because cnt[(0, 2)]
was already 1 (one rectangle can now be formed with the previous row as the bottom corners).
Now, ans
is incremented by 1.
Continuing on to the third and fourth rows, you'll do the same pair checks and counts, but no updates to ans
occur until the fourth row.
- In the fourth row
[1, 0, 1]
, the same pair(0, 2)
is found as in the first row, meaning that for every previous occurrence of this pair (which is two times so far), a rectangle can be completed, soans
gets incremented by 2.
Finally, after iterating through all rows, we conclude with:
ans
= 3 (total count of corner rectangles found in the grid).
This example illuminated how only pairs of '1's in the same rows are used to determine the possibility of forming rectangles, and with each row's pairs, we effectively keep a running count of potential rectangles without the need for checking all possible rectangles directly. The Counter
efficiently handles this incrementation and checking for previously seen pairs.
Solution Implementation
1from collections import Counter
2
3class Solution:
4 def countCornerRectangles(self, grid: List[List[int]]) -> int:
5 rectangle_count = 0 # This will hold the final count of corner rectangles
6 pair_counter = Counter() # Counter to track pairs of columns that have a 1 at the same row
7 num_cols = len(grid[0]) # The number of columns in the grid
8
9 # Iterate through each row in the grid
10 for row in grid:
11 # Enumerate over the row to get both column index and value
12 for col_index_first, cell_first in enumerate(row):
13 # Only process if the cell at the current column has a 1
14 if cell_first:
15 # Consider pairs of columns, starting from the current one
16 for col_index_second in range(col_index_first + 1, num_cols):
17 # Check if the second column also has a 1 at the current row
18 if row[col_index_second]:
19 # If both columns have a 1 at the current row, this forms a potential rectangle corner
20 # Increase the count for this column pair as we found another rectangle corner
21 rectangle_count += pair_counter[(col_index_first, col_index_second)]
22 # Update the counter for the current pair, adding one more occurrence
23 pair_counter[(col_index_first, col_index_second)] += 1
24
25 # Return the total count of rectangles found
26 return rectangle_count
27```
28
29Changes and comments explanation:
30
311. `rectangle_count`: Renamed `ans` to `rectangle_count` to better describe what the variable is used for.
322. `pair_counter`: Renamed `cnt` to `pair_counter` which is a Counter object to keep track of pairs of columns that make the corners of rectangles.
333. `num_cols`: Introduced this variable as a clearer name for the number of columns in the grid (`n` in the original code).
344. `col_index_first` and `cell_first`: Renamed `i` and `c1` for clarity in the enumeration of the first column index and cell value.
355. Comments: Added explanatory comments throughout the code to provide clarity on each step of the process.
366. Standard imports: Included the import statement for the 'Counter' class from the 'collections' module explicitly, which allows for counting occurrences of elements in a hashable object.
37
38Make sure to replace `List` by the correct import statement from 'typing' at the beginning of the file:
39
40```python
41from typing import List
42
1import java.util.HashMap;
2import java.util.List;
3import java.util.Map;
4
5class Solution {
6 public int countCornerRectangles(int[][] grid) {
7 // Number of columns in the grid.
8 int numCols = grid[0].length;
9 // This will store the final count of corner rectangles.
10 int cornerRectanglesCount = 0;
11 // A map to store the counts of 1's pairs across rows.
12 Map<List<Integer>, Integer> pairsCount = new HashMap<>();
13
14 // Loop through each row in the grid.
15 for (int[] row : grid) {
16 // Iterate over every possible pair of columns within this row
17 for (int leftCol = 0; leftCol < numCols; ++leftCol) {
18 // If the current cell is a 1, explore further for a rectangle.
19 if (row[leftCol] == 1) {
20 for (int rightCol = leftCol + 1; rightCol < numCols; ++rightCol) {
21 // Only if the paired cell is also a 1, do we consider it.
22 if (row[rightCol] == 1) {
23 // Create a pair to check in our current map.
24 List<Integer> pair = List.of(leftCol, rightCol);
25 // Increment the count of found rectangles with these 1's as the top corners.
26 cornerRectanglesCount += pairsCount.getOrDefault(pair, 0);
27 // Increment the count of this pair in our map.
28 pairsCount.merge(pair, 1, Integer::sum);
29 }
30 }
31 }
32 }
33 }
34 // The result is the total count of rectangles found.
35 return cornerRectanglesCount;
36 }
37}
38
1#include <vector>
2#include <map>
3using namespace std;
4
5class Solution {
6public:
7 int countCornerRectangles(vector<vector<int>>& grid) {
8 // n represents the number of columns in the grid
9 int num_columns = grid[0].size();
10 // Initialize the answer to 0
11 int answer = 0;
12 // Define a map to store the count of pairs of columns that form the vertical sides of potential rectangles
13 map<pair<int, int>, int> column_pairs_count;
14
15 // Iterate through each row of the grid
16 for (const auto& row : grid) {
17 // Check each pair of columns within the row
18 for (int i = 0; i < num_columns; ++i) {
19 // If the current cell contains a 1, search for a potential second column to form a rectangle
20 if (row[i]) {
21 for (int j = i + 1; j < num_columns; ++j) {
22 // If we find a pair of 1s, this could form the corner of a rectangle
23 if (row[j]) {
24 // Increase the answer by the count of rectangles that can be formed using this column pair
25 answer += column_pairs_count[{i, j}];
26 // Increment the count for this column pair
27 ++column_pairs_count[{i, j}];
28 }
29 }
30 }
31 }
32 }
33 // Return the total count of corner rectangles
34 return answer;
35 }
36};
37
1function countCornerRectangles(grid: number[][]): number {
2 // Initialization of n to represent the number of columns
3 const columnsCount = grid[0].length;
4 // Initialization of the answer variable to count corner rectangles
5 let cornerRectanglesCount = 0;
6 // Using a Map to keep track of the count of pairs of cells with value 1
7 const pairCounts: Map<number, number> = new Map();
8
9 // Looping through each row in the grid
10 for (const row of grid) {
11 // Looping through each cell in the row
12 for (let i = 0; i < columnsCount; ++i) {
13 // Check if the current cell has value 1
14 if (row[i] === 1) {
15 // Nested loop to find another cell with value 1 in the same row
16 for (let j = i + 1; j < columnsCount; ++j) {
17 if (row[j] === 1) {
18 // Creating a unique key for the pair of cells
19 const pairKey = i * 200 + j;
20 // Increment count for the current pair of cells
21 cornerRectanglesCount += pairCounts.get(pairKey) ?? 0;
22 // Update the pair count map with the new count
23 pairCounts.set(pairKey, (pairCounts.get(pairKey) ?? 0) + 1);
24 }
25 }
26 }
27 }
28 }
29
30 // Returning the total count of corner rectangles found in the grid
31 return cornerRectanglesCount;
32}
33
Time and Space Complexity
Time Complexity
The given code's time complexity primarily comes from the nested loops that it uses to iterate over each pair of columns for each row.
- The first loop (
for row in grid
) goes through each row in the grid, which occursm
times wherem
is the number of rows. - Inside this loop, the second loop (
for i, c1 in enumerate(row)
) iterates over each element in the row, which occursn
times wheren
is the number of columns. - The innermost loop (
for j in range(i + 1, n)
) iterates from the current columni
to the last column, with the average number of iterations being roughlyn/2
since it's a triangular iteration overall.
Considering the iterations of the third nested loop, the number of column pairs (i, j)
that will be considered for each row follows the pattern of a combination of selecting two out of n
columns or nC2
.
Therefore, the time complexity is O(m * nC2)
or O(m * n * (n - 1) / 2)
, which simplifies to O(m * n^2)
.
Space Complexity
The space complexity is determined by the storage used by the cnt
Counter, which keeps track of the frequency of each pair of columns that have been seen with '1'
at both the i
th and j
th positions.
- In the worst case scenario, the
cnt
Counter would have an entry for every possible pair of columns. As there aren
columns, the number of column pairs would be the samenC2
we calculated before, orn * (n - 1) / 2
pairs. - Therefore, the space complexity for the
cnt
Counter isO(n^2)
.
Thus, the overall space complexity is O(n^2)
since the Counter's size is the dominant term, and this space is additional to the input (grid
) since the grid
itself is not being modified.
Learn more about how to find time and space complexity quickly using problem constraints.
A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".
What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!