Count the number of possible triangles

Problem Description

Given an array of integers, find the number of triangles that can be formed using three distinct elements of the array as the lengths of the sides. A triangle is valid if the sum of any two sides is greater than the third side.

Example:

  • Input: arr[] = [4, 6, 3, 7]
  • Output: 3
  • Explanation: The valid triangles are [3, 4, 6], [4, 6, 7], and [3, 6, 7]. Note that [3, 4, 7] is not a valid triangle because 3 + 4 is not greater than 7.

Solution Code

import java.util.Arrays;

class Solution {
    // Function to count the number of possible triangles.
    static int countTriangles(int arr[]) {
        int n = arr.length;
        Arrays.sort(arr); // Sort the array to make it easier to find valid triangles
        int count = 0;

        // Fix the third side and use two pointers to find valid pairs
        for (int i = n - 1; i >= 2; i--) {
            int left = 0;
            int right = i - 1;

            while (left < right) {
                // If arr[left] + arr[right] > arr[i], then all elements between left and right
                // can form a triangle with arr[right] and arr[i]
                if (arr[left] + arr[right] > arr[i]) {
                    count += right - left;
                    right--;
                } else {
                    left++;
                }
            }
        }

        return count;
    }
}

Hint

  • Sort the array first. Use a two-pointer approach to efficiently count valid triangles by fixing the largest side and checking for valid pairs of smaller sides.

Approach Name

Two-Pointer Technique with Sorting

Intuition

By sorting the array, we can fix the largest side of the triangle and use two pointers to find valid pairs of smaller sides. If the sum of the two smaller sides is greater than the largest side, then all elements between the two pointers can form valid triangles with the largest side.

Algorithm

  1. Sort the array in ascending order.
  2. Fix the largest side of the triangle (starting from the end of the array).
  3. Use two pointers (left and right) to find valid pairs of smaller sides.
  4. If arr[left] + arr[right] > arr[i], then all elements between left and right can form valid triangles with arr[right] and arr[i]. Increment the count by right - left and move the right pointer to the left.
  5. If arr[left] + arr[right] <= arr[i], move the left pointer to the right.
  6. Repeat until all possible triangles are counted.

Test Input

4 6 3 7

Complexity Analysis

  • Time Complexity: O(n²), where n is the number of elements in the array. Sorting takes O(n log n), and the two-pointer approach takes O(n²) in the worst case.
  • Space Complexity: O(1), as we are using a constant amount of extra space.

This solution efficiently counts the number of valid triangles using sorting and a two-pointer approach, ensuring optimal performance for the given constraints.