3128. Right Triangles LeetCode Solution

In this guide, you will get 3128. Right Triangles LeetCode Solution with the best time and space complexity. The solution to Right Triangles problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Right Triangles solution in C++
4. Right Triangles solution in Java
5. Right Triangles solution in Python
6. Additional Resources

Problem Statement of Right Triangles

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.

Example 1:

0
1
0

0
1
1

0
1
0

0
1
0

0
1
1

0
1
0

0
1
0

0
1
1

0
1
0

Input: grid = [[0,1,0],[0,1,1],[0,1,0]]
Output: 2
Explanation:
There are two right triangles with elements of the value 1. Notice that the blue ones do not form a right triangle because the 3 elements are in the same column.

Example 2:

1
0
0
0

0
1
0
1

1
0
0
0

Input: grid = [[1,0,0,0],[0,1,0,1],[1,0,0,0]]
Output: 0
Explanation:
There are no right triangles with elements of the value 1. Notice that the blue ones do not form a right triangle.

Example 3:

1
0
1

1
0
0

1
0
0

1
0
1

1
0
0

1
0
0

Input: grid = [[1,0,1],[1,0,0],[1,0,0]]
Output: 2
Explanation:
There are two right triangles with elements of the value 1.

Constraints:

1 <= grid.length <= 1000
1 <= grid[i].length <= 1000
0 <= grid[i][j] <= 1

Complexity Analysis

• Time Complexity: O(mn)
• Space Complexity: O(m + n)

3128. Right Triangles LeetCode Solution in C++

class Solution {
 public:
  long long numberOfRightTriangles(vector<vector<int>>& grid) {
    long count = 0;
    const int m = grid.size();
    const int n = grid[0].size();
    vector<int> rows(m);
    vector<int> cols(n);

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if (grid[i][j] == 1) {
          ++rows[i];
          ++cols[j];
        }

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if (grid[i][j] == 1)
          count += (rows[i] - 1) * (cols[j] - 1);

    return count;
  }
};
/* code provided by PROGIEZ */

3128. Right Triangles LeetCode Solution in Java

class Solution {
  public long numberOfRightTriangles(int[][] grid) {
    long count = 0;
    final int m = grid.length;
    final int n = grid[0].length;
    int[] rows = new int[m];
    int[] cols = new int[n];

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if (grid[i][j] == 1) {
          ++rows[i];
          ++cols[j];
        }

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if (grid[i][j] == 1)
          count += (rows[i] - 1) * (cols[j] - 1);

    return count;
  }
}
// code provided by PROGIEZ

3128. Right Triangles LeetCode Solution in Python

class Solution:
  def numberOfRightTriangles(self, grid: list[list[int]]) -> int:
    rows = [0] * len(grid)
    cols = [0] * len(grid[0])

    for i, row in enumerate(grid):
      for j, num in enumerate(row):
        if num == 1:
          rows[i] += 1
          cols[j] += 1

    return sum((rows[i] - 1) * (cols[j] - 1)
               for i, row in enumerate(grid)
               for j, num in enumerate(row)
               if num == 1)
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.