Count the number of possible triangles

JavaView on GFG

Intuition

Count triplets forming valid triangles. Sort + two pointers: for each largest side, count valid pairs.

Algorithm

1Sort array. For each k (largest side) from n-1 down to 2: two pointers i=0, j=k-1.
2If arr[i]+arr[j] > arr[k]: all pairs (i, i+1..j-1, k) valid, count += j-i, j--. Else i++.

Common Pitfalls

•Triangle inequality: sum of two smaller sides > largest. Sort first; largest side is arr[k].

Count the number of possible triangles.java

Java

// Approach: Sort array. For each pair (i,j) with j>i, binary search for the largest k where arr[k] < arr[i]+arr[j].
// Time: O(n^2 log n) Space: O(1)
import java.util.*;

class Solution {
    // Function to count the number of possible triangles.
    static int countTriangles(int arr[]) {
        Arrays.sort(arr);
        int n = arr.length;
        int cnt = 0;
        for (int i = 2; i < n; i++) {
            int j = 0;
            int k = i - 1;
            while (j < k) {
                int sum = arr[j] + arr[k];
                if (sum > arr[i]) {
                    cnt += k - j;
                    k--;
                } else
                    j++;
            }
        }

        return cnt;
    }
}

Was this solution helpful?