How to remove duplicate pairs from an ArrayList in Java?

Question

I've an ArrayList which contains pairs of integers( say int i, int j). But it may be contains duplicates pairs (like (int i, int j) and (int j, int i)). Now how can I remove duplicates from it in O(n) time complexity.

Updated code:

class Pair
{
    int i, j;
    Pair(int i,int j){
        this.i=i;
        this.j=j;
    }

}

public class My 
{
    public static void main(String[] args) {
        Pair p;
        List> src = Arrays.asList(new Pair(1,2), 
            new Pair(2,3), new Pair(2,1),new Pair(1,2));
        HashSet dest  = new HashSet();

        for(int i=0; i < src.size(); i++) {
            p=src.get(i);
            if(dest.contains(p.j+" "+p.i)) {
                System.out.println("duplicacy");
            }  
            else {
                dest.add(p.i+" "+p.j);
            }
         
        }
        System.out.println("set is = "+dest);
     
        List> ans=new ArrayList();
        String temp;
        int i,j;
        Iterator it=dest.iterator();
        while(it.hasNext()) 
        {
            temp=it.next();
            i=Integer.parseInt(temp.substring(0,temp.indexOf(' ')));
            j=Integer.parseInt(temp.substring(temp.indexOf(' 
               ')+1,temp.length()));
            ans.add(new Pair(i,j));
         }
    
         for(Pair i_p:ans) {
             System.out.println("Pair = "+i_p.i+" , "+i_p.j);
         }

     }//end of main method
 }//end of class My

This code is working fine but I want to know it performance wise, I mean its overall time complexity ?

user_13415164 · Answer

Make only one loop throught list of Pairs and collect by the way in HashSet processed pair and it's reversed copy:

List> lp = Arrays.asList(new Pair(1,2),
                                               new Pair(2,3),
                                               new Pair(1,2),
                                               new Pair(2,1));
Set> sp = new HashSet<>();

List> ulp = lp.stream()
                                    .collect(ArrayList::new,
                                             (l,p)-> { Pair p1 = new Pair(p.getValue(), p.getKey());
                                                       if (!(sp.contains(p))&&!(sp.contains(p1))){
                                                           l.add(p);
                                                           sp.add(p);
                                                           sp.add(p1);
                                                        }} , List::addAll);

System.out.println(ulp);

user_13312820 · Answer

If you can modify Pair class, just implement equals() and hashCode():

public class Pair {
    private int a;
    private int b;

    public Pair(int a, int b) {
        this.a = a;
        this.b = b;
    }

    @Override
    public boolean equals(Object o) { 
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Pair pair = (Pair) o;
        return (a == pair.a && b == pair.b) || (a == pair.b && b == pair.a);
    }

    @Override
    public int hashCode() {
        return Objects.hashCode(new HashSet<>(Arrays.asList(a,b))); 
    }

    @Override
    public String toString() {
        return "Pair{" +
                "a=" + a +
                ", b=" + b +
                '}';
    }
}

Then just create a new Set:

List pairs = Arrays.asList(new Pair(1, 2), new Pair(2, 1), new Pair(3, 2));

Set pairSet = new HashSet<>(pairs);

System.out.println(pairSet);

Output:

[Pair{a=1, b=2}, Pair{a=3, b=2}]

If you can't modify Pair class:

List pairs = Arrays.asList(new Pair(1, 2), new Pair(2, 1), new Pair(3, 2));

Set pairSet = pairs.stream()
      .map(pair -> new HashSet<>(Arrays.asList(pair.getA(), pair.getB())))
      .distinct()
      .map(integers -> {
          Iterator iterator = integers.stream().iterator();
          return new Pair(iterator.next(), iterator.next());
      })
      .collect(Collectors.toSet());

System.out.println(pairSet);

Output:

[Pair{a=1, b=2}, Pair{a=2, b=3}]

If you want, you can convert your Set back to a list:

List list = new ArrayList<>(set);

But it's most likely unnecessary.

user_2527458 · Answer

Since the contains() of HashSet runs in O(1) time (See this and other references) you can use the following method which is the overall O(n):

import java.util.*;
import javafx.util.*;

public class Main
{
    public static void main(String[] args) {
           List> src = Arrays.asList(new Pair(1,2), new Pair(2,3), new Pair(2,1));
           HashSet> dest  = new HashSet();

            for(int i=0; i < src.size(); i++) {
                if(dest.contains(src.get(i)) || 
                    dest.contains(new Pair(src.get(i).getValue(),src.get(i).getKey()))) {
                    
                }else {
                    dest.add(src.get(i));
                }
            }
            
            System.out.println(dest);

    }
}

EDIT 1:

You can use Map.Entry instead of javafx.util.pair. Do the program without Javafx is as follow.

import java.util.*;

public class Main
{
    public static void main(String[] args) {
           List> src = Arrays.asList(new AbstractMap.SimpleEntry(1,2), 
                new AbstractMap.SimpleEntry(2,3), new AbstractMap.SimpleEntry(2,1));
           HashSet> dest  = new HashSet();

            for(int i=0; i < src.size(); i++) {
                if(dest.contains(src.get(i)) || 
                    dest.contains(new AbstractMap.SimpleEntry(src.get(i).getValue(),src.get(i).getKey()))) {
                    
                }else {
                    dest.add(src.get(i));
                }
            }
            
            System.out.println(dest);

    }
}

How to remove duplicate pairs from an ArrayList in Java?

Updated code:

3 Answers