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 Codeint 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 approachimport 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 Codepublic 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 Codeif __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 approachusing System;class GFG{// Function to count the right-angled// triangle in the given grid[,]astatic 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 Codepublic 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 afunction 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
16
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!