Counting the triangles that can be formed from segments of given lengths 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 &gt; c\$ ii) \$b + c &gt; a\$ iii) \$a + c &gt; b\$
  
  Following are steps to count triangle.
  
  
  Sort the array in non-decreasing order.
  Initialize two pointers i and j to first and second elements respectively, and initialize count of triangles as 0.
  Fix i and j and find the rightmost index k (or largest arr[k]) such that arr[i] + arr[j] &gt; 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] &lt; arr[j] &lt;
  arr[k]. And we check for condition (i) when we pick k.
  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.
  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 &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;algorithm&gt;
#include &lt;iterator&gt;

using namespace std;
int triangles (vector&lt;int&gt; &amp;V, int N);

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

int triangles (vector&lt;int&gt; &amp;V, int N)
{
    int sum = 0;
    sort(V.begin(), V.end());
    for (int i = 0; i &lt;= N-3; i++)
    {   
        int k = i + 2;
        for (int j = i + 1; j &lt;= N-2; j++)
        {
            while (k &lt; N &amp;&amp; V[k] &lt; 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 &lt; 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?
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.