Count the number of possible triangles

Difficulty: Medium Asked-in: Amazon, Linkedin, Facebook

Key takeaway: An excellent problem to learn problem solving using sorting and two pointers approach.

Let’s understand the problem

Write a program to count the number of possible triangles that can be formed with three elements from a given unsorted array of positive integers. The three elements, representing the lengths of the sides of a triangle, must satisfy the triangle inequality: the sum of any two sides must be greater than the third side. In other words, x + y > z, y + z > x, and z + x > y must all be true for the triplet (x, y, z) to form a valid triangle.

Assume that all array elements are positive integers.

Example 1

Input: X[]= [4, 6, 3, 7], Output = 3

Explanation: There are three triangles possible: {3, 4, 6}, {4, 6, 7} and {3, 6, 7}.

Example 2

Input: X[] = [10, 21, 22, 100, 101, 200, 300], Output = 6

Explanation: There can be 6 possible triangles: {10, 21, 22}, {21, 100, 101}, {22, 100, 101}, {10, 100, 101}, {100, 101, 200} and {101, 200, 300}.

Discussed solution approaches

• Brute force approach  using three nested Loop
• Solution approach  using sorting and binary search
• Solution approach using sorting and nested loops
• Efficient approach using two pointers

Brute force approach  using three nested loop

Solution idea

One basic solution is to consider every combination of three elements in the given array and check if they satisfy the triangle inequality (the sum of any two sides must be greater than the third side). As we do this, we also keep a count of the number of combinations that satisfy this condition.

To implement this, we use three nested loops:

• The outermost loop runs from i = 0 to n - 3 to select the first side of the triangle, X[i].
• The middle loop runs from j = i + 1 to n - 2 to select the second side, X[j].
• The innermost loop runs from k = j + 1 to n - 1 to select the third side, X[k].

For each iteration, we check if the three sides form a valid triangle. If they do, we increment the count by 1. After all iterations are completed, we return the total count of triangles found.

Solution code C++

int triangleCount(int X[], int n) 
{ 
    int count = 0;
    for (int i = 0; i < n - 2; i = i + 1) 
    {
        for (int j = i + 1; j < n - 1; j = j + 1) 
        { 
            for (int k = j + 1; k < n; k = k + 1)
            {
                if (X[i] + X[j] > X[k] 
                    && X[i] + X[k] > X[j] 
                    && X[k] + X[j] > X[i]) 
                {
                    count = count + 1;
                }
            } 
        } 
    } 
    return count;
}

Solution analysis

The outer for loop iterates n - 2 times, the middle for loop iterates (n - i - 2) times and the inner for loop iterates (n - j - 1) times. The time complexity of each of the three loops is O(n). So the overall time complexity of this code is O(n) * O(n) * O(n) = O(n^3).

From another perspective, we are exploring all possible combinations of all three sides of a triangle. So the total number of possibilities = The number of ways to pick three elements among n elements = nC3 = n(n - 1)(n - 2)/3 = O(n^3).

We are using constant extra space, so space complexity is O(1).

Solution approach  using sorting and binary search

Solution idea

The critical question is: Can we improve the time complexity further? Is it possible to preprocess the array and efficiently identify all possible triangles? One idea is to sort the given array. This is because if we consider a triplet (x, y, z) such that x ≤ y ≤ z, we only need to check x + y > z in order to determine if the triangle formed by them is valid. The idea is simple: If z ≥ y and z ≥ x, then adding any number to z will always produce a sum that is greater than either x or y. So the inequalities z + x > y and z + y > x are satisfied implicitly by the property x ≤ y ≤ z.

To determine number of elements that satisfy the inequality X[k] < X[i] + X[j], we first sort the array X[]. We then consider each pair of elements (X[i], X[j]) such that j > i. Since the array is sorted, as we traverse towards the right to select index k, the value of X[k] can only increase or remain the same. This means that there is a right limit on the value of k such that the elements satisfy X[k] < X[i] + X[j]. Any elements beyond this value of k will not satisfy the inequality.

To find this right limit k, we can use binary search since the array X is sorted. Once we find the right limit k, we can conclude that all the elements in the range (j + 1, k - 1) (inclusive) satisfy the required inequality. So the count of elements satisfying the inequality will be (k - 1) - (j + 1) + 1 = k - j - 1.

Solution code C++

// find the farthest index k of the third side
// whose length is less than the sum of the other two sides.
int binarySearch(int A[], int l, int r, int twoSidesSum) 
{
    while (l <= r) 
    {
        int mid = (l + r) / 2;
        if (A[mid] >= twoSidesSum)
            r = mid - 1;
        else
            l = mid + 1;
    }            
    return l;
}

int triangleCount(int X[], int n)
{
    int count = 0;
    sort(X, X + n);
    for (int i = 0; i < n - 2; i++) 
    {
        int k = i + 2;
        for (int j = i + 1; j < n - 1; j++) 
        {
            k = binarySearch(X, k, n - 1, X[i] + X[j]);
            count = count + k - j - 1;
        }
    }
    return count;
}

The critical point to think about: When we find the right limit index k for a specific pair (i, j), we don't need to start searching for the right limit k for pair (i, j + 1) again from the index j + 2. Instead, we can continue from index k directly (where we left off for the last value of j). This will reduce the range of our binary search for k to shorter values, which can improve the performance of the above algorithm.

Solution analysis

Suppose we are using some efficient O(nlogn) sorting algorithm. So overall time complexity = Time complexity of sorting + Total number of loop iterations * Time complexity of binary search = O(nlogn) + O(n^2) * O(logn) = O(nlogn) + O(n^2logn) = O(n^2logn).

In the worst case, inner loop will take O(nlogn) time when we need to apply binary search n times. What would be the such situation? Think! Suppose we are using iterative binary search and in-place sorting algorithms like heap sort. Space complexity = O(1).

Solution approach using sorting and nested loops

Solution idea

In the above approach, we are applying binary search O(n^2) time in the worst case to find the right limit of the index k for every pair of indices (i, j). Can we think to improve this further? Here is a better idea!

As array is sorted, we can find the right limit of k by traversing linearly from k = i + 2 and stopping at the first value of k that does not satisfy the inequality X[i] + X[j] > X[k]. The count of elements X[k] satisfying this inequality for a particular pair (i, j) is equal to k - j - 1.

Solution steps

To find the number of possible triangles with sides of lengths given in the array X, we can follow these steps:

1. We initialize a variable count to store the count of all possible triangles.
2. We sort the array in ascending order.

3. Now we run a nested loop:

   • Outer loop from 0 to n - 3 to pick the first side X[i] of the triangle.
   • Inner loop from i + 1 to n - 2 to pick the second side X[j] of the triangle.

4. Inside the inner loop:

   • We define a variable k to track the third side X[k] of the triangle. We initialize it to i + 2.
   • We run a while loop that continues as long as k is less than n and X[i] + X[j] > X[k]. This loop helps us find the count of the third sides which satisfy the conditions of a triangle (i.e., all values of k such that X[i] + X[j] > X[k]). In other words, we find the farthest index k of the third side (greater than the indices of both sides) whose length is less than the sum of the other two sides.
   • After the end of while loop, we increase the value of count by k - j - 1.
5. After both loops have completed, we return the value of count.

Solution code C++

int triangleCount(int X[], int n)
{
    int count = 0;
    sort(X, X + n);
    for (int i = 0; i < n - 2; i = i + 1)
    {
        int k = i + 2;
        for (int j = i + 1; j < n - 1; j = j + 1)
        {   
            // find the farthest index k of the third side
            // whose length is less than the sum of the other two sides.
            while (k < n && X[i] + X[j] > X[k])
                k = k + 1;
            count = count + (k - j - 1);
        }
    }
    return count;
}

Solution analysis

The code contains three nested loops, which may lead some to believe that its time complexity is O(n^3). However, by closer examination, we can determine that the complexity is actually better.

In the outermost loop, k is initialized with i + 2. This means that the innermost while loop will run n - i - 2 times at each iteration of the outermost loop. The total number of loop iterations for each iteration of the outer loop is equal to the total iterations of the innermost while loop plus the total iterations of the for loop, which is equal to (n - i - 2) + (n - i - 2) = 2n - 2i - 4 = O(n).

Therefore, the outer loop runs O(n) times, and each iteration, we perform an O(n) operation. The time complexity of the three nested loops is O(n)*O(n) = O(n^2), which is much more efficient than O(n^3).

If we use an efficient O(nlogn) sorting algorithm, the overall time complexity is O(nlogn) + O(n^2) = O(n^2). Since we use a constant extra variable, the space complexity depends on the space complexity of the sorting algorithm.

• If heap sort: Space complexity = O(1)
• If quick sort: Space complexity = O(logn)
• If merge sort: Space complexity = O(n)

Efficient approach   using sorting and two pointers

Solution idea

Suppose we have a sorted array, and we want to find all possible triangles. Now, we consider each element X[i] as the third side of a triangle and try to apply two-pointer approach to find the other two sides of the valid triangle in the subarray from l = 0 to r = i - 1.

• If X[l] + X[r] > X[i], then valid triangles can be formed using the integers at indices (l, r), (l + 1, r), and so on up to the pair of indices (r - 1, r). This is because the array is sorted, so the integers at these indices will also satisfy the triangle inequality. We can then calculate the total count of the triangles that can be formed in one go, which is r - l. Then, we decrement the pointer r by 1 and repeat the process.
• If X[l] + X[r] < X[i], then no valid triangles can be formed using the integers at indices (l, r - 1), (l, r - 1), and so on up to the pair of indices (l, l + 1). In this case, we increment the pointer l by 1 and repeat the process.

Solution steps

1. First we sort the array in ascending order.
2. Now, we run the outer loop from i = n - 1 to 3 to pick the third side X[i] of the triangle.

3. For each iteration of the outer loop, we run two pointer inner loop to pick the other two sides of the triangle. Here both pointers are moving in the opposite direction from l = 0 to r = i - 1. Note: Now we run inner loop till l < r.

   • If X[l] + X[r] > X[i], we increment the triangle count by r - l and decrement the value of r by 1.
   • If If X[l] + X[r] < X[i], we increment l by 1.
4. After the outer loop has finished executing, we returns the value stored in the count variable, which is the total number of triangles that can be formed using the integers in the array as their side lengths.

Solution code C++

int triangleCount(int X[], int n)
{
    sort(X, X + n);
    int count = 0;
    for (int i = n - 1; i >= 2; i = i - 1)
    {
        int l = 0;
        int r = i - 1;
        while (l < r)
        {
            if (X[l] + X[r] > X[i])
            {
                count = count + r - l;
                r = r - 1;
            }
            else
                l = l + 1;
        }
    }
    return count;
}

Solution analysis

Suppose we are using some efficient O(nlogn) sorting algorithm. So overall time complexity. = Time complexity of sorting + Time complexity of nested loop = O(nlogn) + O(n^2) = O(n^2). We are using constant extra variable, so space complexity depends on the space complexity of the sorting algorithm.

• If heap sort: Space complexity = O(1)
• If quick sort: Space complexity = O(logn)
• If merge sort: Space complexity = O(n)

Critical ideas to think!

• How can we modify the above code if values can be zero?
• Searching is a critical operation in solving this problem. Can we consider using a hash table as a solution?
• What are the best and worst-case inputs for the above approaches?
• Why do we initialize k = i + 2?
• Is it possible to solve this problem in O(nlogn) time complexity?
• How can we modify the above solutions, if we need to return the count of all possible right-angle triangles?

Suggested coding problems to practice

1. Find pair sum in an array
2. Remove duplicates from the sorted array
3. Container with the most water
4. Triplets with zero-sum
5. Trapping rain water

Enjoy learning, enjoy coding, enjoy algorithms!