Finding triplets with zero sum

user_10554702 0
Viewed 1243

I am trying to solve a problem in GeeksClasses and I am having an issue with my submission. My code works but they are saying Your program took more time than expected.

problem link: https://practice.geeksforgeeks.org/problems/find-triplets-with-zero-sum/1/?track=SPCF-Sorting&batchId=154

Problem statement:

Given an array of integers. Check whether it contains a triplet that sums up to zero.

Input:

The first line of input contains an integer T, denoting the number of test cases. Then T test cases follow. The first line of each test case contains an integer N, denoting the number of elements in array. The second line of each test case contains N space separated values of the array.

Output

For each test case, output will be 1 if triplet exists else 0

Expected Auxiliary Space: O(1)

Expected Time Complexity: O(n2)

Example:

Input:

2

5

0 -1 2 -3 1

3

1 2 3

Output:

1

0

Here is my code

def isPair(arr,left,right,u):
    while left < right:
        if arr[left] + arr[right] < u:
            left += 1
        elif arr[left] + arr[right] == u:
            return True
        elif arr[left] + arr[right] > u:
            right -= 1
    return False

def findTriplets(a,n):
    #code here
    a = sorted(a)
    for i in range(n):
        if isPair(a,i+1,n-1,0-a[i]):
            return 1
    return 0
#driver code
if __name__=='__main__':
    t=int(input())
    for i in range(t):
        n=int(input())
        a=list(map(int,input().strip().split()))
        print(findTriplets(a,n))
python-3.x python
2 Answers

That problem looks interesting, here are two observations we can use. Every valid triplet is of either form:

  1. (0, -x, x)
  2. or (x, y, z) such that x and y have opposite sign from z and x + y = - z

I'll consider a simpler form of input as most of your input is redundant with the content of the two lists of integers, ie. example_1 = [[0, -1, 2, -3, 1], [1, 2, 3]] should result in [1, 0].

Giving that I think the following is a decently fast/readable solution: 

from itertools import combinations

def solve_all(inputs):
    return [solve(i) for i in inputs]

def solve(single_input):
    input_set = set(single_input)
    negatives_set = set(-x for x in single_input if x < 0)
    positives_set = set(x for x in single_input if x > 0)

    if 0 in input_set and len(negatives_set & positives_set) > 0:
        return 1

    if any(sum(c) in positives_set for c in combinations(negatives_set, 2)):
        return 1

    if any(sum(c) in negatives_set for c in combinations(positives_set, 2)):
        return 1

    return 0
user_17201990 
public class FindTriplets{

    public static List<List<Integer>> findTriplets(int nums[]) {
        boolean found = false;
        List<Integer> triples = null;
        HashSet<Integer> set = null;
        HashSet<List<Integer>> tripleSet = new HashSet<List<Integer>>();
        for (int i = 0; i < nums.length - 1; i++) {         
            set = new HashSet<Integer>();
            for (int j = i + 1; j < nums.length; j++) {
                found = false;
                int x = -(nums[i] + nums[j]);
                if (set.contains(x)) {
                    Integer [] temp = {x,nums[i],nums[j]};
                    Arrays.sort(temp);
                    triples = new ArrayList<Integer>();
                    triples.add(temp[0]);
                    triples.add(temp[1]);
                    triples.add(temp[2]);
                    found = true;
                } else {
                    set.add(nums[j]);
                }               
                if(found==true){
                    tripleSet.add(triples);
                }               
            }
        }
        return new ArrayList<List<Integer>>(tripleSet);
    }

   public static void main(String[] args) {
        int arr[] = {0, -1, 2, -3, 1}; 
        //int arr[] = {-1, 0, 1, 2, -1, -4};
        List<List<Integer>> triplets = findTriplets(arr); 
        System.out.println("Triplets : "+triplets );                
    }
}
user_115279680
Related