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

287 views
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;

by (3.7k points)

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);
}

//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;
}
}
}
}
return false;
}

Output:-

Triplet: 12, 3, 9
Pair Found

by (2.8k points)

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

}

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

}

}

}

return false;

}

by (4.4k points)

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

}

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