We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Right Triangles

Difficulty: Medium

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.

Key Insights

  • A right triangle can be formed from three elements: two in the same row and one in the same column.
  • For every pair of elements in the same row with value 1, we need to count how many elements of value 1 exist in the columns of these elements.
  • We can use combinatorial counting to determine the number of triangles formed by choosing pairs of 1s in the same row.

Space and Time Complexity

Time Complexity: O(n * m) where n is the number of rows and m is the number of columns in the grid.
Space Complexity: O(m) to keep track of the count of 1s in each column.

Solution

To solve the problem, we can follow these steps:

  1. Iterate through each row of the grid.
  2. For each row, identify all the columns that contain a value of 1.
  3. For every pair of columns containing a 1, we calculate the number of 1s in the columns of those two columns to determine how many right triangles can be formed.
  4. Use combinatorial counting to sum up the valid triangles.

The main data structure used here is an array to keep track of the count of 1s in each column.

Code Solutions

def countRightTriangles(grid):
    n = len(grid)
    m = len(grid[0])
    
    # Count of 1s in each column
    column_count = [0] * m
    for j in range(m):
        for i in range(n):
            if grid[i][j] == 1:
                column_count[j] += 1

    total_triangles = 0

    # Iterate through each row
    for i in range(n):
        ones_in_row = []
        for j in range(m):
            if grid[i][j] == 1:
                ones_in_row.append(j)
        
        # Count triangles for each pair of columns with 1
        k = len(ones_in_row)
        for x in range(k):
            for y in range(x + 1, k):
                total_triangles += column_count[ones_in_row[x]] * column_count[ones_in_row[y]]

    return total_triangles
← Back to All Questions