Counting the triangles that can be formed from segments of given lengths

Question

Problem Statement:

Given an unsorted array of positive integers. Find the number of triangles that can be formed with three different array elements as lengths of three sides of triangles.

Input: The first line of the input contains T denoting the number of testcases. First line of test case is the length of array N and second line of test case are its elements.

Output: Number of possible triangles are displayed to the user.

Constraints:

\$1 \le T \le 200\$
\$3 \le N \le 10^7\$
\$1 \le \mathrm{arr}[i] \le 10^3\$

Example:

Input:

2
3
3 5 4
5
6 4 9 7 8

Output:

1
10

Algorithm:

The efficient \$O(n^2)\$ algorithm for solving this problem has been explained here.

Let \$a\$, \$b\$ and \$c\$ be three sides. The below condition must hold for a triangle (Sum of two sides is greater than the third side) i) \$a + b > c\$ ii) \$b + c > a\$ iii) \$a + c > b\$

Following are steps to count triangle.

1. Sort the array in non-decreasing order.

2. Initialize two pointers i and j to first and second elements respectively, and initialize count of triangles as 0.

3. Fix i and j and find the rightmost index k (or largest arr[k]) such that arr[i] + arr[j] > arr[k]. The number of triangles that can be formed with arr[i] and arr[j] as two sides is k – j. Add k – j to count of triangles.

   Let us consider arr[i] as \$a\$, arr[j] as \$b\$ and all elements between arr[j+1] and arr[k] as \$c\$. The above mentioned conditions (ii) and (iii) are satisfied because arr[i] < arr[j] < arr[k]. And we check for condition (i) when we pick k.

4. Increment j to fix the second element again.

   Note that in step 3, we can use the previous value of k. The reason is simple, if we know that the value of arr[i] + arr[j-1] is greater than arr[k], then we can say arr[i] + arr[j] will also be greater than arr[k], because the array is sorted in increasing order.

5. If j has reached end, then increment i. Initialize j as i + 1, k as i+2 and repeat the steps 3 and 4.

Code Implementation (in C++):

This is my implementation of the algorithm in C++ (using vectors instead of raw arrays):

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

using namespace std;
int triangles (vector<int> &V, int N);

int main () {
    int T;
    cin >> T;
    vector<int> V;
    for (int i = 0; i < T; i++)
    {
        int N;
        cin >> N;
        for (int j = 0; j < N; j++)
        {
           int temp;
           cin >> temp;
           V.push_back(temp);
        }
        cout << triangles (V, N) << endl;
        V.clear();
    }
    return 0;
}

int triangles (vector<int> &V, int N)
{
    int sum = 0;
    sort(V.begin(), V.end());
    for (int i = 0; i <= N-3; i++)
    {   
        int k = i + 2;
        for (int j = i + 1; j <= N-2; j++)
        {
            while (k < N && V[k] < V[i] + V[j])
                k++;
            sum += k-j-1;
        }
    }
    return sum;
}

Problem:

The code gives the perfectly correct output for any input, however, when I submit the code on GeekForGeeks Practice, it says

Your program took more time than expected (Time Limit Exceeded). Expected Time Limit < 2.656sec. Hint: Please optimize your code and submit again.

At this point, I'm not sure how to optimize my code. Any ideas? Do I necessarily need to use an array instead of a vector in order to speed up the program?

Answer 1

Don't use using namespace std;. It is extremely bad practice and will ruin your life. You will have trouble on common identifiers like count, size, etc. See Why is “using namespace std;” considered bad practice? for more information.

The input format is extremely awkward, but this seems to be beyond your control, so I'll leave it alone.

Instead of using a linear search as you are doing in your loop, it might be beneficial to do a binary search if the amount of data is large. (This needs some testing.) Also, use standard algorithms to make your code more readable.

Also, in this very case, a dynamic vector may not be the best way to appeal to the timer. (I'm not sure how I would phrase that.) reserve may help. You can try using a static vector like this one because you know that the size is below a limit.

Answer 2

The statement V.push_back(temp); can be inefficient, as the vector V may need to be reallocated multiple times.

Use std::vector::reserve(N) to ensure sufficient space exists in the vector before reading in the data to avoid multiple reallocations.

---

\$3 \le N \le 10^7\$
\$1 \le \mathrm{arr}[i] \le 10^3\$

With \$10^7\$ pigeons and \$10^3\$ holes, many holes can have over 10,000 pigeons! You might want to consider an array of counts indexed by side length. No sort required; it is automatically sorted. But your algorithm will need considerable reworking.

Answer 3

Even after using reserve, as suggested by @L.F. and @AJNeufeld, there was no considerable speedup and it was still timing out. So I decided to use dynamically allocated arrays instead. I also removed using namespace std, and instead only imported those std functions which are required in the program.

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

using std::cout;
using std::cin;
using std::endl;
using std::sort;

long long int triangles (int arr[], int N);

int main () {
    int T;
    cin >> T;
    for (int i = 0; i < T; i++)
    {
        int N;
        cin >> N;
        int *arr = new int[N];
        for (int j = 0; j < N; j++)
        {
        cin >> arr[j];
        }
        cout << triangles (arr, N) << endl;
        delete arr;
    }
    return 0;
}

long long int triangles (int arr[], int N)
{
    long long int sum = 0;
    sort(arr, arr+N);
    for (int i = 0; i <= N-3; i++)
    {   
        int k = i + 2;
        for (int j = i + 1; j <= N-2; j++)
        {
            while (k < N && arr[k] < (arr[i] + arr[j]))
                k++;
            sum += k-j-1;
        }
    }
    return sum;
}

Note that the data type of the sum which is returned by the triangles() function must be at least long long int, as it otherwise exceeds the range of regular int.