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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Right Triangles

Number: 3388

Difficulty: Medium

Paid? No

Companies: Mitsogo

Problem Description

Given a 2D boolean matrix grid, count the number of right triangles that can be formed using three cells with value 1. A set of three cells forms a right triangle if one cell (the vertex) shares its row with one cell and its column with another cell. Note that all three cells must contain 1 and they are not required to be adjacent.

Key Insights

  • The right triangle is defined by choosing a cell as the vertex of the right angle.
  • For a given vertex cell with value 1, one other cell in the same row and another in the same column (both with value 1) are needed.
  • Precompute the number of ones in each row and each column.
  • For each 1 at position (i, j), the number of right triangles with that cell as the right-angle vertex is (rowCount[i] - 1) * (colCount[j] - 1).
  • Sum over all cells with value 1 to obtain the answer.
  • The order of selection does not matter since every valid triangle is counted exactly once when considering the right-angle vertex.

Space and Time Complexity

Time Complexity: O(n*m) where n and m are the number of rows and columns respectively. Space Complexity: O(n + m) for storing the count of ones for each row and each column.

Solution

We solve the problem by first precomputing the number of ones in every row and every column. Then, iterate through each cell of the grid. For each cell that contains a 1, consider it as the potential right angle vertex and calculate how many triangles can be formed by multiplying the number of ones in its row (excluding the current cell) and in its column (excluding the current cell). Finally, sum these products to get the total number of valid right triangles.

Code Solutions

# Calculate the number of right triangles in the grid

def countRightTriangles(grid):
    # Number of rows and columns
    rows, cols = len(grid), len(grid[0])
    
    # Precompute count of ones for each row
    rowCount = [sum(grid[i][j] for j in range(cols)) for i in range(rows)]
    # Precompute count of ones for each column
    colCount = [sum(grid[i][j] for i in range(rows)) for j in range(cols)]
    
    result = 0
    # Iterate through each cell in the grid
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == 1:
                # Subtract 1 to exclude the current cell itself
                countRow = rowCount[i] - 1
                countCol = colCount[j] - 1
                # Multiply counts if both are positive
                result += countRow * countCol
    return result

# Example usage:
grid = [[0,1,0],[0,1,1],[0,1,0]]
print(countRightTriangles(grid))  # Expected output: 2
← Back to All Questions