Go To Problem

Find All Triplets with Zero Sum

Medium

Points: 4

Given an array arr[], find all possible triplets i, j, k in the arr[] whose sum of elements is equals to zero.

Returned triplet should also be internally sorted i.e. i<j<k.

💡Example 1:

Input:
  arr[] = [0, -1, 2, -3, 1]
Output: 
  [[0, 1, 4], [2, 3, 4]]
Explanation:Triplets with sum 0 are:
  arr[0] + arr[1] + arr[4] = 0 + (-1) + 1 = 0
  arr[2] + arr[3] + arr[4] = 2 + (-3) + 1 = 0

💡Example 2:

Input:
  arr[] = [1, -2, 1, 0, 5]
Output:
  [[0, 1, 2]]
Explanation:  Only triplet which satisfies the condition is arr[0] + arr[1] + arr[2] = 1 + (-2) + 1 = 0

💡Example 3:

Input:
  arr[] = [2, 3, 1, 0, 5]
Output:
  [[]]
Explanation: There is no triplet with sum 0.

Expected Time Complexity:

O(n^2)

Expected Space Complexity:

O(n^2)

Constraints:

3 <= arr.size() <= 10^3

-10^4 <= arr[i] <= 10^4

Topic Tags:

Complete Code [Links]:

• C++ Code
• Java Code
• Python Code
• Javascript Code

Main Code :

C++ Code:

//Time Complexity : O(n^3)
//Space Complexity : O(n^3)
class Solution {
  public:
    vector<vector<int>> findTriplets(vector<int> &arr) {
        // Code here
        int len = arr.size();
        std::vector<std::vector<int>> res;
        for (int i = 0; i < len - 2; i++) {
            for (int j = i + 1; j < len - 1; j++) {
                for (int k = j + 1; k < len; k++) {
                    if (arr[i] + arr[j] + arr[k] == 0) {
                        res.push_back({i, j, k});
                    }
                }
            }
        }
        return res;
    }
};

Java Code:

//Time Complexity : O(n^3)
//Space Complexity : O(n^3)
class Solution {
    public List<List<Integer>> findTriplets(int[] arr) {
        // Your code here
        int len=arr.length;
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < len - 2; i++)
            for (int j = i + 1; j < len - 1; j++)
                for (int k = j + 1; k < len; k++)
                    if (arr[i] + arr[j] + arr[k] == 0) res.add(Arrays.asList(i, j, k));
        return res;
    }
    
}

Python Code:

#Space Complexity: O(n²) 
#Time Complexity: O(n²)
class Solution:
    def findTriplets(self, arr):
        n, result, pair_sum_map = len(arr), set(), {}

        for i in range(n):
            for j in range(i + 1, n):
                pair_sum_map.setdefault(arr[i] + arr[j], []).append((i, j))

        for i in range(n):
            for pair in pair_sum_map.get(-arr[i], []):
                if i not in pair:
                    result.add(tuple(sorted([i, *pair])))

        return [list(triplet) for triplet in sorted(result)]

JavaScript Code:

//Time Complexity : O(n^3)
//Space Complexity : O(n^3)
class Solution {
    findTriplets(arr) {
        const res = [];
        const len = arr.length;
        for (let i = 0; i < len - 2; i++) {
            for (let j = i + 1; j < len - 1; j++) {
                for (let k = j + 1; k < len; k++) {
                    if (arr[i] + arr[j] + arr[k] === 0) {
                        res.push([i, j, k]);
                    }
                }
            }
        }

        return res;
    }
}