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.

Count the number of possible triangles example

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 pseudocode

triangleCount(X, n)
    count = 0
    // Check every combination of three elements
    for i from 0 to n - 3
        for j from i + 1 to n - 2
            for k from j + 1 to n - 1
                // Count the triplet 
                // if its lengths satisfy the triangle inequalities
                if X[i] + X[j] > X[k] AND
                   X[i] + X[k] > X[j] AND
                   X[j] + X[k] > 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 = 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? 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 pseudocode

binarySearch(A, l, r, twoSidesSum)
    // Find the first index whose value is at least twoSidesSum
    while l <= r
        mid = l + (r - l) / 2

        if A[mid] >= twoSidesSum
            r = mid - 1
        else
            l = mid + 1

    return l


triangleCount(X)
    n = length(X)
    count = 0
    sort X in ascending order
    // Choose the first two sides
    for i from 0 to n - 3
        for j from i + 1 to n - 2
            twoSidesSum = X[i] + X[j]
            // Find the first third side that is too long
            k = binarySearch(X, j + 1, n - 1, twoSidesSum)
            // Count valid third sides before that index
            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. This will reduce the range of our binary search, which can improve the performance of the above algorithm. Here is the optimised pseudocode:

binarySearch(X, l, r, twoSidesSum)
    // Find the first index whose value is at least twoSidesSum
    while l <= r
        mid = l + (r - l) / 2

        if X[mid] >= twoSidesSum
            r = mid - 1
        else
            l = mid + 1

    return l

triangleCount(X)
    n = length(X)
    count = 0
    sort X in ascending order
    // Choose the first side
    for i from 0 to n - 3
        // Initialize k to the first possible third-side index
        k = i + 2
        // Choose the second side
        for j from i + 1 to n - 2
            twoSidesSum = X[i] + X[j]
            // Continue searching from the previous boundary k
            k = binarySearch(X, k, n - 1, twoSidesSum)
            // Count valid third sides before k
            count = count + k - j - 1

    return count

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^2*logn) = O(n^2*logn).

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

We initialise a variable count to store the count of all possible triangles.
We sort the array in ascending order.
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.
Inside the inner loop:
- We define a variable k to track the third side X[k] of the triangle. We initialise 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 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.
After both loops, we return the value of count.

Solution pseudocode

triangleCount(X, n)
    count = 0
    sort X in ascending order
    // Choose the first side
    for i from 0 to n - 3
        k = i + 2
        // Choose the second side
        for j from i + 1 to n - 2
            // Advance k while the third side can form a triangle
            while k < n and X[i] + X[j] > X[k]
                k = k + 1
            // Count valid third sides between j and k
            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 initialised 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 = Total iterations of the innermost while loop + Total iterations of the inner for loop = (n - i - 2) + (n - i - 2) = 2n - 2i - 4 = O(n). So, the outer loop runs O(n) times, and each iteration, we perform an O(n) operation. The time complexity = O(n)*O(n) = O(n^2).

If we use an efficient O(nlogn) sorting algorithm, the overall time complexity = O(nlogn) + O(n^2) = O(n^2). Since we use a constant extra variable, the space complexity depends on 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

First we sort the array in ascending order.
Now, we run the outer loop from i = n - 1 to 3 to pick the third side X[i] of the triangle.
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.
After the outer loop, we returns the value stored in the count variable.

Solution pseudocode

triangleCount(X, n)
    sort X in ascending order
    count = 0
    // Treat each element as the largest side
    for i from n - 1 down to 2
        l = 0
        r = i - 1
        // Search for pairs that can form a triangle with X[i]
        while l < r
            if X[l] + X[r] > X[i]
                // Every value from X[l] through X[r - 1]
                // can pair with X[r] to form a triangle
                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 initialise k = i + 2?
Is it possible to solve this problem in O(nlogn) time?
How can we modify the above solutions, if we need to return the count of all possible right-angle triangles?

Count the number of possible triangles

Let’s understand the problem

Example 1

Example 2

Discussed solution approaches

Brute force approach using three nested loop

Solution idea

Solution pseudocode

Solution analysis

Solution approach using sorting and binary search

Solution idea

Solution pseudocode

Solution analysis

Solution approach using sorting and nested loops

Solution idea

Solution steps

Solution pseudocode

Solution analysis

Efficient approach using sorting and two pointers

Solution idea

Solution steps

Solution pseudocode

Solution analysis

Critical ideas to think!

Suggested coding problems to practice

More from EnjoyAlgorithms

Self-paced Courses and Blogs