CODEWITHSUNDEEP
javaalgorithm
tsure
tsure

Reputation: 315

Pairs in a list

What is the most optimal way to find unique pairs of all numbers in a list in Java? I have a solution where I convert the list into an array and then basically pair the first element with 2nd , then first with 3rd and so on.. However, this turns out to be O(n^2). Here is my basic pseudo code:

int arr[] = convertListToArray(arrList) 
   for i=1;i< arr.length; i++
     for j =1+1; j<arr.length; j++
          print arr[i] , arr[j]

This is clearly o(n^2). Can this be done in a better way?

Upvotes: 2

Views: 147

Answers (3)

Harmlezz
Harmlezz

Reputation: 8058

This code finds duplicates in O(n). Adding an item to a HashSet takes O(1). We add n items, hence it takes O(n). here you go:

public static void main(String[] args) throws Exception {
    List<Integer> list = Arrays.asList(new Integer[] { 1, 2, 3, 4, 5, 6, 2, 4, 6 });
    Set<Integer> set = new HashSet<>();
    for (Integer value : list) {
        if (!set.add(value)) System.out.printf("%d is at least a duplicate\n", value);
    }
}

Upvotes: 0

Trygve Flathen
Trygve Flathen

Reputation: 696

Assuming there are no duplicates, there will be N choose 2 = N(N-1)/2 different pairs, which is clearly O(N^2). Avoiding duplicates can be done by first removing duplicates in the original list (this would be an additional O(N log N) operation). Note that this would remove any pairs of equal values though.

Upvotes: 0

Tim B
Tim B

Reputation: 41168

There are some tricks you can do in some situations if the number set is constrained. Fundamentally your problem is n^2 though so in the general case you don't have many alternatives.

If you only need unique pairs then you can remove duplicates from the List (for example by dumping it into a Set then back out again) and then iterate over it.

Iterating over all unique pairs would then be:

for (int i=0;i<len;i++) {
    for (j=i+1;j<len;j++) {
    }
}

Note that j loops from i+1 onwards so this is a bit better than the n^2 case although it is still non-linear growth.

Upvotes: 5

Related Questions