Find triplet with given sum in an array.
Given an array of unsorted integers and a value k. Write a code to determine whether or not there exist three elements in array whose sum is equal to k.
Return true if triplet exist else return false.
For example:
Example 1:
Input: {1, 4, 45, 6, 10, 8} k = 13 Output: true (1, 4, 8)
Example 2:
Input: {2, 7, 4, 0, 9, 5, 1, 3} k = 6
Output: true {(2, 4, 0), (5, 1, 0), (1, 2, 3)}
This problem is similar to find triplets with zero sum. So, we have to find three numbers of an array whose sum is equal to given value k.
We have discussed the problem statement. Let’s discuss how we can solve this problem efficiently. Also, At the end of this post, i have mentioned the link of video tutorial in which i have explained multiple approaches and their time complexities.
Method 1: Brute Force Approach
The simplest approach is to use three for loops to generate all triplets and compare every sum with given value k. If triplet exist then return true else return false.
The time complexity of this approach is O(n^3).
Find pairs with given sum in a sorted array
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
/* Find Triplet with Given sum using Brute Force Approach */ public class TripletSum { public static boolean findTripletWithBruteForce(int[] arr, int sum) { //If array size is less than 3 then simply return false if(arr.length < 3) { return false; } int len = arr.length; //Run three loop to check whether triplet exists in an array for(int i = 0; i < len-2; i++) { for(int j = i+1; j < len-1; j++) { for(int k = j+1; k < len; k++) { if(arr[i] + arr[j] + arr[k] == sum) { return true; } } } } return false; } public static void main(String[] args) { int[] arr = { 1, 4, 45, 6, 10, 8}; int k = 13; boolean result = findTripletWithBruteForce(arr, k); if(result) { System.out.println("Exists"); } else { System.out.println("Not exists"); } } } |
Find Triplet with Given Sum in an Array using Sorting
We can reduce the time complexity, if we first sort the array and then run two for loop to find triplets whose sum is equal to given value k.
The time complexity of this approach is O(n^2).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
/* Find Triplet with Given sum using Sorting */ public class TripletSum { public static boolean findTriplet(int[] arr, int sum) { if(arr.length < 3) { return false; } //Sort the array Arrays.sort(arr); int len = arr.length; for(int i = 0; i < len; i++) { int start = i+1; int end = len-1; while(start < end) { if(arr[i] + arr[start] + arr[end] == sum) { return true; } else if (arr[i] + arr[start] + arr[end] < sum) { start++; } else { end--; } } } return false; } public static void main(String[] args) { int[] arr = { 1, 4, 45, 6, 10, 8}; int k = 13; boolean result = findTriplet(arr, k); if(result) { System.out.println("Exists"); } else { System.out.println("Not exists"); } } } |
