Valid Triangle Number

Difficulty Level Medium
Frequently asked in Bloomberg Robinhood
ArrayViews 1204

Problem

In the Valid Triangle Number problem, we have given an array of non-negative integers. Find the number of triplets that can form a triangle. If we consider the numbers in the array as side lengths of the triangle.

Example

Input

[ 2, 2, 3, 4 ]

Output

3

Explanation

We can form three triplets that can form a triangle.

triplets are :

  1. 2,3,4 (using the first 2)
  2. 2,3,4 (using the second 2)
  3. 2,2,3

Brute force approach

A triplet can form a triangle if and only if it satisfies the condition a+b>c. It means that sum of two sides of a triangle must be greater than the third side.

The brute force approach is very simple and easy. We will check for each triplet if they satisfy the condition to form a triangle. We will also maintain a variable to keep track of the count of triplets that can form a triangle. So when we encounter a triplet that can form a triangle we will increase the count. In this way, after checking for all the possible triplets we will have the total number of triplets that can be formed.

Implementation of  Valid Triangle Number

C++ code for Valid Triangle Number

// C++ code to count the number of 
// possible triangles using brute 
// force approach 
#include <bits/stdc++.h> 
using namespace std; 

// Function to count all possible 
// triangles with arr[] elements 
int findNumberOfTriangles(int arr[], int n) 
{ 
  // Count of triangles 
  int count = 0; 

  // The three loops select three 
  // different values from array 
  for (int i = 0; i < n; i++) { 
    for (int j = i + 1; j < n; j++) { 

      // The innermost loop checks for 
      // the triangle property 
      for (int k = j + 1; k < n; k++) 

        // Sum of two sides is greater 
        // than the third 
        if ( 
          arr[i] + arr[j] > arr[k] 
          && arr[i] + arr[k] > arr[j] 
          && arr[k] + arr[j] > arr[i]) 
          count++; 
    } 
  } 
  return count; 
} 

// Driver code 
int main() 
{ 
  int arr[] = { 10, 21, 22, 100, 101, 200, 300 }; 
  int size = sizeof(arr) / sizeof(arr[0]); 

  cout 
    << "Total number of triangles possible is "
    << findNumberOfTriangles(arr, size); 

  return 0; 
} 
Total number of triangles possible is 6

Java code for Valid Triangle Number

// Java code to count the number of 
// possible triangles using brute 
// force approach 
import java.io.*; 
import java.util.*; 

class check
{ 

  // Function to count all possible 
  // triangles with arr[] elements 
  static int findNumberOfTriangles(int arr[], int n) 
  { 
    // Count of triangles 
    int count = 0; 
  
    // The three loops select three 
    // different values from array 
    for (int i = 0; i < n; i++) { 
      for (int j = i + 1; j < n; j++) { 
  
        // The innermost loop checks for 
        // the triangle property 
        for (int k = j + 1; k < n; k++) 
  
          // Sum of two sides is greater 
          // than the third 
          if ( 
            arr[i] + arr[j] > arr[k] 
            && arr[i] + arr[k] > arr[j] 
            && arr[k] + arr[j] > arr[i]) 
            count++; 
      } 
    } 
    return count; 
  } 
  
  // Driver code 
  public static void main(String[] args) 
  { 
    int arr[] = { 10, 21, 22, 100, 101, 200, 300 }; 
    int size = arr.length; 
  
    System.out.println( "Total number of triangles possible is "+ 
    findNumberOfTriangles(arr, size)); 
  } 
}
Total number of triangles possible is 6

Time complexity

O(n^3) Because we are using three loops to find the triplet.

Space complexity

O(1) Because we are maintaining the count variable to keep track of triplets that can form triangles.

Efficient Approach

To optimize the solution we sort the array. We will run two loops.

  1. The first loop will keep track of the first side and the second loop will keep track of the second side of the triangle.
  2. The first loop runs from start to end and the second loop runs from i+1 to end.
  3.  We will maintain a variable k =i+2;
  4. After fixing the first and second sides we need the third side such that a+b>c. We will find a position(k) where the value of c is the maximum possible satisfying the condition to form a triangle.
  5. Then we will add ( k-j ) to the total count.

Valid Triangle Number

Implementation of  Valid Triangle Number

C++ Program for Valid Triangle Number

// C++ program to count number of triangles that can be 
// formed from given array 
#include <bits/stdc++.h> 
using namespace std; 
int comp(const void* a, const void* b) 
{ 
  return *(int*)a > *(int*)b; 
} 
int findNumberOfTriangles(int arr[], int n) 
{ 
  // Sort the array elements in non-decreasing order 
  qsort(arr, n, sizeof(arr[0]), comp); 

  // Initialize count of triangles 
  int count = 0; 
  for (int i = 0; i < n - 2; ++i) { 
    // Initialize index of the rightmost third 
    // element 
    int k = i + 2; 

    // Fix the second element 
    for (int j = i + 1; j < n; ++j) { 
      while (k < n && arr[i] + arr[j] > arr[k]) 
        ++k; 
      if (k > j) 
        count += k - j - 1; 
    } 
  } 

  return count; 
} 

// Driver code 
int main() 
{ 
  int arr[] = { 10, 21, 22, 100, 101, 200, 300 }; 
  int size = sizeof(arr) / sizeof(arr[0]); 

  cout << "Total number of triangles possible is " << findNumberOfTriangles(arr, size); 

  return 0; 
} 
Total number of triangles possible is 6

Java Program for Valid Triangle Number

// Java program to count number of triangles that can be 
// formed from given array 
import java.io.*; 
import java.util.*; 

class CountTriangles { 
  // Function to count all possible triangles with arr[] 
  // elements 
  static int findNumberOfTriangles(int arr[]) 
  { 
    int n = arr.length; 
    // Sort the array elements in non-decreasing order 
    Arrays.sort(arr); 

    // Initialize count of triangles 
    int count = 0; 
    for (int i = 0; i < n - 2; ++i) { 
      // Initialize index of the rightmost third element 
      int k = i + 2; 

      // Fix the second element 
      for (int j = i + 1; j < n; ++j) { 
        while (k < n && arr[i] + arr[j] > arr[k]) 
          ++k; 
        if (k > j) 
          count += k - j - 1; 
      } 
    } 
    return count; 
  } 

  public static void main(String[] args) 
  { 
    int arr[] = { 10, 21, 22, 100, 101, 200, 300 }; 
    System.out.println("Total number of triangles is " + findNumberOfTriangles(arr)); 
  } 
}
Total number of triangles possible is 6

Time complexity

O(n^2)

Because we are using two loops to find the triplet.

Space complexity

O(1) Because we are maintaining the count variable to keep track of triplets that can form triangles.

References

Translate »