Count right angled triangles in a matrix having two of its sides parallel to sides of the matrix

Namachila November 19, 2025

0 0 7 minutes read

Given a binary matrix arr[][] of dimensions N * M , the task is to count the number of right-angled triangles that can be formed by joining the cells containing the value 1 such that the triangles must have any two of its sides parallel to the sides of the rectangle.

Examples:

Input: arr[][] = {{0, 1, 0}, {1, 1, 1}, {0, 1, 0}}
Output: 4
Explanation: Right-angled triangles that can be formed are (a[1][1], a[1][0], a[0][1]), (a[1][1], a[2][1], a[1][0]), (a[1][1], a[1][2], a[0][1]) and (a[1][1], a[1][2], a[2][1])

Input: arr[][] = {{1, 0, 1, 0}, {0, 1, 1, 1}, {1, 0, 1, 0}, {0, 1, 0, 1}}
Output: 16

Approach: The idea is to traverse the given grid and store the count of 1s present in each row and each column in auxiliary arrays row[] and col[] respectively. Then for each cell in the grid arr[][], if arr[i][j] is 1, then the total number of right-angled triangles formed can be calculated by (row[i] – 1)*(col[j] – 1) for each cell. Follow the steps below to solve the problem:

Initialize the arrays col[] and row[] with 0.
Traverse the given grid and visit every cell arr[i][j].
If arr[i][j] is 1, increment row[i] and col[j] by 1.
After traversing the grid, initialize a variable ans with 0.
Again traverse the whole grid and now, if arr[i][j] is 1 then update the count of the right-angled triangle by:

(row[i] – 1)*(col[j] – 1)

After traversing, print the value of ans as the total number of right-angled triangles.

Below is the implementation for the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the right-angled
// triangle in the given grid a[][]
int numberOfTriangle(
    vector<vector<int> >& a)
{
    int N = a.size();
    int M = a[0].size();
 
    // Stores the count of 1s for
    // each row[] and column[]
    int rows[N] = { 0 };
    int columns[M] = { 0 };
 
    // Find the number of 1s in
    // each of the rows[0, N - 1]
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
 
            // Increment row[i]
            if (a[i][j] == 1) {
                rows[i]++;
            }
        }
    }
 
    // Find the number of 1s in
    // each of the columns[0, N - 1]
    for (int i = 0; i < M; ++i) {
 
        for (int j = 0; j < N; ++j) {
 
            // Increment columns[i]
            if (a[j][i] == 1) {
                columns[i]++;
            }
        }
    }
 
    // Stores the count of triangles
    int answer = 0;
 
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
 
            // If current cell has value 1
            if (a[i][j] == 1) {
 
                // Update the answer
                answer += (rows[i] - 1)
                          * (columns[j] - 1);
            }
        }
 
        
    }
   // Return the count
        return answer;
}
 
 
// Driver Code
int main()
{
    // Given grid arr[][]
    vector<vector<int> > arr;
 
    arr = { { 1, 0, 1, 0 },
            { 0, 1, 1, 1 },
            { 1, 0, 1, 0 },
            { 0, 1, 0, 1 } };
 
    // Function Call
    cout << numberOfTriangle(arr);
 
    return 0;
}

Java

// Java program for the
// above approach
import java.util.*;
class GFG{
 
// Function to count the right-angled
// triangle in the given grid a[][]
static int numberOfTriangle(int[][] a)
{
  int N = a.length;
  int M = a[0].length;
 
  // Stores the count of 1s for
  // each row[] and column[]
  int []rows = new int[N];
  int []columns = new int[M];
 
  // Find the number of 1s in
  // each of the rows[0, N - 1]
  for (int i = 0; i < N; ++i) 
  {
    for (int j = 0; j < M; ++j) 
    {
      // Increment row[i]
      if (a[i][j] == 1) 
      {
        rows[i]++;
      }
    }
  }
 
  // Find the number of 1s in
  // each of the columns[0, N - 1]
  for (int i = 0; i < M; ++i) 
  {
    for (int j = 0; j < N; ++j) 
    {
      // Increment columns[i]
      if (a[j][i] == 1) 
      {
        columns[i]++;
      }
    }
  }
 
  // Stores the count 
  // of triangles
  int answer = 0;
 
  for (int i = 0; i < N; i++) 
  {
    for (int j = 0; j < M; ++j) 
    {
      // If current cell 
      // has value 1
      if (a[i][j] == 1) 
      {
        // Update the answer
        answer += (rows[i] - 1) * 
                  (columns[j] - 1);
      }
    }
  }
 
  // Return the count
  return answer;
}
 
// Driver Code
public static void main(String[] args)
{
  // Given grid arr[][]
  int [][]arr = {{1, 0, 1, 0},
                 {0, 1, 1, 1},
                 {1, 0, 1, 0},
                 {0, 1, 0, 1}};
 
  // Function Call
  System.out.print(numberOfTriangle(arr));
}
}
 
// This code is contributed by gauravrajput1

Python3

# Python3 program for the above approach
 
# Function to count the right-angled
# triangle in the given grid a[][]
def numberOfTriangle(a):
     
    N = len(a)
    M = len(a[0])
 
    # Stores the count of 1s for
    # each row[] and column[]
    rows = [0] * N
    columns = [0] * M
 
    # Find the number of 1s in
    # each of the rows[0, N - 1]
    for i in range(N):
        for j in range(M):
 
            # Increment row[i]
            if (a[i][j] == 1):
                rows[i] += 1
 
    # Find the number of 1s in
    # each of the columns[0, N - 1]
    for i in range(M):
        for j in range(N):
 
            # Increment columns[i]
            if (a[j][i] == 1):
                columns[i] += 1
 
    # Stores the count of triangles
    answer = 0
 
    for i in range(N):
        for j in range(M):
 
            # If current cell has value 1
            if (a[i][j] == 1):
 
                # Update the answer
                answer += ((rows[i] - 1) *
                      (columns[j] - 1))
 
    # Return the count
    return answer
 
# Driver Code
if __name__ == '__main__':
     
    # Given grid arr
    arr = [ [ 1, 0, 1, 0 ],
            [ 0, 1, 1, 1 ],
            [ 1, 0, 1, 0 ],
            [ 0, 1, 0, 1 ] ]
 
    # Function call
    print(numberOfTriangle(arr))
 
# This code is contributed by mohit kumar 29

C#

// C# program for the
// above approach
using System;
 
class GFG{
 
// Function to count the right-angled
// triangle in the given grid[,]a
static int numberOfTriangle(int[,] a)
{
  int N = a.GetLength(0);
  int M = a.GetLength(1);
 
  // Stores the count of 1s for
  // each []row and column[]
  int []rows = new int[N];
  int []columns = new int[M];
 
  // Find the number of 1s in
  // each of the rows[0, N - 1]
  for(int i = 0; i < N; ++i) 
  {
    for(int j = 0; j < M; ++j) 
    {
       
      // Increment row[i]
      if (a[i, j] == 1) 
      {
        rows[i]++;
      }
    }
  }
 
  // Find the number of 1s in
  // each of the columns[0, N - 1]
  for(int i = 0; i < M; ++i) 
  {
    for(int j = 0; j < N; ++j) 
    {
       
      // Increment columns[i]
      if (a[j, i] == 1) 
      {
        columns[i]++;
      }
    }
  }
 
  // Stores the count 
  // of triangles
  int answer = 0;
 
  for(int i = 0; i < N; i++) 
  {
    for(int j = 0; j < M; ++j) 
    {
       
      // If current cell 
      // has value 1
      if (a[i, j] == 1) 
      {
         
        // Update the answer
        answer += (rows[i] - 1) * 
               (columns[j] - 1);
      }
    }
  }
 
  // Return the count
  return answer;
}
 
// Driver Code
public static void Main(String[] args)
{
   
  // Given grid [,]arr
  int [,]arr = { { 1, 0, 1, 0 },
                 { 0, 1, 1, 1 },
                 { 1, 0, 1, 0 },
                 { 0, 1, 0, 1 } };
 
  // Function Call
  Console.Write(numberOfTriangle(arr));
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
 
// JavaScript program for the
// above approach
// Function to count the right-angled
// triangle in the given grid a
function numberOfTriangle(a)
{
  var N = a.length;
  var M = a[0].length;
 
  // Stores the count of 1s for
  // each row and column
  var rows = Array.from({length: N}, (_, i) => 0);
  var columns = Array.from({length: M}, (_, i) => 0);
 
  // Find the number of 1s in
  // each of the rows[0, N - 1]
  for (i = 0; i < N; ++i) 
  {
    for (j = 0; j < M; ++j) 
    {
      // Increment row[i]
      if (a[i][j] == 1) 
      {
        rows[i]++;
      }
    }
  }
 
  // Find the number of 1s in
  // each of the columns[0, N - 1]
  for (i = 0; i < M; ++i) 
  {
    for (j = 0; j < N; ++j) 
    {
      // Increment columns[i]
      if (a[j][i] == 1) 
      {
        columns[i]++;
      }
    }
  }
 
  // Stores the count 
  // of triangles
  var answer = 0;
 
  for (i = 0; i < N; i++) 
  {
    for (j = 0; j < M; ++j) 
    {
      // If current cell 
      // has value 1
      if (a[i][j] == 1) 
      {
        // Update the answer
        answer += (rows[i] - 1) * 
                  (columns[j] - 1);
      }
    }
  }
 
  // Return the count
  return answer;
}
 
// Driver Code
 
  // Given grid arr
  var arr = [[1, 0, 1, 0],
                 [0, 1, 1, 1],
                 [1, 0, 1, 0],
                 [0, 1, 0, 1]];
 
  // Function Call
  document.write(numberOfTriangle(arr));
 
// This code contributed by shikhasingrajput 
 
</script>

Output

Time Complexity: O(N*M) where NxM is the dimensions of the given grid.
Space Complexity: O(N*M)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!