Find a triplet that sum to a given value in java

Question

Find a triplet (Sorted array) that sum to a given value in java.

int arr[] = {5,6,7,8,10,20,30,40};

int sum = 21;

Answer 1

See the very simple solution to find triplet that sum of a given sorted array. See a naive approach that runs three loops and check one by one which sum of three elements is given sum or not. If the sum of three elements is given sum, then print elements and pair found otherwise print not found.

See the running code to find triplet that sum of a given sorted array:-

//Time Complexity O(n^3)
    private static boolean isTripletInSortedArray(int[] arr, int sum) {
        //Base check
        if(arr.length < 3)
            return false;
        for(int i=0; i<arr.length; i++) {
            for(int j=i+1; j<arr.length; j++) {
                for(int k=j+1; k<arr.length; k++) {
                    if(arr[i]+arr[j]+arr[k] == sum) {
                        System.out.println("Triplet: " + arr[i] + ", " + arr[j] + ", " + arr[k]);
                        return true;
                    }
                }
            }
        }
        System.out.println("Triplet is not found");
        return false;
    }

Output:-

Pair: [6, 10, 5]
Pair Found

Answer 2

See the following method by using the hashing method to find triplet. This method to find triplet using hashing in O(n) time complexity.

Time Complexity O(n^2)

Space Complexity O(n)

See the following steps:-

Step1:- Run for loop from i=0 to n-2

Step2:- Create an empty hashtable

Step3:- Run another inner loop from j=i+1 to n-1

Step4:- Under loop, If -(arr[i] + arr[j]) is present in hashtable

Step5:- print arr[i], arr[j] and -(arr[i]+arr[j])

Step6:- Else

Step7:- Insert arr[j] in hashtable.

See the running code to find triplet:-

private static void isTripletInSortedArray(int arr[], int n, int sum) { 

    for (int i = 0; i < n - 1; i++)  { 

        // Find all pairs with sum equals to "sum-arr[i]" 

        HashSet<Integer> set = new HashSet<>(); 

        for (int j = i + 1; j < n; j++) { 

            int x = sum - (arr[i] + arr[j]); 

            if (set.contains(x)) 

                System.out.print("["+ x+","+ arr[i]+","+ arr[j]+"]"); 

            else

                set.add(arr[j]); 

        } 

    } 

} 

Answer 3

See the very most optimized solution to find triplet that sum to a given value in sorted array in java. We can solve it in O(n^2) time complexity and O(1) extra space. 

See the running code to find the triplet of given sum:-

//If arry not sorted then first of all sort the array O(n log n) and find the pairs. 

//Unsorted array Time Complexity O(n log n)+O(n^2).

//Don't use hashing because hashing will require O(n)extra space. So, bellow approach is better 

//Time Complexity O(n^2)

private static boolean isTripletInSortedArray1(int[] arr, int sum) {

//Base check

if(arr.length < 3)

return false;

int len = arr.length;

//O(n)

for(int i=0; i<len; i++) {

//O(n)

if(isPair(arr, i+1, len-1, sum-arr[i])) {

System.out.println(arr[i]+"]");

return true;

}

}

return false;

}

//Time Complexity O(n)

private static boolean isPair(int[] arr, int left, int right, int sum) {

int start=left, end=right;

while(start<end) {

if(arr[start]+arr[end]==sum) {

System.out.print("Pair: ["+arr[start]+", "+ arr[end]+", ");

return true;

}

if(arr[start]+arr[end] > sum) {

end--;

}else {

start++;

}

}

return false;

}