Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Example
4.
Brute Force Approach
4.1.
Steps of Algorithm
4.2.
Pseudocode
4.2.1.
Complexity Analysis
5.
Optimized Approach
5.1.
Steps of Algorithm   
5.2.
Implementation
5.2.1.
Complexity Analysis
6.
Frequently Asked Questions
6.1.
How does the sizeof() function in C++?
6.2.
How does the sort function work?
6.3.
What is Max function C++?
6.4.
What is the time complexity for the optimized approach?
6.5.
What is the space complexity for the optimized approach?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

Smallest Difference Triplet from Three arrays

Author Anju Jaiswal
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

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.             

smallest difference triplet from three arrays

Recommended topic, kth largest element in an array and  Euclid GCD Algorithm

Problem Statement

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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.

    

Smallest Difference Triplet from Three arrays algorithm
  • 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).

 

Smallest Difference Triplet from Three arrays algorithm
  • 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   

  1. Sorting the three arrays in non decreasing order.
  2. Use Three-pointers and start from the left-most members of three arrays (i,j,k).
  3. Now find minimum element and maximum element from the present triplet, calculate the absolute current difference between maximum and minimum element(max-min)  
  4. And compare the current_difference with the value of resultant difference till now and update the value.
  5. Now increment pointer of minimum element’s array.
  6. 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).
  7. Finally, print the final result.
Smallest Difference Triplet from Three arrays algorithm

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


Output

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)

Output

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

    }
}

Output

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.

Check out this problem - Pair Sum In Array.

Frequently Asked Questions

How does the sizeof() function in C++?

The sizeof keyword is a compile-time operator for determining the size of a variable or data type in bytes.

Syntax: sizeof (data type)

How does the sort function work?

Sorting means arranging the data in a particular fashion, increasing or decreasing. There is a built-in function in C++ STL called sort().

Syntax - sort(startaddress, endaddress, comparator)

What is Max function C++?

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:

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem DesignMachine learning and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!!

Previous article
Check if reversing a sub-array make the array sorted
Next article
Suffix Array Construction (Brute Force N ^ 2 LogN)
Live masterclass