Understanding Algorithm: Complexity and Performance

Finding Array Triplets with Given Sum

Board Infinity
Board Infinity
Finding Array Triplets with Given Sum

    A quick guide to Asymptotic Analysis

    Searching Algorithm and its Types

    What is Hashing in Data Structure?

    How to Build a TreeMap?

    Difference between Hashmap and HashTable

    A Quick Guide to Bubble Sort Algorithm

    How to find the kth smallest/largest element in an array?

    How to use Merge Sort with Linked Lists

    Finding Array Triplets with Given Sum

    What Is An Algorithm (Understanding The Ingredients)

    Tail Recursion Problem

    Stack vs Heap Memory: Key Differences

    Algorithm and Flowchart: Differences Explained

    Big O Notation: Space and Time Complexity

    Graphs in Data Structure and Algorithm

    Time Complexity: Explanation

    Binary Search Tree: Explanation

    Heap Sort Algorithm

    Time Complexity of Sorting Algorithms

    Load Factor and Rehashing

Problem statement

You are given an array and a target value. Your task is to determine if there exists a triplet that sums to the target value. If there exists such a triplet in the array then print the triplet and return true, otherwise return false.

Some of the examples are given below:

Input 1

array = {4, 1, 3, 5, 6}, sum = 11

Output 1

4, 1 and 6

Explanation

The sum of 4, 1, and 6 is equal to 4 + 1 + 6 = 11.

Input 2

array = {2, 4, 1, 3, 5, 6}, sum = 13

Output 2

2, 5, and 6

Explanation

The sum of 2, 5, and 6 is equal to 2 + 5 + 6 = 13.

Naive approach

The naive approach to solve this problem is to generate all possible triplets and for each possible triplet compute the sum and compare with the target value. If it comes out to be equal to the target value then print the triplet.

Below is step by step process of this approach:

1. The input is an array of length N and the target sum is equal to S.

2. Create three nested loops.

3. In the outermost loop, iterate from index1 = 0 to index1 = N - 1.

4. In the second outermost loop, iterate from index2 = index1 + 1 to N - 1.

5. In the innermost loop, iterate from index2 + 1 to N - 1.

6. Now determine the sum of elements stored at indices: index1, index2, and index3. If the sum comes out to be equal to the target value then return this triplet and break.

7. If no such triplet exists, then return “Triplet not found!”.

Below is the implementation of this approach in C++:

Source Code

#include <bits/stdc++.h>
using namespace std;

bool findTriplet(int array[], int length, int target)
{
    // first element is array[i]
    for (int index1 = 0; index1 < length - 2; index1++)
    {
        // Second element is array[j]
        for (int index2 = index1 + 1; index2 < length - 1; index2++)
        {
            // Now find the third number
            for (int index3 = index2 + 1; index3 < length; index3++)
            {
                // Check if sum turns out to be equal to target
                if (array[index1] + array[index2] + array[index3] == target)
                {
                    cout << "Triplet is " << array[index1] <<
                        ", " << array[index2] << ", " << array[index3];
                    return true;
                }
            }
        }
    }
    // If we reach here, then no triplet was found
    return false;
}
int main() {
   
    // Initialize an array
    int array[] = { 4, 1, 3, 5, 6 };
   
    // target sum
    int target = 11;
    int length = sizeof(array) / sizeof(array[0]);
    bool answer = findTriplet(array, length, target);
   
    if(answer == false)
    {
        cout << "Triplet not found!";
    }
    return 0;
}

write your code here: Coding Playground

Output

The sum of 4, 1, and 6 is equal to 4 + 1 + 6 = 11.

Complexity analysis:

Time complexity - O(N^3), as we are iterating using three nested loops.

Auxiliary space - O(1), as no extra space is used.

Optimized approach

Now we will discuss the optimized approach to solve the triplet sum problem. The intuition is to sort the array first then we can use two pointers to find a pair and fix the first number (array[index]). In simple words, we can traverse the array and set the first element of the triplet. Now, we will use the two-pointers algorithm to determine the pair that sums equal to the target - array[index]. The two pointers method takes

Below is the implementation of this approach in C++:

Algorithm

1. The very step is to sort the given array.

2. Now iterate over the array and fix an element of the possible triplet, array[index].

3. Then, we need to fix two pointers, one at left = index + 1 and the other at right = N - 1 and then find the sum. Then follow the below given steps on the basis of this sum:

  • If the sum of the pair turns out to be equal to target - array[index] then this is the required triplet. Therefore, print the triplet.
  • If the sum of the pair comes out to be lesser than the target - array[index] then increment the left pointer by one.
  • If the sum of the pair comes out to be greater than the target - array[index] then decrement the right pointer by one.

Consider the following program that implements this approach in C++

Source Code

#include <bits/stdc++.h>
using namespace std;

bool findTriplet(int array[], int length, int target)
{
    int left, right;
   
    /* Sort the array */
    sort(array, array + length);
   
    /* Fix the first element and find the
       other two elements */
    for (int index = 0; index < length - 2; index++) {
        // Apply two pointer method
        left = index + 1;
        right = length - 1;
        while (left < right) {
            if (array[index] + array[left] + array[right] == target) {
                cout << "Triplet is " << array[index] << ", " << array[left] << ", " << array[right];
                return true;
            }
            else if (array[index] + array[left] + array[right] < target)
                left++;
            else // array[index] + array[left] + array[right] > target
                right--;
        }
    }
    // No triplet was found
    return false;
}
int main() {
   
    // Initialize an array
    int array[] = {2, 4, 1, 3, 5, 6};
   
    // target sum
    int target = 13;
    int length = sizeof(array) / sizeof(array[0]);
    bool answer = findTriplet(array, length, target);
   
    if(answer == false)
    {
        cout << "Triplet not found!";
    }
    return 0;
}

write your code here: Coding Playground

Output

Conclusion

In this article, we discussed how we can determine the triplet sum in an array. We discussed the naive approach first and then moved to the optimized approach.