Find pythagorean triplets in an array faster than O(N^2)?


  • 0
    H

    Input : int[] array = {3,7, 2,24,12,1,5,6,4,9,13,10,25}

    Expected Output with java toString :
    [[3, 4, 5], [5, 12, 13], [7, 24, 25]]

    List<List<Integer>> findPythagoreanTriplets(int[] array)  {
    //implement function here
    }

  • 0

    I guess it's pretty hard to get the complexity better than O(n^2), take a look at geeksforgeeks and stackoverflow.


  • 0
    F

    Here is a algorithm I think in most case is better than O(n^2) algorithm, I write it in C++ as follow:

    vector<vector<int> > pythagorean_triplets(vector<int> A) {
    int n = A.size();
    vector<vector<int> > ret;
    if( n<=2 ) {
    	return ret;
    }
    sort(A.begin(), A.end());
    unordered_map<int, bool> hash;
    for(int i = 0; i < n; ++i) {
    	A[i] *= A[i]; // calculate square value for elements in A
    	hash[A[i]] = true; // hash to mark elements in A
    }
    
    int maxA = A[n-1];
    int i = 0, j = n-1, k = 0;
    while(i<=j) {
    	for(k=i+1; k<=j && A[k]+A[i]<=maxA; ++k ) {
    		if(hash[A[k]+A[i]]) {
    			vector<int> tmp(3,0);
    			tmp[0] = (int)sqrt(A[i]);
    			tmp[1] = (int)sqrt(A[k]);
    			tmp[2] = (int)sqrt(A[i]+A[k]);
    			ret.push_back(tmp);
    		}
    	}
    	++i;
    	j=k-1;
    }
    return ret;}
    

    the idea behind this is that: after you sort the array, say you get A' from A, if A[i] + A[j] > maxL, where i < j, then there is no necessary for you to do further check started from j for range i to j, which means:

    firstly: for current loop, no need to check elements behind j

    secondly: for loop i+1, no need to check elements behind j

    so, just update new j in second loop, you will get a more tighter j.

    I cannot prove this, but I believe this algorithm is faster than O(n^2) in average case, but for worst case, it will be O(n^2), worst case happens when maxL > square second largest element + square third largest element.

    Moreover, the space complexity of algorithm could be improved from O(n)->O(1).


  • 0

    Yes, there is another way to find pythagorean triples maybe less than O(N^2), which use O(K) where K is the total number of triples with c less than the maximum value of in the given array. While c = sqrt(a^2+b^2).
    The solution is a modification of the code from here.
    The key is to generate the triples in the order of sqrt(a^2+b^2).

    public static List<int[]> findTriplets(int[] nums){
    	List<int[]> ret = new ArrayList<int[]>();
    	if (nums == null || nums.length <=2 ) return ret;
    	Set<Integer> set = new HashSet<>();
    	Set<Long> AB = new HashSet<Long>();
    	int max = Integer.MIN_VALUE;
    	for (int num: nums){
    		max = Math.max(max,num);
    		set.add(num);
    	}
    	int a, b, c=0;
    	int a1, b1, c1;
    	int m = 2;
    	while (c < max){
    		for (int n=1; n<m; n++){
    			a = m*m - n*n;
    			b = 2*m*n;
    			c = m*m + n*n;
    			if (c > max) break;
    			if (a > b) {
    				int temp = a;
    				a= b;
    				b= temp;
    			}
    			long code = (long)a<<32 + (long)b;
    			if (! AB.contains(code) ) {
    				AB.add(code);
    				if (set.contains(a) && set.contains(b) && set.contains(c)) {
    					ret.add(new int[]{a,b,c});
    					System.out.println(""+a+","+b+","+c);
    				}
    				for (int i=2; i*c <=max; i++) {
    					a1=a*i;
    					b1=b*i;
    					c1=c*i;
    					long code1 = (long)a1<<32 + (long)b1;
    					if (! AB.contains(code1) ) {
    						AB.add(code1);
    						if (set.contains(a1) && set.contains(b1) && set.contains(c1)) {
    							ret.add(new int[]{a1,b1,c1});
    							System.out.println(""+a1+","+b1+","+c1);
    						}
    					} else break;
    				}
    			}
    		}
    		m++;
    	}
    	return ret;
    }
    

  • 1
    M

    Putting out a no-brainer python, if you don't care about O(n):

    from itertools import combinations
    
    def answer(nums):
      sq_map = dict((num ** 2, num) for num in nums)
      return [(sq_map[x], sq_map[y], sq_map[x+y]) for x,y in combinations(sq_map, 2) if x+y in sq_map.keys()]
    

    Now I should go look into an optimum solution...


  • 1
    A

    I would argue that we cannot do better than O(n^2) as this problem has a lower bound Big-Omega(n^2) so to do better we need more information about the data. Otherwise, we can build a case which where the algorithm will fail.


  • 0
    D

    @hsjoshi1 said in Find pythagorean triplets in an array faster than O(N^2)?:

    int[] array = {3,7, 2,24,12,1,5,6,4,9,13,10,25}

    It return duplicate List but can be fixed using Set.

    List<List<Integer>> findPythagoreanTriplets(int[] input)  {
    
        // Sort the Numbers
        
        if(input == null){
            return null;
        }
        
        Map<Integer,Integer> store = new HashMap<>();
        
        List<List<Integer>> tripletsSuperList = new ArrayList<>();
        //O(n)
        for(int i=0; i< input.length ; i++) {
        	int temp = (int)Math.pow(input[i],2);
        	System.out.println(temp);
             store.put(input[i], temp);
        }
    
        //O(n)
        for(int i=0; i< input.length ; i++) {
             Integer firstNumber = input[i];
             Integer secondSqrt = null;
             if(store.keySet().contains(firstNumber+1)) {
            	 secondSqrt = store.get(firstNumber+1);
             }
             
             if(store.keySet().contains(firstNumber-1)) {
            	 secondSqrt = store.get(firstNumber-1);
             }
             
             
             if(secondSqrt != null) {
    
                 Integer thirdNumberSqRt = Math.abs(store.get(firstNumber) - secondSqrt);
                 if(Math.sqrt(thirdNumberSqRt) == (int)Math.sqrt(thirdNumberSqRt) && store.get((int)Math.sqrt(thirdNumberSqRt)) != null){
                      List<Integer> tripletsSubList = new ArrayList<>();
                      tripletsSubList.add(firstNumber);
                      tripletsSubList.add((int)Math.sqrt(secondSqrt));
                      tripletsSubList.add((int)Math.sqrt(thirdNumberSqRt));
                      tripletsSuperList.add(tripletsSubList);
                 }
                  
             }
        
        }
        return tripletsSuperList;
    }

  • 0
    S

    From 3SUM

    the current best known algorithm for 3SUM runs in O( n^2 / (log(n)/ log(log(n)) ) time

    Improved sub-quadratic 3SUM

    However I am not interested to purchase that article. Hoping for someone who has extra bucks to spare and willing to share it with others for free (provided it is not patented knowledge)

    Did LinkedIn interviewer specified that (s)he wants 3SUM faster than O (n^2), complexity specification is somewhat unusual.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.