Count the number of possible triangles

Given an integer array arr[]. Find the number of triangles that can be formed with three different array elements as lengths of three sides of the triangle. 

A triangle with three given sides is only possible if sum of any two sides is always greater than the third side.

Examples:

Input: arr[] = [4, 6, 3, 7]
Output: 3
Explanation: There are three triangles possible [3, 4, 6], [4, 6, 7] and [3, 6, 7]. Note that [3, 4, 7] is not a possible triangle. 

Input: arr[] = [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]

Input: arr[] = [1, 2, 3]
Output: 0
Explanation: No triangles are possible.

Constraints:
3 <= arr.size() <= 10³
0 <= arr[i] <= 10⁵

Approach 01:

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int countTriangles(vector<int>& sideLengths) {
        sort(sideLengths.begin(), sideLengths.end());  // Sort the array to enable the triangle condition check
        int n = sideLengths.size();
        int triangleCount = 0;  // Count of valid triangles

        for (int longestSideIndex = 2; longestSideIndex < n; ++longestSideIndex) {
            int left = 0;
            int right = longestSideIndex - 1;

            while (left < right) {
                // Check if the triangle inequality holds
                if (sideLengths[left] + sideLengths[right] > sideLengths[longestSideIndex]) {
                    triangleCount += (right - left);  // Count all valid pairs
                    --right;  // Move the right pointer left to check other pairs
                } else {
                    ++left;  // Move the left pointer right to increase the sum
                }
            }
        }

        return triangleCount;
    }
};

class Solution:
    def countTriangles(self, sideLengths):
        sideLengths.sort()  # Sort the array to enable the triangle condition check
        n = len(sideLengths)
        triangleCount = 0  # Count of valid triangles

        for longestSideIndex in range(2, n):
            left = 0
            right = longestSideIndex - 1

            while left < right:
                # Check if the triangle inequality holds
                if sideLengths[left] + sideLengths[right] > sideLengths[longestSideIndex]:
                    triangleCount += (right - left)  # Count all valid pairs
                    right -= 1  # Move the right pointer left to check other pairs
                else:
                    left += 1  # Move the left pointer right to increase the sum

        return triangleCount

Time Complexity:

• Sorting:

  The array is sorted at the beginning, which takes \( O(n \log n) \), where \( n \) is the number of elements in sideLengths.

• Outer Loop:

  The outer loop iterates through each element, starting from the third element. This contributes \( O(n) \).

• Two-Pointer Approach:

  For each iteration of the outer loop, the two-pointer approach runs in \( O(n) \) in the worst case. Combining this with the outer loop, the two-pointer approach contributes \( O(n^2) \).

• Overall Time Complexity:

  \( O(n^2) \), since \( O(n^2) \) dominates \( O(n \log n) \).

Space Complexity:

• Sorting:

  The sorting operation is in-place, so it uses \( O(1) \) additional space.

• Auxiliary Variables:

  Constant space is used for pointers and loop variables.

• Overall Space Complexity:

  \( O(1) \), as no additional space is used apart from input and output storage.