complexity of removing the duplicate element from a list which contain a pair of integer

user_15163166 0
Viewed 62

I have a list containing pairs of integer example -> [{1,2},{2,3},{2,1}]

I want to remove the duplicate elements from it like (1,2) and (2,1) is same.

Here is my code ->

class Pair<t1,t2>
{
    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<Pair<Integer,Integer>> src = Arrays.asList(new Pair(1,2), 
            new Pair(2,3), new Pair(2,1),new Pair(1,2));
        HashSet<String> 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<Pair<Integer,Integer>> ans=new ArrayList();
        String temp;
        int i,j;
        Iterator<String> 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

Here I have first convert the 2 integers into single string then insert it into hashset. Can someone please tell me the performance and time complexity of above code ?

java
2 Answers

QUICK REVIEW:

set: set interface extends collection interface. in a set, no duplicates are allowed. every element in a set must be unique.

hashset: is implemented using a hash table. elements are not ordered. the add, remove, and contains methods has constant time complexity O(1).

To answer your question, let us keep it in mind that we will only be concerned about the most expensive of any operation meaning that if some part of our code has a time complexity of o(n) and another o(n^2) then we will pick o(n^2) instead of o(n) reason being that it's the most expensive we're worried about.

First, let's talk about the space complexity as it's easy to spot, from your code you have three variables that stores larger data:

  1. src
  2. dest
  3. ans

The first basically have space complexity of s(n) n being the original size of your data unfiltered(not unique). in your sample above s(4) = 4, note: it means 4 * the datatype size you're using, if for example, you're storing a list of integer, you will say s(4(int)) = 4*(4bytes) = 16bytes of space.

The second following the same analogy above means we have the size of "src", "minus the duplicates" s(n) = 4 - 2(duplicates) = 2*(datatype size in bytes/bits)

The third basically just stores the values from "dest" in pairs, so we should have basically the same size but with datatype difference.

That's just a basic translation of the space complexity, so following our rules we will keep the highest of the sizes. So, our space complexity is s(n*(datatype size)), it's safe to just say s(n).

For the time complexity, following the same rules, we need the most expensive operation in terms of time, and that's the for loop performed on "src" which is the size of any data we're working on in this case 4, so we can say our time complexity is o(n).

Summary of your algorithm:

Space Complexity: s(n)

Time complexity: o(n)

Performance is relatively on average.

user_53652270

Since HashSet uses O(1) for contains method, your time complexity is 3N+c which N is size of input pairs and c is constant. So the overall time complexity is O(N). However you can improve your code by avoiding unnecessary loops.

Your space complexity is also 3N+c which is in order of O(N). However you can improve this too.

I suggest extend your pair class to include an equal method.

class Pair<t1,t2>
{
    int i, j;
    Pair(int i,int j){
        this.i=i;
        this.j=j;
    }

    public int getI() { return i;}
    public int getJ() { return j;}
    
   // Overriding equals() to compare two Complex objects
    @Override
    public boolean equals(Object o) {
  
        // If the object is compared with itself then return true  
        if (o == this) {
            return true;
        }

        Pair c = (Pair) o;
        if( (i==c.getI() && j==c.getJ() ) ||
            (i==c.getJ() && j==c.getI() ) ) {
             return true;
         }else {
            return false;
         }

}
user_25274580
Related