How can I improve the time complexity of the following program " Remove duplicates from an array"?

Question

I am new to Data Structures and Algorithms. I was working on a problem set which is basically to remove duplicates from an array and return the array without the duplicates. My goal was to design an efficient algorithm which can solve this problem. I used the approach of writing a Naive code and then finding various ways to improve the time complexity of the code. Currently, the code I wrote has a time complexity of O(n^2). So, I was wondering if someone can kindly point out the possible improvements on my code so that I can bring down the time complexity from O(n^2) to O(nlogn) or O(n) if possible. Please I am trying to approach this problem without sorting the array. Thanks.

public class MainClass {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
       int [] a= {1,7,7,7,9,9,10,10,10,11,11,1};
        removeduplicates(a);




    }

    public static void removeduplicates(int[]a)
    {
        int flag=0;
        int b =0;
        int k=0;
        int [] temp = new int[a.length];
        for(int i=0;i<a.length;i++)
        {
            int key = a[i];
            for(int j=i+1;j<a.length;j++)
            {
                if(key==a[j])
                {
                    flag++;

                }
            }

            if(flag==0)
            {
                temp[k] = key;
                k++;

            }

            else
            {
                for( int m=0;m<temp.length;m++)
                {
                    if(key==temp[m])
                    {
                        b++;
                    }
                }

                if(b==0)
                {
                    temp[k] = key;
                    k++;
                }
            }

            b = 0;
        }

        for(int i=0;i<k;i++)
            System.out.print(temp[i] +"\t");

    }


}

// The following code is a improvement on the above code with a time complexity of O(n). Thanks @Bohemian for the suggestions:-

import java.util.HashSet;


public class MainClass {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
          HashSet<Integer> hs = new HashSet<Integer>();
           int [] a= {1,7,7,7,9,9,10,10,10,11,11,1};

           for(int i=0;i<a.length;i++)
           {
              hs.add(a[i]);
           }

           Integer [] rtrn = new Integer[hs.size()];
           rtrn = hs.toArray(rtrn);

           for(int i=0;i<rtrn.length;i++)
               System.out.print(rtrn[i] +"\t");

    }

}

Answer 1

An O(n) solution in pseudo code is:

• create a HashSet
• for each value, discard it if the set already contains it

Because all operations on a HashSet are O(1), and you do n of these, the overall complexity is O(n).

You may find this line useful:

if (!set.add(i)) continue;

The add() method of a set returns true if the set was modified by the operation (ie if it didn't already contain the value).