Triplet Sum in Array (3sum) using Two pointer technique

By Sorting the array the efficiency of the algorithm can be improved. This efficient approach uses the two-pointer technique. Traverse the array and fix the first element of the triplet. Now use the Two Pointers algorithm to find if there is a pair whose sum is equal to x – array[i]. Two pointers algorithm take linear time so it is better than a nested loop.

Step-by-step approach:

Sort the given array.
Loop over the array and fix the first element of the possible triplet, arr[i].
Then fix two pointers, one at i + 1 and the other at n – 1. And look at the sum,
- If the sum is smaller than the required sum, increment the first pointer.
- Else, If the sum is bigger, Decrease the end pointer to reduce the sum.
- Else, if the sum of elements at two-pointer is equal to given sum then print the triplet and break.

Below is the implementation of the above approach:

C++

// C++ program to find a triplet
#include <bits/stdc++.h>
using namespace std;
 
// returns true if there is triplet with sum equal
// to 'sum' present in A[]. Also, prints the triplet
bool find3Numbers(int A[], int arr_size, int sum)
{
    int l, r;
    /* Sort the elements */
    sort(A, A + arr_size);
    /* Now fix the first element one by one and find the
       other two elements */
    for (int i = 0; i < arr_size - 2; i++) {
 
        // To find the other two elements, start two index
        // variables from two corners of the array and move
        // them toward each other
        l = i + 1; // index of the first element in the
        // remaining elements
        r = arr_size - 1; // index of the last element
        while (l < r) {
            if (A[i] + A[l] + A[r] == sum) {
                printf("Triplet is %d, %d, %d", A[i], A[l],A[r]);
                return true;
            }
            else if (A[i] + A[l] + A[r] < sum)
                l++;
            else // A[i] + A[l] + A[r] > sum
                r--;
        }
    }
    // If we reach here, then no triplet was found
    return false;
}
 
/* Driver program to test above function */
int main()
{
    int A[] = { 1, 4, 45, 6, 10, 8 };
    int sum = 22;
    int arr_size = sizeof(A) / sizeof(A[0]);
    find3Numbers(A, arr_size, sum);
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

C

// C program to find a triplet
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 
int cmpfunc(const void* a, const void* b)
{
    return (*(int*)a - *(int*)b);
}
 
// returns true if there is triplet with sum equal
// to 'sum' present in A[]. Also, prints the triplet
bool find3Numbers(int A[], int arr_size, int sum)
{
    int l, r;
   
    /* Sort the elements */
    qsort(A, arr_size, sizeof(int), cmpfunc);
   
    /* Now fix the first element one by one and find the
       other two elements */
    for (int i = 0; i < arr_size - 2; i++)
    {
       
        // To find the other two elements, start two index
        // variables from two corners of the array and move
        // them toward each other
        l = i + 1; // index of the first element in the
        // remaining elements
        r = arr_size - 1; // index of the last element
        while (l < r) {
            if (A[i] + A[l] + A[r] == sum) {
                printf("Triplet is %d, %d, %d", A[i], A[l],
                       A[r]);
                return true;
            }
            else if (A[i] + A[l] + A[r] < sum)
                l++;
            else // A[i] + A[l] + A[r] > sum
                r--;
        }
    }
   
    // If we reach here, then no triplet was found
    return false;
}
 
/* Driver program to test above function */
int main()
{
    int A[] = { 1, 4, 45, 6, 10, 8 };
    int sum = 22;
    int arr_size = sizeof(A) / sizeof(A[0]);
    find3Numbers(A, arr_size, sum);
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

Java

// Java program to find a triplet
class FindTriplet {
 
    // returns true if there is triplet with sum equal
    // to 'sum' present in A[]. Also, prints the triplet
    boolean find3Numbers(int A[], int arr_size, int sum)
    {
        int l, r;
 
        /* Sort the elements */
        quickSort(A, 0, arr_size - 1);
 
        /* Now fix the first element one by one and find the
           other two elements */
        for (int i = 0; i < arr_size - 2; i++) {
 
            // To find the other two elements, start two
            // index variables from two corners of the array
            // and move them toward each other
            l = i + 1; // index of the first element in the
                       // remaining elements
            r = arr_size - 1; // index of the last element
            while (l < r) {
                if (A[i] + A[l] + A[r] == sum) {
                    System.out.print("Triplet is " + A[i] + ", " + A[l] + ", " + A[r]);
                    return true;
                }
                else if (A[i] + A[l] + A[r] < sum)
                    l++;
 
                else // A[i] + A[l] + A[r] > sum
                    r--;
            }
        }
 
        // If we reach here, then no triplet was found
        return false;
    }
 
    int partition(int A[], int si, int ei)
    {
        int x = A[ei];
        int i = (si - 1);
        int j;
 
        for (j = si; j <= ei - 1; j++) {
            if (A[j] <= x) {
                i++;
                int temp = A[i];
                A[i] = A[j];
                A[j] = temp;
            }
        }
        int temp = A[i + 1];
        A[i + 1] = A[ei];
        A[ei] = temp;
        return (i + 1);
    }
 
    /* Implementation of Quick Sort
    A[] --> Array to be sorted
    si  --> Starting index
    ei  --> Ending index
     */
    void quickSort(int A[], int si, int ei)
    {
        int pi;
 
        /* Partitioning index */
        if (si < ei) {
            pi = partition(A, si, ei);
            quickSort(A, si, pi - 1);
            quickSort(A, pi + 1, ei);
        }
    }
 
    // Driver program to test above functions
    public static void main(String[] args)
    {
        FindTriplet triplet = new FindTriplet();
        int A[] = { 1, 4, 45, 6, 10, 8 };
        int sum = 22;
        int arr_size = A.length;
 
        triplet.find3Numbers(A, arr_size, sum);
    }
}

Python3

# Python3 program to find a triplet
 
# returns true if there is triplet
# with sum equal to 'sum' present
# in A[]. Also, prints the triplet
def find3Numbers(A, arr_size, sum):
 
    # Sort the elements 
    A.sort()
 
    # Now fix the first element 
    # one by one and find the
    # other two elements 
    for i in range(0, arr_size-2):
     
 
        # To find the other two elements,
        # start two index variables from
        # two corners of the array and
        # move them toward each other
         
        # index of the first element
        # in the remaining elements
        l = i + 1
         
        # index of the last element
        r = arr_size-1
        while (l < r):
         
            if( A[i] + A[l] + A[r] == sum):
                print("Triplet is", A[i], 
                     ', ', A[l], ', ', A[r]);
                return True
             
            elif (A[i] + A[l] + A[r] < sum):
                l += 1
            else: # A[i] + A[l] + A[r] > sum
                r -= 1
 
    # If we reach here, then
    # no triplet was found
    return False
 
# Driver program to test above function 
A = [1, 4, 45, 6, 10, 8]
sum = 22
arr_size = len(A)
 
find3Numbers(A, arr_size, sum)
 
# This is contributed by Smitha Dinesh Semwal

C#

// C# program to find a triplet
using System;
 
class GFG {
 
    // returns true if there is triplet
    // with sum equal to 'sum' present
    // in A[]. Also, prints the triplet
    bool find3Numbers(int[] A, int arr_size,
                      int sum)
    {
        int l, r;
 
        /* Sort the elements */
        quickSort(A, 0, arr_size - 1);
 
        /* Now fix the first element 
    one by one and find the
    other two elements */
        for (int i = 0; i < arr_size - 2; i++) {
 
            // To find the other two elements,
            // start two index variables from
            // two corners of the array and
            // move them toward each other
            l = i + 1; // index of the first element
            // in the remaining elements
            r = arr_size - 1; // index of the last element
            while (l < r) {
                if (A[i] + A[l] + A[r] == sum) {
                    Console.Write("Triplet is " + A[i] + ", " + A[l] + ", " + A[r]);
                    return true;
                }
                else if (A[i] + A[l] + A[r] < sum)
                    l++;
 
                else // A[i] + A[l] + A[r] > sum
                    r--;
            }
        }
 
        // If we reach here, then
        // no triplet was found
        return false;
    }
 
    int partition(int[] A, int si, int ei)
    {
        int x = A[ei];
        int i = (si - 1);
        int j;
 
        for (j = si; j <= ei - 1; j++) {
            if (A[j] <= x) {
                i++;
                int temp = A[i];
                A[i] = A[j];
                A[j] = temp;
            }
        }
        int temp1 = A[i + 1];
        A[i + 1] = A[ei];
        A[ei] = temp1;
        return (i + 1);
    }
 
    /* Implementation of Quick Sort
A[] --> Array to be sorted
si --> Starting index
ei --> Ending index
*/
    void quickSort(int[] A, int si, int ei)
    {
        int pi;
 
        /* Partitioning index */
        if (si < ei) {
            pi = partition(A, si, ei);
            quickSort(A, si, pi - 1);
            quickSort(A, pi + 1, ei);
        }
    }
 
    // Driver Code
    static void Main()
    {
        GFG triplet = new GFG();
        int[] A = new int[] { 1, 4, 45, 6, 10, 8 };
        int sum = 22;
        int arr_size = A.Length;
 
        triplet.find3Numbers(A, arr_size, sum);
    }
}
 
// This code is contributed by mits

Javascript

<script>
 
// Javascript program to find a triplet
 
// returns true if there is triplet with sum equal
// to 'sum' present in A[]. Also, prints the triplet
function find3Numbers(A, arr_size, sum)
{
    let l, r;
 
    /* Sort the elements */
    A.sort((a,b) => a-b);
 
    /* Now fix the first element one 
    by one and find the
    other two elements */
    for (let i = 0; i < arr_size - 2; i++) {
 
        // To find the other two
        // elements, start two index
        // variables from two corners of 
        // the array and move
        // them toward each other
         
        // index of the first element in the
        l = i + 1; 
         
        // remaining elements
         
       // index of the last element
        r = arr_size - 1; 
        while (l < r) {
            if (A[i] + A[l] + A[r] == sum) 
            {
            document.write("Triplet is " + A[i] + ", "
                  + A[l] + ", " + A[r]);
                return true;
            }
            else if (A[i] + A[l] + A[r] < sum)
                l++;
            else // A[i] + A[l] + A[r] > sum
                r--;
        }
    }
 
    // If we reach here, then no triplet was found
    return false;
}
 
/* Driver program to test above function */
 
    let A = [ 1, 4, 45, 6, 10, 8 ];
    let sum = 22;
    let arr_size = A.length;
 
    find3Numbers(A, arr_size, sum);
 
 
// This code is contributed by Mayank Tyagi
 
</script>

PHP

<?php
// PHP program to find a triplet
 
// returns true if there is 
// triplet with sum equal to
// 'sum' present in A[]. Also,
// prints the triplet
function find3Numbers($A, $arr_size, $sum)
{
    $l; $r;
 
    /* Sort the elements */
    sort($A);
 
    /* Now fix the first element 
    one by one and find the
    other two elements */
    for ($i = 0; $i < $arr_size - 2; $i++) 
    {
 
        // To find the other two elements, 
        // start two index variables from 
        // two corners of the array and 
        // move them toward each other
        $l = $i + 1; // index of the first element 
                     // in the remaining elements
 
        // index of the last element
        $r = $arr_size - 1; 
        while ($l < $r) 
        {
            if ($A[$i] + $A[$l] + 
                $A[$r] == $sum)
            {
                echo "Triplet is ", $A[$i], " ",
                                    $A[$l], " ", 
                                    $A[$r], "\n";
                return true;
            }
            else if ($A[$i] + $A[$l] +
                     $A[$r] < $sum)
                $l++;
            else // A[i] + A[l] + A[r] > sum
                $r--;
        }
    }
 
    // If we reach here, then
    // no triplet was found
    return false;
}
 
// Driver Code
$A = array (1, 4, 45, 6, 10, 8);
$sum = 22;
$arr_size = sizeof($A);
 
find3Numbers($A, $arr_size, $sum);
 
// This code is contributed by ajit
?>

Output

Triplet is 4, 8, 10

Complexity Analysis:

Time complexity: O(N^2), There are only two nested loops traversing the array, so time complexity is O(n^2). Two pointers algorithm takes O(n) time and the first element can be fixed using another nested traversal.
Auxiliary Space: O(1), As no extra space is required.

Triplet Sum in Array (3sum) using Two pointer technique

C++

C

Java

Python3

C#

Javascript

PHP

Triplet Sum in Array (3sum)

Categories

Contact US

Triplet Sum in Array (3sum) using Two pointer technique

C++

C

Java

Python3

C#

Javascript

PHP

Triplet Sum in Array (3sum)

Similar Reads

Categories

Contact US