# 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

### More Programming Questions:

#### Strings:

The complete list can be found here: Practise Programming Questions