Leetcode 750. Number Of Corner Rectangles

Problem Explanation:

In this problem, we have a grid consisting of entries only 0 or 1. The task is to find out the total number of axis-aligned rectangles that can be formed using the '1's in the grid, where only the corners need to be '1'. Please note, the all four '1's used should be distinct.

For example, consider the below grid:

1[[1, 0, 0, 1, 0],
2 [0, 0, 1, 0, 1],
3 [0, 0, 0, 1, 0],
4 [1, 0, 1, 0, 1]]

Here, the only corner rectangle that can be formed, has the corners grid[1][2], grid[1][4], grid[3][2], grid[3][4].

This problem can be solved using multiple consecutive row pairs. For each pair of rows, we iterate over each element in the rows. If an element of value 1 is found in both rows, increment the count. Finally, return the total pairs of those '1's as those can form a rectangle with any other pair.

Solution Details:

To find the total rectangle count, first we iterate through all row pairs. For each row pair, we again iterate through each element in a row, checking if the entry in each row is 1. If we find an entry where the same element in both rows is 1, we increment a count, because we know that those two points can form the corners of a rectangle (along with another pair). Once we find all such points for a row pair, we know that they can form count * (count - 1) / 2 rectangles amongst themselves - this is derived from the formula for combinations.

Let's take the example of the following grid to illustrate this:

1[[1, 0, 0, 1, 0],
2 [0, 0, 1, 0, 1],
3 [0, 0, 0, 1, 0],
4 [1, 0, 1, 0, 1]]

• Start with first row and compare with all subsequent rows one by one. Iterating through the first row C(0,2) = 0 so add 0 to ans. Iterating through the second row C(0,2) = 0 so add 0 to ans. Iterating through the third row C(1,2) = 1 so add 1 + 0 + 0 = 1 to ans.
• Similarly, proceed for the rest of the rows.
• Finally, return ans which will be the total rectangles formed.

Solutions:

C++ Solution:

1
2cpp
3class Solution {
4 public:
5  int countCornerRectangles(vector<vector<int>>& grid) {
6    int ans = 0;
7
8    for (int row1 = 0; row1 < grid.size() - 1; ++row1)
9      for (int row2 = row1 + 1; row2 < grid.size(); ++row2) {
10        int count = 0;
11        for (int j = 0; j < grid[0].size(); ++j)
12          if (grid[row1][j] && grid[row2][j])
13            ++count;
14        ans += count * (count - 1) / 2; // update ans for current pair
15      }
16
17    return ans;
18  }
19};

Python Solution:

1
2python
3class Solution:
4    def countCornerRectangles(self, grid):
5        ans = 0
6        for row1 in range(len(grid) - 1):
7            for row2 in range(row1 + 1, len(grid)):
8                count = sum(1 for col in range(len(grid[0])) if grid[row1][col] and grid[row2][col])
9                ans += count * (count - 1) // 2
10        return ans

Java Solution:

1
2java
3public class Solution {
4    public int countCornerRectangles(int[][] grid) {
5        int ans = 0;
6
7        for (int row1 = 0; row1 < grid.length - 1; ++row1)
8            for (int row2 = row1 + 1; row2 < grid.length; ++row2) {
9                int count = 0;
10                for (int j = 0; j < grid[0].length; ++j)
11                    if (grid[row1][j] == 1 && grid[row2][j] == 1)
12                        ++count;
13                ans += count * (count - 1) / 2; 
14            }
15
16        return ans;
17    }
18}

JavaScript Solution:

1
2js
3var countCornerRectangles = function(grid) {
4    let ans = 0;
5
6    for (let row1 = 0; row1 < grid.length - 1; ++row1)
7        for (let row2 = row1 + 1; row2 < grid.length; ++row2) {
8            let count = 0;
9            for (let j = 0; j < grid[0].length; ++j)
10                if (grid[row1][j] == 1 && grid[row2][j] == 1)
11                    ++count;
12            ans += count * (count - 1) / 2; 
13        }
14
15    return ans;
16};

C# Solution:

1
2csharp
3public class Solution {
4    public int CountCornerRectangles(int[][] grid) {
5        int ans = 0;
6
7        for (int row1 = 0; row1 < grid.Length - 1; ++row1)
8            for (int row2 = row1 + 1; row2 < grid.Length; ++row2) {
9                int count = 0;
10                for (int j = 0; j < grid[0].Length; ++j)
11                    if (grid[row1][j] == 1 && grid[row2][j] == 1)
12                        ++count;
13                ans += count * (count - 1) / 2;
14            }
15
16        return ans;
17    }
18}

With these examples and explanations, we believe it should be easy to understand the problem and it's solution.In conclusion, this problem highlights the necessity to break down complex problems into simpler tasks during problem-solving. By first identifying row pairs, then scanning each row for '1's, and finally calculating the number of rectangles that can be formed from multiple pairs, we were able to find a solution for a seemingly complicated problem using basic mathematics and simple iteration algorithm.

Although the provided solutions used multiple languages such as C++, Python, Java, JavaScript, and C#, the underlying logic remained uniform throughout - demonstrating that the tools used to solve a problem can vary widely, but the general approach and strategic thinking remain the same.

Finally, this problem underscored the fact that many problems may appear difficult at first glance but taking a systematic approach to breaking them down into smaller components can make them much more manageable. While these coding solutions are detailed and concise, the key to mastering them is understanding the fundamental concepts and reasoning behind each step.

This logic and approach demonstrated here can be universally applied to a range of programming languages beyond the examples provided, further reinforcing the principles of effective problem decomposition and stepwise refinement in algorithm design.

So, whether you're implementing this solution in Python, C++, Java, JavaScript or C#, the underlying principles remain the same. Stay confident, continue learning, and happy coding!