Triplet Family

JavaView on GFG

Time: O(n^2)

Space: O(1)

Intuition

Find if three elements a, b, c exist such that a+b=c (or similar constraint). Sort + two sum.

Algorithm

1Sort. For each c (largest element): use two-pointer search for pair (a,b) with a+b=c in the prefix.

Common Pitfalls

•For each element as potential sum: two-pointer in remaining elements. O(n^2) total.

Triplet Family.java

Java

// Approach: Sort array. For each element as potential largest, two pointers find if a+b = third element.
// Time: O(n^2) Space: O(1)
class Solution {
    public boolean findTriplet(int[] arr) {
        int n = arr.length;

        // Iterate through each element as the potential third element
        for (int i = 0; i < n; i++) {
            HashSet<Integer> complements = new HashSet<>();

            // Iterate through the rest of the elements
            for (int j = 0; j < n; j++) {
                if (i != j) { // Ensure we don't use the same element
                    int required = arr[i] - arr[j];

                    // Check if the required complement exists
                    if (complements.contains(required))
                        return true;

                    // Add the current element to the set
                    complements.add(arr[j]);
                }
            }
        }
        return false;
    }
}

Was this solution helpful?