POTD #8 - Find All Triplets with Zero Sum | Geeks For Geeks

{% raw %}

Problem Statement

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.

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 = 0arr[2] + arr[3] + arr[4] = 2 + (-3) + 1 = 0

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

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

My Approach

• Created a dict with val as key and index as value, after iterating through the array.
• Started iterating the array, and another iteration from the next index position.
• a + b + c = 0. I need to check c (c = 0 – a – b). Will check if c is in dict.
• if c is in dict, then will sort a,b,c and store in result set.

class Solution:    def findTriplets(self, arr):        # Your code here        hash_set = {}        index = 0        total = len(arr)        result = []        result_set = {}                for itr in range(total):            hash_set[arr[itr]] = itr                for first in range(total):            for itr in range(first+1, total):                rem = 0 - arr[itr] - arr[first]                if hash_set.get(rem) is not None and hash_set.get(rem) != first and hash_set.get(rem) != itr:                    val = [first, itr, hash_set.get(rem)]                    val.sort()                    if result_set.get(tuple(val)) is None:                        result_set[tuple(val)] = True                        result.append(val)                        return result

{% endraw %}