Count the number of possible triangles

JavaView on GFG

Problem Overview

Count triplets forming valid triangles.

See our study guide for structured GFG and LeetCode practice.

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?