Question

Find a triplet in unsorted array that sum to a given value in java ?

int arr[] = {12, 3, 4, 1, 6, 9};
int sum = 24;

Answer 1

See the very simple solution comes in our mind. We have three loops and see the sum of given triplet is equal to given sum.

public static void main(String[] args) {
        int arr[] = {12, 3, 4, 1, 6, 9};
        int sum = 24;
        boolean isFound = isTripletInUnSortedArray(arr,sum);
        System.out.println(isFound == true ? "Pair Found" : "Pair Not Found");       
    }

//Time Complexity : O(n^3)
    private static boolean isTripletInUnSortedArray(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:-

Triplet: 12, 3, 9
Pair Found

Answer 2

See the given solution to find triplet in unsorted array. This solution is nice by using hashing in term of time complexity. This solution will take O(n^2) time complexity and O(n)  space complexity.

See the running code to find triplet in unsorted array.:-

public static void main(String[] args) {

int arr[] = {12, 3, 4, 1, 6, 9};

int sum = 24;

isFound = isTripletInUnSortedArrayUsingHashing(arr,sum);

System.out.println(isFound == true ? "Pair Found" : "Pair Not Found");

}

 //Time Complexity:- O(n^2)

//Space Complexity:- O(n)

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

// Fix the first element as arr[i] 

        for (int i = 0; i < arr.length - 2; i++) { 

            // Find pair in subarray A[i+1..n-1] 

            // with sum equal to sum - A[i] 

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

            int curr_sum = sum - arr[i]; 

            for (int j = i + 1; j < arr.length; j++) { 

                if (set.contains(curr_sum - arr[j]) ) { 

                    System.out.println("Triplet is ["+ arr[i]+", "+ arr[j]+", "+ (curr_sum - arr[j])+"]"); 

                    return true; 

                } 

                set.add(arr[j]); 

            } 

        }

return false;

}

Answer 3

This solution will take only O(n^2) time complexity. In this solution, first of all sort the array and find triplet in sorted array.

See the running code to find the triplet in unsorted array:-

public static void main(String[] args) {

int arr[] = {12, 3, 4, 1, 6, 9};

int sum = 24;

isFound = isTripletInUnSortedArrayUsingSorting(arr,sum);

System.out.println(isFound == true ? "Pair Found" : "Pair Not Found");

}

//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 isTripletInUnSortedArrayUsingSorting(int[] arr, int sum) {

/* Sort the elements */

        quickSort(arr, 0, arr.length - 1);

//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;

}

//Time Complexity O(n log n)

//start:- Starting index 

    //end:- Ending index 

private static void quickSort(int arr[], int start, int end) { 

        int pi; 

  

        /* Partitioning index */

        if (start < end) { 

            pi = partition(arr, start, end); 

            quickSort(arr, start, pi - 1); 

            quickSort(arr, pi + 1, end); 

        } 

    } 

private static int partition(int arr[], int start, int end) { 

        int x = arr[end]; 

        int i = (start - 1); 

        int j; 

  

        for (j = start; j <= end - 1; j++) { 

            if (arr[j] <= x) { 

                i++; 

                int temp = arr[i]; 

                arr[i] = arr[j]; 

                arr[j] = temp; 

            } 

        } 

        int temp = arr[i + 1]; 

        arr[i + 1] = arr[end]; 

        arr[end] = temp; 

        return (i + 1); 

    } 

Output:-

Pair: [9, 12, 3]

Pair Found