Do you think IIT Guwahati certified course can help you in your career?
No
Introduction
Today's problem, i.e., " Smallest Difference Triplet from Three arrays, "is highly asked in product-based companies. We'll review all options, including brute force and the most efficient solution.
Let's get started with the problem statement without further ado.
Three same sized arrays are provided. Find a triplet whose absolute difference between maximum and minimum element is the minimum of all the triplets. A triplet should be chosen so that one element from each of the three given arrays appears in it.
If there are two or more minor difference triplets, display the one with the smallest sum of its elements.
Example
Input :arr1[] = {4, 3, 7}
arr2[] = {21, 5, 11}
arr3[] = {2, 6, 10}
Output : 4, 5, 6
Input : arr1[] = {14, 11, 17, 8}
arr2[] = {9, 16, 12, 7}
arr3[] = {12, 15, 10, 4}
Output : 12 12 11
Explanation: As we check all the possible triplets from three arrays and print the one triplet which satisfies the condition.
Brute Force Approach
Consider every triplet and find the required smallest difference triplet out of them.
Steps of Algorithm
Generate all the possible triplets using three loops.
Now store the current difference between the present triplet's maximum and min/imum element and the present triplet's current sum.
And compare these two(current_sum and current_difference) with the values till now(sum and difference).
According to the given condition, update the values and print the final results.
Pseudocode
FOR i←0 to length of the array{
FOR j←0 to length of the array{
FOR k←0 to the length of the array{
max = maximum(array1[i],array2[j],array3[k])
min = minimum(array1[i],array2[j], array3[k])
current_difference = maximum - minimum
current_sum = array1[i],array2[j],array3[k]
IF (current_difference < difference){
difference = current_difference
sum = current_sum;
a = max
b = sum - max - min
c = min
}
IF (current_difference == difference && current_sum<sum){
sum = current_sum
a = max
b = sum - max - min
c = min
}
}
}
}
Complexity Analysis
Time Complexity: O(n*n*n) because we are traversing three arrays to check the possible triplets' condition.
Space Complexity: O(1) because the variables used are of constant space, and no additional space is used here.
Optimized Approach
We can optimize the above solution to find the Smallest Difference Triplet from Three arrays by using the concept of sorting.
Steps of Algorithm
Sorting the three arrays in non decreasing order.
Use Three-pointers and start from the left-most members of three arrays (i,j,k).
Now find minimum element and maximum element from the present triplet, calculate the absolute current difference between maximum and minimum element(max-min)
And compare the current_difference with the value of resultant difference till now and update the value.
Now increment pointer of minimum element’s array.
Repeat steps 3, 4, 5 until any one pointer reaches to its end i.e (till this i<n or j<n or k<n condition is not failed).
Finally, print the final result.
Implementation
C++
#include <bits/stdc++.h>
using namespace std;
// Function to find and print the the Smallest Difference Triplet From Three Arrays
void Smallest_Difference_Triplet_From_Three_Arrays(int A[], int B[],
int C[], int n)
{
int difference = INT_MAX, sum =INT_MAX;
int a,b,c;
sort(A, A+n);
sort(B, B+n);
sort(C, C+n);
int i =0,j=0,k=0;
while (i < n && j < n && k < n)
{
int current_sum = A[i] + B[j] + C[k];
// maximum number
int maximum = max(max(A[i], B[j]), C[k]);
// Find minimum and increment its index.
int minimum = min(min(A[i], B[j]), C[k]);
int current_difference = maximum - minimum;
if (minimum == A[i])
i++;
else if (minimum == B[j])
j++;
else
k++;
// comparing new difference with the
// previous one and updating accordingly
if(current_difference<difference){
difference = current_difference;
sum = current_sum;
a = minimum;
b = sum - maximum - minimum;
c = maximum;
}
}
cout<<"Smallest Difference Triplet from Three arrays : ";
cout<<a<<", "<<b<<", "<<c<<endl;
}
// Driver program to test above
int main()
{
int arr1[] = {4, 3, 7};
int arr2[] = {21, 5, 11};
int arr3[] = {2, 6, 10};
int n = sizeof(arr1) / sizeof(arr1[0]);
Smallest_Difference_Triplet_From_Three_Arrays(arr1, arr2, arr3, n);
return 0;
}
You can also try this code with Online C++ Compiler
Smallest Difference Triplet from Three arrays : 4, 5, 6
Python
# Function to find and print the Smallest Difference Triplet From Three Arrays
def Smallest_Difference_Triplet_From_Three_Arrays(A, B, c, n):
# sorting all the three arrays
A.sort()
B.sort()
C.sort()
# To store resultant three numbers
a = 0; b = 0; c = 0
# pointers to arr1, arr2,
# arr3 respectively
i = 0; j = 0; k = 0
# Loop until one array reaches to its end
# Find the smallest difference.
difference = 2147483647 ;sum=0
while (i < n and j < n and k < n):
current_sum = A[i] + B[j] + C[k]
# maximum number
maximum = max(max(A[i], B[j]), C[k])
# Find minimum and increment its index.
minimum = min(min(A[i], B[j]), C[k])
current_difference = maximum - minimum
if (minimum == A[i]):
i += 1;
elif (minimum == B[j]):
j += 1
else:
k += 1
# Comparing new difference with the
# previous one and updating accordingly
if (current_difference < difference):
difference = current_difference
sum = current_sum
a = maximum
b = sum - (maximum + minimum)
c = minimum
# Print result
print("Smallest Difference Triplet from Three arrays : ",end=" ")
print(a, ", ", b, ", ", c)
# Driver code
arr1 = [4, 3, 7]
arr2 = [21, 5, 11]
arr3 = [2, 6, 10]
n = len(A)
Smallest_Difference_Triplet_From_Three_Arrays(arr1, arr2, arr3, n)
You can also try this code with Online Python Compiler
Smallest Difference Triplet from Three arrays : 4, 5, 6
Java
import java.util.*;
import java.lang.*;
import java.io.*;
// Function to find and print the Smallest Difference Triplet From Three Arrays
class CodingNInjas
{ static void
Smallest_Difference_Triplet_From_Three_Arrays(int A[],
int B[], int C[], int n)
{
// sorting all the three arrays
Arrays.sort(A);
Arrays.sort(B);
Arrays.sort(B);
// To store resultant three numbers
int a=0, b=0, c=0;
// pointers to A, B, C respectively
int i = 0, j = 0, k = 0;
// Loop until one array reaches to its end
// Find the smallest difference.
int difference = 2147483647;
int sum = 0;
while (i < n && j < n && k < n)
{
int current_sum = A[i] + B[j] + C[k];
// maximum number
int maximum = Math.max(Math.max(A[i], B[j]), C[k]);
// Find minimum and increment its index.
int minimum = Math.min(Math.min(A[i], B[j]), C[k]);
int current_difference = maximum - minimum;
if (minimum == A[i])
i++;
else if (minimum == B[j])
j++;
else
k++;
// comparing new difference with the
// previous one and updating accordingly
if (current_difference < difference)
{
difference = current_difference;
sum = current_sum;
a = minimum;
b = sum - (maximum + minimum);
c = maximum;
}
}
// Print result
System.out.print("Smallest Difference Triplet from Three arrays :");
System.out.print(a + ", " + b + ", " + c);
}
public static void main (String[] args) throws java.lang.Exception
{
int arr1[] = {4, 3, 7};
int arr2[] = {21, 5, 11};
int arr3[] = {2, 6, 10};
int n = arr1.length;
Smallest_Difference_Triplet_From_Three_Arrays(arr1, arr2, arr3, n);
}
}
You can also try this code with Online Java Compiler
Smallest Difference Triplet from Three arrays : 4, 5, 6
Complexity Analysis
Time Complexity: O(n*logn)
Explanation: In this approach, we are sorting the three arrays, so the complexity for sorting is O(n*logn) and traversing the arrays in a single loop with a complexity O(n).
The overall complexity we have is O(n*logn).
Space Complexity: O(1)because the variables used are of constant space, and no additional space is used here.
The max() function in C++ accepts two values and returns the larger one. This function is available in <algorithm. h>.
What is the time complexity for the optimized approach?
The time complexity for the optimized approach isO(n*logn) because we are sorting the three arrays, so the complexity for sorting is O(n*logn) and traversing the arrays in a single loop with a complexity O(n).
What is the space complexity for the optimized approach?
The space complexity is O(1)because the variables used in this approach are of constant space, and no additional space is used.
Conclusion
This article discussed the different approaches to find the Smallest Difference Triplet from Three arrays, starting with the brute first approach and then the efficient approach with examples and its C++, Java and Python code.
We hope this blog has helped you enhance your knowledge regarding the problem Smallest Difference Triplet from Three arrays. If you want to learn more about Interview questions, visit the links below: