Problem Description

You are given a 2D boolean matrix grid.

A collection of 3 elements of grid is a right triangle if one of its elements is in the same row with another element and in the same column with the third element. The 3 elements may not be next to each other.

Return an integer that is the number of right triangles that can be made with 3 elements of grid such that all of them have a value of 1.

Intuition

To solve this problem, the key is understanding how to count potential right triangles in the grid efficiently. For each 1 in the grid, consider it as the right-angled vertex of a potential right triangle. The other two vertices of this triangle must also be 1s: one located in the same row and the other in the same column.

The procedure is as follows:

1. Count 1s in Rows and Columns: Create two arrays, rows and cols, to count the number of 1s in each row and column, respectively. This helps us quickly determine potential placements for the two other vertices of a triangle for any given 1.

2. Enumerate Potential Triangles:

   • For each 1 located at position (i, j), treat it as the right angle of a triangle.
   • The number of potential horizontal edges (along row i) is given by rows[i] - 1 (excluding the current 1 itself).
   • Similarly, the number of potential vertical edges (along column j) is given by cols[j] - 1.
   • Multiply these two numbers to get the number of potential right triangles with (i, j) as the right angle.

By doing the above, you effectively count the number of right triangles that can be formed with each 1 as the right angle, accumulating the total count as you iterate through the grid.

Learn more about Math and Combinatorics patterns.

Solution Approach

The solution employs a technique based on counting and enumeration. Here's a step-by-step breakdown of the approach:

1. Initial Setup: Create two arrays, rows and cols. These arrays will be used to store the count of 1s present in each row and each column of the grid, respectively.

   • rows[i] will store the count of 1s in the i-th row.
   • cols[j] will store the count of 1s in the j-th column.

2. Counting 1s: Iterate over each element of the grid. For any 1 found at position (i, j), increment rows[i] and cols[j]. This step is crucial for fast access to the number of potential connections in rows and columns.

3. Enumerate and Calculate Right Triangles:

   • Initialize a variable ans to keep track of the total number of right triangles.
   • Again, traverse each element of the grid. When a 1 is encountered at (i, j), compute the number of triangles using it as the right angle.
   • If grid[i][j] is 1, the potential triangles using this 1 as a right angle is calculated as:
     • (rows[i] - 1) * (cols[j] - 1)
       • rows[i] - 1 represents potential elements in the same row.
       • cols[j] - 1 represents potential elements in the same column.
   • Add this value to ans.

4. Return the Result: Finally, return the value of ans.

By considering each 1 as a potential right angle for triangles and calculating possible configurations based on row and column counts, the solution efficiently counts all valid right triangles in the grid.

Example Walkthrough

Let's walk through a small example using the provided solution approach.

Consider the following 2D boolean grid:

grid = [
  [1, 0, 1],
  [0, 1, 0],
  [1, 0, 1]
]

In this grid, we want to find all possible right triangles formed by 1s.

Step 1: Initial Setup

• Create two arrays rows and cols to count the number of 1s per row and column.
  • Initialize: rows = [0, 0, 0] and cols = [0, 0, 0]

Step 2: Counting 1s

• Iterate through each element in the grid to count 1s:
  • Row 0:
    • grid[0][0] is 1, increment rows[0] and cols[0] → rows = [1, 0, 0], cols = [1, 0, 0]
    • grid[0][2] is 1, increment rows[0] and cols[2] → rows = [2, 0, 0], cols = [1, 0, 1]
  • Row 1:
    • grid[1][1] is 1, increment rows[1] and cols[1] → rows = [2, 1, 0], cols = [1, 1, 1]
  • Row 2:
    • grid[2][0] is 1, increment rows[2] and cols[0] → rows = [2, 1, 1], cols = [2, 1, 1]
    • grid[2][2] is 1, increment rows[2] and cols[2] → rows = [2, 1, 2], cols = [2, 1, 2]

Now we have the counts:

• rows = [2, 1, 2]
• cols = [2, 1, 2]

Step 3: Enumerate and Calculate Right Triangles

• Initialize ans to 0 to track the number of triangles.

• For each 1 in the grid, calculate potential right triangles:

  • grid[0][0] is 1, potential triangles = (rows[0] - 1) * (cols[0] - 1) = 1 * 1 = 1
  • grid[0][2] is 1, potential triangles = (rows[0] - 1) * (cols[2] - 1) = 1 * 1 = 1
  • grid[1][1] is 1, potential triangles = (rows[1] - 1) * (cols[1] - 1) = 0 * 0 = 0
  • grid[2][0] is 1, potential triangles = (rows[2] - 1) * (cols[0] - 1) = 1 * 1 = 1
  • grid[2][2] is 1, potential triangles = (rows[2] - 1) * (cols[2] - 1) = 1 * 1 = 1

• Sum them up: ans = 1 + 1 + 0 + 1 + 1 = 4

Step 4: Return the Result

• The total number of right triangles in the grid is 4.

Solution Implementation

Time and Space Complexity

The time complexity of the code is O(m * n) because there are two nested loops. The first set of loops calculates the sum of values in each row and each column, iterating over every element in the grid once, which is O(m * n). The second set of nested loops also goes through every grid element once, resulting in a total time complexity of O(m * n).

The space complexity is O(m + n). This is due to the storage of two lists, rows and cols, which store the sum of each row and each column, respectively. The size of rows depends on the number of rows m, and the size of cols depends on the number of columns n. Therefore, the combined space complexity is O(m + n).

Learn more about how to find time and space complexity quickly.