Find the Count of Triangles in an Unsorted Array

In this tutorial, we will write the Python program to count the possible number of triangle. We have given an unsorted array and we need to determine how many triangles can be created using three distinct values from an unordered array of positive integers. A triangle can be formed when the sum of any two values (or sides) is greater than the third value (or side).

Example -

Let's solve this problem using the naïve approach.

Approach - 1: Naïve Approach

First, we will solve this problem using the naïve approach. In this approach, we will follow the below steps -

1. Initialize a variable count to keep track of the number of triangles found, initially set to 0.
2. Then create three nested loops to iterate through all possible combinations of three array elements.
3. In the innermost loop, check if the current combination of three elements can form a valid triangle according to the triangle inequality theorem: the sum of the lengths of any two sides must be greater than the length of the third side.
4. If the current combination forms a valid triangle, increment the count variable by 1.
5. After the loops finish iterating, the count variable will contain the total number of triangles that can be formed.

Let's implement the above steps in the Python code.

Example -

Output:

Number of triangles: 3

This naive approach has a time complexity of O(n³) due to the three nested loops, making it inefficient for large arrays. However, it provides a straightforward solution to the problem.

Approach - 2: Using Sorting

To solve this problem using sorting, you can follow these steps:

1. Sort the input array arr in ascending order.
2. Initialize a variable count to keep track of the number of triangles.
3. Iterate through the sorted array from left to right using a loop. For each element arr[i] at index i, perform the following steps:
   1. Initialize two pointers, left and right, where left points to the first element (index 0) and right points to the element just before arr[i].
   2. While left is less than right, check if arr[left] + arr[right] > arr[i]. If this condition is met, it means that triangles can be formed with arr[i], arr[left], and arr[right]. Increment the count by the number of valid triangles that can be formed, which is right - left.
   3. If the condition is not met, decrement the right pointer to explore smaller values.
4. After the loop completes, count will contain the total number of triangles that can be formed.
5. Return the value of count as the output.

Let's understand the following example -

Example -

Output:

Number of triangles (arr1): 3
Number of triangles (arr2): 6

The time complexity of the code provided to count the number of triangles in a sorted array is O(n^2), where 'n' is the length of the input array arr.

Approach - 3: Two Pointer Approach

To solve this problem using the two-pointer approach, we can follow these steps:

1. Sort the input array in ascending order.
2. Initialize a variable `count` to 0. This variable will keep track of the number of triangles.
3. Iterate through the sorted array using a pointer `i` from 0 to `n-3`, where `n` is the length of the array. This pointer represents the first side of the potential triangle.
4. For each `i`, initialize another pointer `left` to `i+1` and `right` to `n-1`. These two pointers represent the second and third sides of the potential triangle.
5. Inside a while loop, check if `arr[i] + arr[left] > arr[right]`, where `arr[i]`, `arr[left]`, and `arr[right]` represent the lengths of the three sides. If this condition is met, it means we can form a triangle.
6. If the condition is met, it implies that we can also form triangles with `left+1`, `left+2`, ..., `right-1` as the third side, as long as the sum of the lengths of any two sides is greater than the third side. So, increment the `count` by `right - left`.
7. If the condition is not met, decrement `right` by 1 to reduce the third side's length.
8. After the while loop, increment `left` by 1 to consider the next potential second side.
9. Repeat steps 5-8 until `left` is greater than or equal to `right`.
10. Continue the outer loop to consider the next potential first side (`i`).
11. After the outer loop finishes, return the value of `count`, which represents the total number of triangles.

Below is the Python code of the two-pointer approach.

Example -

Output:

Number of triangles: 3

This code finds the number of triangles that can be formed using the two-pointer approach and has a time complexity of O(n^2).

Conclusion

In this tutorial, we explored three approaches to solve the problem of counting triangles in an unsorted array, where each triangle is formed by selecting three distinct values from the array. The naive approach involved three nested loops and had a time complexity of O(n³), making it inefficient for large arrays. The sorting-based approach and the two-pointer approach both offered efficient solutions with time complexities of O(n²). Sorting the array allowed us to reduce the problem to finding valid triangle combinations efficiently. The two-pointer approach further improved performance by eliminating unnecessary checks.