3 Sum : Find triplets that add up to a target value

DevSniper
Published : 28 July 2024

155 Views

Array Coding Problems Google DSA Challange

Given an integer array arr, your task is to find all unique triplets [nums[i], nums[j], nums[k]] such that :-

The indices i, j and k are distinct (i.e. i != j, i != k, j != k).
The sum of the elements at these indices equals a target value (i.e. nums[i] + nums[j] + nums[k] == target)

Make sure that the solution set does not contain duplicate triplets.

Example 1 :-

arr : [1,4,3,5,6], target: 4

Output : []

Example 2 :-

arr = [-1,0,1,2,-1,-4], target : 0

Output : [[-1,-1,2],[-1,0,1]]

Example 3 :-

arr: [2,-2,1,3,5,0], target: 1

Output : [[2,-2,1],[-2,3,0]]

Constraints :

3 <= arr.length <= 3000
-10^5 <= arr[i] <= 10^5
The solution set does not contain duplicate triplets.
The order of the output and the order of the triplets does not matter.

Brute Force Approach

Brute force approach involves using nested loops for checking all possible combinations of three elements from the array and verifying if their sum matches the target value.

C++

Java

Python

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

vector<vector<int>> ThreeSum(int arr[],int n,int target)
{
    set<vector<int>> st;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                if (arr[i] + arr[j] + arr[k] == target) {
                    vector<int> temp = {arr[i], arr[j], arr[k]};
                    sort(temp.begin(), temp.end());
                    st.insert(temp);
                }
            }
        }
    }
    vector<vector<int>> result(st.begin(), st.end());
    return result;
}
int main()
{
    int arr[] = {10, -6,-3, 1, 2, 8, -2, -3};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 8;
    vector<vector<int>> ans =ThreeSum(arr,n,target);
    for (auto it : ans) {
        cout << "[";
        for (auto i : it) {
            cout << i << ", ";
        }
        cout << "] ";
    }
    return 0;
}

[-3, 1, 10, ] [-2, 2, 8, ]

Time Complexity : O(N^3)

Space Complexity : O(1)

Using Sorting and Two Pointers (Optimal Solution)

We can reduce the complexity of the algorithm after sorting the array and using two pointer technique.

C++

Java

Python

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

vector<vector<int>> ThreeSum(int arr[],int n,int target)
{
    vector<vector<int>> ans;
    sort(arr, arr + n);
    for (int i = 0; i < n; i++) {
        // remove duplicates:
        if (i != 0 &amp;&amp; arr[i] == arr[i - 1]) {
            continue;
        }
        // moving 2 pointers:
        int j = i + 1;
        int k = n- 1;
        while (j < k) {
            int sum = arr[i] + arr[j] + arr[k];
            if (sum < target) {
                j++;
            } else if (sum > target) {
                k--;
            } else {
                vector<int> temp = {arr[i], arr[j], arr[k]};
                ans.push_back(temp);
                j++;
                k--;
                // skip the duplicates:
                while (j < k &amp;&amp; arr[j] == arr[j - 1])
                    j++;
                while (j < k &amp;&amp; arr[k] == arr[k + 1])
                    k--;
            }
        }
    }
    return ans;
}
int main()
{
    int arr[] = {10, -6,-3, 1, 2, 8, -2, -3};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 8;
    vector<vector<int>> ans =ThreeSum(arr,n,target);
    for (auto it : ans) {
        cout << "[";
        for (auto i : it) {
            cout << i << ", ";
        }
        cout << "] ";
    }
    return 0;
}

[-3, 1, 10, ] [-2, 2, 8, ]

Time Complexity : O(N^2)

Space Complexity : O(1)

Template

C++