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 = 0
arr[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
Syed Jafer K 