Number Of Corner Rectangles - Leetcode Solution

The Number of Corner Rectangles problem on LeetCode is a problem that asks you to find the number of pairs of two 1's that form a rectangle with corners being the four 1's in the grid.

Problem Statement:

Given a grid of 0's and 1's, count the number of corner rectangles that can be found in the grid. A corner rectangle is a rectangle whose four corners are all 1's.

Example input:

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

Expected output: 1

Explanation: In the above grid, there is only one pair of 1s that form a corner rectangle as shown below:

  1 0 1
  0 1 0
  1 0 1    

We can solve this problem by using a dynamic programming approach. We can create a 2D dp array where dp[i][j] represents the number of times we have found a pair of 1's on the ith and jth row. Then, we can iterate through each pair of columns and count how many pairs of rows have 1's in both of those columns and add that to our answer.

Let's look at the pseudocode for our solution:

Pseudocode:

function countCornerRectangles(grid): m = grid.length n = grid[0].length

# Initialize our dp array to 0
dp = []
for i from 0 to m:
    dp[i] = []
    for j from 0 to n:
        dp[i][j] = 0

ans = 0

# Iterate through each row
for i from 0 to m:
    # Iterate through each pair of columns
    for j from i+1 to n:
        count = 0
        # Iterate through each row
        for k from 0 to m:
            # If we find a pair of 1's in both columns, we add to our count
            if grid[k][i] == 1 and grid[k][j] == 1:
                count += 1
                ans += dp[k][j]
        # Store the count in our dp array
        dp[i][j] = count

return ans

Let's go through the above pseudocode step by step:

• We first initialize our dp array to 0. dp[i][j] represents the number of times we have found a pair of 1's on the ith and jth row.
• We then initialize our answer variable to 0.
• We iterate through each row (i) in the grid.
• For each row, we iterate through each pair of columns (j) starting from i+1.
• We then iterate through each row (k).
• If we find a pair of 1's in both columns (i and j) on this row (k), we add 1 to our count variable.
• We then add to our answer variable the number of times we have found a pair of 1's on this row (k) and the jth column (dp[k][j]).
• Finally, we store the count variable in our dp array i.e, dp[i][j] = count.

This solution has a time complexity of O(n^3), which is not the best, but it will pass on LeetCode.

In conclusion, we have solved the Number of Corner Rectangles problem on LeetCode using a dynamic programming approach.

1