Jobs

Interviews

Discussions

Number Of Corner Rectangles

Medium

Asked by:

36 views

Topics:

Arrays

Given an m x n integer matrix grid, return the number of corner rectangles (4 sides) that have all four corners (4 nodes) being 1.

A corner rectangle is defined as having four distinct indices i1, i2, j1, and j2 such that grid[i1][j1], grid[i1][j2], grid[i2][j1], grid[i2][j2] are all 1.

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[0][0], grid[0][3], grid[3][0], grid[3][3].

Example 2:

Input: grid = [[1,1,1],[1,1,1],[1,1,1]]
Output: 9
Explanation: There are 9 corner rectangles. For example, the 4 corners grid[0][0], grid[0][1], grid[1][0], grid[1][1] form a corner 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.

Try coding it in LeetCode

Number Of Corner Rectangles

Medium

Asked by:

36 views

Topics:

Arrays

Given an m x n integer matrix grid, return the number of corner rectangles (4 sides) that have all four corners (4 nodes) being 1.

A corner rectangle is defined as having four distinct indices i1, i2, j1, and j2 such that grid[i1][j1], grid[i1][j2], grid[i2][j1], grid[i2][j2] are all 1.

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[0][0], grid[0][3], grid[3][0], grid[3][3].

Example 2:

Input: grid = [[1,1,1],[1,1,1],[1,1,1]]
Output: 9
Explanation: There are 9 corner rectangles. For example, the 4 corners grid[0][0], grid[0][1], grid[1][0], grid[1][1] form a corner 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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the matrix, and what is the maximum possible size of the matrix (number of rows and columns)?
What values can the elements of the matrix take (e.g., only 0 and 1, or a broader range of integers)?
If there are no corner rectangles in the input matrix, what value should I return?
Does the order of rows and columns matter when counting corner rectangles (i.e., is a rectangle formed by (row1, col1), (row1, col2), (row2, col1), (row2, col2) considered the same as one formed by (row2, col2), (row2, col1), (row1, col2), (row1, col1))?
Is the input matrix guaranteed to be rectangular (i.e., all rows have the same number of columns)?

Brute Force Solution

Approach

The brute force strategy for counting corner rectangles involves checking every possible combination of points in the given grid. We will consider all possible sets of four points and see if they form a rectangle with sides parallel to the axes. If they do, we increment our count.

Here's how the algorithm would work step-by-step:

Pick the first point from the grid.
Pick a second point from the grid.
Pick a third point from the grid.
Pick a fourth point from the grid.
Check if these four points form a rectangle. To be a rectangle, the points must form two pairs, where each pair has the same 'horizontal' position or 'vertical' position, and the horizontal positions in one pair are different to the horizontal positions in the other pair, and similarly for the vertical positions.
If they form a rectangle, add one to the rectangle count.
Repeat this process for every possible combination of four points from the grid.
The final count is the total number of rectangles found.

Code Implementation

def number_of_corner_rectangles_brute_force(grid):
    rectangle_count = 0
    grid_height = len(grid)
    grid_width = len(grid[0]) if grid_height > 0 else 0

    # Iterate through all possible combinations of four points
    for first_row in range(grid_height):
        for first_col in range(grid_width):
            for second_row in range(grid_height):
                for second_col in range(grid_width):
                    for third_row in range(grid_height):
                        for third_col in range(grid_width):
                            for fourth_row in range(grid_height):
                                for fourth_col in range(grid_width):

                                    # Check if all points are actually '1's
                                    if (grid[first_row][first_col] == 1 and
                                            grid[second_row][second_col] == 1 and
                                            grid[third_row][third_col] == 1 and
                                            grid[fourth_row][fourth_col] == 1):

                                        # Checks if it forms a rectangle
                                        if (first_row == second_row and third_row == fourth_row and
                                                first_col == third_col and second_col == fourth_col and
                                                first_row != third_row and first_col != second_col):
                                            rectangle_count += 1

    return rectangle_count

Big(O) Analysis

Time Complexity

O(m^4) – Given an m x n grid, this brute force approach iterates through all possible combinations of four points. The algorithm selects the first point, then the second, then the third, and finally the fourth. This leads to four nested loops, each potentially iterating through all m*n points in the grid. Thus, the time complexity is proportional to m * m * m * m, which simplifies to O(m^4), where m is the number of points to select from.

Space Complexity

O(1) – The brute force solution iterates through all possible combinations of four points within the grid but does not use any auxiliary data structures that scale with the input size. It only uses a few integer variables to store the indices of the chosen points and a counter for the rectangles. Therefore, the space complexity is constant, regardless of the grid's dimensions, and can be expressed as O(1).

Optimal Solution

Approach

The problem asks us to find rectangles formed by 1s in a grid. Instead of checking every possible rectangle, the optimal approach focuses on identifying pairs of rows that could potentially form the top and bottom of a rectangle. By efficiently counting these pairs, we avoid unnecessary calculations.

Here's how the algorithm would work step-by-step:

Go through each row in the grid.
For each row, compare it to every row below it.
When comparing two rows, count how many columns have a '1' in both rows.
If you find a pair of rows with at least two columns where both rows have '1's, you've found a potential rectangle.
The number of ways to choose two columns from the shared '1's between the two rows tells you how many rectangles those two rows contribute.
For each pair of rows, the number of rectangles formed will be determined by calculating combinations (specifically n choose 2, where n is the number of shared columns containing '1's).
Add up the number of rectangles from each pair of rows. This gives you the total number of rectangles in the grid.

Code Implementation

def number_of_corner_rectangles(grid):
    number_of_rows = len(grid)
    number_of_columns = len(grid[0]) if number_of_rows > 0 else 0
    rectangle_count = 0

    for row_index_one in range(number_of_rows):
        for row_index_two in range(row_index_one + 1, number_of_rows):
            # Count common 1s to see potential rectangles
            common_ones_count = 0

            for column_index in range(number_of_columns):
                if grid[row_index_one][column_index] == 1 and grid[row_index_two][column_index] == 1:
                    common_ones_count += 1

            # Need at least 2 common 1s to form a rectangle
            if common_ones_count >= 2:
                # Calculate combinations of column pairs
                rectangle_count += common_ones_count * (common_ones_count - 1) // 2

    return rectangle_count

Big(O) Analysis

Time Complexity

O(m²n) – The algorithm iterates through all possible pairs of rows in the grid. Given 'm' rows, this involves approximately m * m/2 comparisons. For each pair of rows, it iterates through all 'n' columns to count the shared '1's. Therefore, the time complexity is dominated by the nested row loop (m squared) and the column checking loop (n), resulting in a time complexity of O(m²n).

Space Complexity

O(1) – The provided solution iterates through the rows of the grid and compares pairs of rows, calculating the number of columns with '1' in both. It only uses a few integer variables to store row indices and the count of shared '1's. These variables consume a constant amount of space, irrespective of the grid's dimensions (number of rows and columns). Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty input matrix	Return 0 immediately as there are no possible rectangles.
Matrix with fewer than 2 rows or 2 columns	Return 0 immediately as a rectangle requires at least 2 rows and 2 columns.
Matrix containing non-binary values (not 0 or 1)	The solution should explicitly check if the matrix contains only 0s and 1s and can either throw an exception or treat other values as 0.
All values in the matrix are 0	The solution should return 0, as no corner rectangles can be formed.
All values in the matrix are 1	The solution should correctly calculate the number of corner rectangles, which depends on the dimensions of the matrix and can be computed combinatorially (n choose 2) * (m choose 2).
Large matrix dimensions leading to integer overflow when calculating the number of rectangles	Use 64-bit integers to prevent integer overflow during calculation.
Matrix where only one row or column contains 1s	The solution should return 0, as corner rectangles require at least two rows and two columns with 1s.
Input matrix is a square matrix	The solution logic should work correctly without any assumptions about the matrix's dimensions.

Null or empty input matrix

How to Handle:

Return 0 immediately as there are no possible rectangles.

Matrix with fewer than 2 rows or 2 columns

How to Handle:

Return 0 immediately as a rectangle requires at least 2 rows and 2 columns.

Matrix containing non-binary values (not 0 or 1)

How to Handle:

The solution should explicitly check if the matrix contains only 0s and 1s and can either throw an exception or treat other values as 0.

All values in the matrix are 0

How to Handle:

The solution should return 0, as no corner rectangles can be formed.

All values in the matrix are 1

How to Handle:

The solution should correctly calculate the number of corner rectangles, which depends on the dimensions of the matrix and can be computed combinatorially (n choose 2) * (m choose 2).

Large matrix dimensions leading to integer overflow when calculating the number of rectangles

How to Handle:

Use 64-bit integers to prevent integer overflow during calculation.

Matrix where only one row or column contains 1s

How to Handle:

The solution should return 0, as corner rectangles require at least two rows and two columns with 1s.

Input matrix is a square matrix

How to Handle:

The solution logic should work correctly without any assumptions about the matrix's dimensions.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the matrix, and what is the maximum possible size of the matrix (number of rows and columns)?
What values can the elements of the matrix take (e.g., only 0 and 1, or a broader range of integers)?
If there are no corner rectangles in the input matrix, what value should I return?
Does the order of rows and columns matter when counting corner rectangles (i.e., is a rectangle formed by (row1, col1), (row1, col2), (row2, col1), (row2, col2) considered the same as one formed by (row2, col2), (row2, col1), (row1, col2), (row1, col1))?
Is the input matrix guaranteed to be rectangular (i.e., all rows have the same number of columns)?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Pick the first point from the grid.
Pick a second point from the grid.
Pick a third point from the grid.
Pick a fourth point from the grid.
Check if these four points form a rectangle. To be a rectangle, the points must form two pairs, where each pair has the same 'horizontal' position or 'vertical' position, and the horizontal positions in one pair are different to the horizontal positions in the other pair, and similarly for the vertical positions.
If they form a rectangle, add one to the rectangle count.
Repeat this process for every possible combination of four points from the grid.
The final count is the total number of rectangles found.

Code Implementation

def number_of_corner_rectangles_brute_force(grid):
    rectangle_count = 0
    grid_height = len(grid)
    grid_width = len(grid[0]) if grid_height > 0 else 0

    # Iterate through all possible combinations of four points
    for first_row in range(grid_height):
        for first_col in range(grid_width):
            for second_row in range(grid_height):
                for second_col in range(grid_width):
                    for third_row in range(grid_height):
                        for third_col in range(grid_width):
                            for fourth_row in range(grid_height):
                                for fourth_col in range(grid_width):

                                    # Check if all points are actually '1's
                                    if (grid[first_row][first_col] == 1 and
                                            grid[second_row][second_col] == 1 and
                                            grid[third_row][third_col] == 1 and
                                            grid[fourth_row][fourth_col] == 1):

                                        # Checks if it forms a rectangle
                                        if (first_row == second_row and third_row == fourth_row and
                                                first_col == third_col and second_col == fourth_col and
                                                first_row != third_row and first_col != second_col):
                                            rectangle_count += 1

    return rectangle_count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Go through each row in the grid.
For each row, compare it to every row below it.
When comparing two rows, count how many columns have a '1' in both rows.
If you find a pair of rows with at least two columns where both rows have '1's, you've found a potential rectangle.
The number of ways to choose two columns from the shared '1's between the two rows tells you how many rectangles those two rows contribute.
For each pair of rows, the number of rectangles formed will be determined by calculating combinations (specifically n choose 2, where n is the number of shared columns containing '1's).
Add up the number of rectangles from each pair of rows. This gives you the total number of rectangles in the grid.

Code Implementation

def number_of_corner_rectangles(grid):
    number_of_rows = len(grid)
    number_of_columns = len(grid[0]) if number_of_rows > 0 else 0
    rectangle_count = 0

    for row_index_one in range(number_of_rows):
        for row_index_two in range(row_index_one + 1, number_of_rows):
            # Count common 1s to see potential rectangles
            common_ones_count = 0

            for column_index in range(number_of_columns):
                if grid[row_index_one][column_index] == 1 and grid[row_index_two][column_index] == 1:
                    common_ones_count += 1

            # Need at least 2 common 1s to form a rectangle
            if common_ones_count >= 2:
                # Calculate combinations of column pairs
                rectangle_count += common_ones_count * (common_ones_count - 1) // 2

    return rectangle_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input matrix	Return 0 immediately as there are no possible rectangles.
Matrix with fewer than 2 rows or 2 columns	Return 0 immediately as a rectangle requires at least 2 rows and 2 columns.
Matrix containing non-binary values (not 0 or 1)	The solution should explicitly check if the matrix contains only 0s and 1s and can either throw an exception or treat other values as 0.
All values in the matrix are 0	The solution should return 0, as no corner rectangles can be formed.
All values in the matrix are 1	The solution should correctly calculate the number of corner rectangles, which depends on the dimensions of the matrix and can be computed combinatorially (n choose 2) * (m choose 2).
Large matrix dimensions leading to integer overflow when calculating the number of rectangles	Use 64-bit integers to prevent integer overflow during calculation.
Matrix where only one row or column contains 1s	The solution should return 0, as corner rectangles require at least two rows and two columns with 1s.
Input matrix is a square matrix	The solution logic should work correctly without any assumptions about the matrix's dimensions.

Null or empty input matrix

How to Handle:

Return 0 immediately as there are no possible rectangles.

Matrix with fewer than 2 rows or 2 columns

How to Handle:

Return 0 immediately as a rectangle requires at least 2 rows and 2 columns.

Matrix containing non-binary values (not 0 or 1)

How to Handle:

The solution should explicitly check if the matrix contains only 0s and 1s and can either throw an exception or treat other values as 0.

All values in the matrix are 0

How to Handle:

The solution should return 0, as no corner rectangles can be formed.

All values in the matrix are 1

How to Handle:

The solution should correctly calculate the number of corner rectangles, which depends on the dimensions of the matrix and can be computed combinatorially (n choose 2) * (m choose 2).

Large matrix dimensions leading to integer overflow when calculating the number of rectangles

How to Handle:

Use 64-bit integers to prevent integer overflow during calculation.

Matrix where only one row or column contains 1s

How to Handle:

The solution should return 0, as corner rectangles require at least two rows and two columns with 1s.

Input matrix is a square matrix

How to Handle:

The solution logic should work correctly without any assumptions about the matrix's dimensions.