How to Find Possible Triangles in an Array

In this example, we’ll find possible triangles in an array:

Input:
int[] arr1 = {4, 3, 9, 8 };
Output:
Set 1 :: 4 9 8
Set 2 :: 3 9 8
Possible triangles :: 2

Algorithm: (Approach #1)

  • Run three nested loops, each loop starting from the index of the previous loop to end of the array.
  • Check if sum of two sides is greater than the third.
  • If all three conditions match, (that means it is a possible triangle), then increase the count.
  • Print the sides/count.

1. Java

public class FindPossibleTriangles {

    public static void main(String[] args) {
        int[] arr = {6, 4, 9, 7, 8};
        int numberOfTriangles = findNumberOfTriangles(arr, arr.length);
        System.out.println("Possible triangles :: " + numberOfTriangles);
    }

    static int findNumberOfTriangles(int arr[], int n) {
        int count = 0;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (arr[i] + arr[j] > arr[k]
                            && arr[i] + arr[k] > arr[j]
                            && arr[k] + arr[j] > arr[i]) {
                        count++;
                        System.out.println("Set " + count + " :: " + arr[i] + " " + arr[j] + " " + arr[k]);
                    }
                }
            }
        }

        return count;
    }
}

Output:

Set 1 :: 6 4 9
Set 2 :: 6 4 7
Set 3 :: 6 4 8
Set 4 :: 6 9 7
Set 5 :: 6 9 8
Set 6 :: 6 7 8
Set 7 :: 4 9 7
Set 8 :: 4 9 8
Set 9 :: 4 7 8
Set 10 :: 9 7 8
Possible triangles :: 10

Approach #2:

    // Effective approach
    static int findNumberOfTriangles(int arr[], int n) {
        int count = 0;

        Arrays.sort(arr);

        for(int i= arr.length - 1; i >=0; i--){
            int left = 0;
            int right = i - 1;

            while(left < right){
                if(arr[left] + arr[right] > arr[i]){
                    count += (right - left);
                    right--;
                }
                else{
                    left++;
                }
            }
        }
        return count;
    }

Complete Java Solutions can be found here: Github Link

The complete list can be found here: Practise Programming Questions