CareerCup

Hashing might give the average complexity of O(N). The worst case is O(N*N). You ask why?
Imagine this-
array[] = 7, 14, 21, 28, 35, 42, 49
If you mod by the array length (7). It would mean all these would be colliding into bucket 0. Thus insertion of elements( or checking for duplicates takes- 0 + 1 + 2+ 3 + 4+ 5+ 6 = 21 steps).
I think sorting is the best general purpose option.

Solution with Time Complexity "n log(n)" and with no extra space.

import java.util.Arrays;

        Integer[] input_arr = {3,2,1,3,2,5,5,7,6,1};
        Arrays.sort(input_arr); //This will sort the array in-place using quicksort algo in N log(N) time.
        for(int data : input_arr)
            System.out.print(data + "  ");
        for(int i=1; i<input_arr.length ; i++) {
            if(input_arr[i] == input_arr[i-1])
                    input_arr[i-1] = null; // Replace the duplicate value with null
        }
        
        System.out.println();
        for(int i=0 ; i<input_arr.length; i++)
            System.out.print(input_arr[i] + "  ");


}

i would use hashset because of its efficient way of removing duplicates.

I would say the answer mostly depends on the input. But Hashing is the best in most cases.

In case we are using java APIs HashMap or HashSet...... they do have their own algo to keep functioning.... so we can't just say O(1) is the complexity.... using these APIs for purpose is OK if we are not too concerned about complexity or we are sure the best algo is being used in these APIs.

In case we are not using any pre built APIs yes BST or a SORTED ARRAY data structure is looking good as total nlog(n) complexity is required to insert, delete duplicates and maintain unique data having n elements.

how about the following solution :

Integer[] array = {1,1,2,2,3,3,4,4,4,5,6,7,8,8};
List<Integer> list2 = Arrays.asList(array);
Set<Integer> s = new HashSet<Integer> (list2);

for(Integer i :s)
{
System.out.println(i);
}

yes hashing using key value as the number and it's value frequency is the best wy to eliminate duplicates as we ca do that in o(1) space and o(n) time complexity . Is there any better way ?

don't you need a hash-entry for each of the N elements (in the worst case when there are no duplicates), so space complexity should be O(N) as well as its time-complexity, right?

When the N elemnts are given as an array and you're allowed to modify it, then you could use a modifies BuildHeap function to build a heap in place (and don't insert duplicates in that heap) in O(N) with no additional memory.

The complexity will be O(n*logn) (to build sorted array) and additional memory O(n)

Best will be hashmap
Second best is BST, it eliminates the duplicates in O(logn).

probably hasing:)

Yes hashing with O (1) space and O(n) time complexity.
Correct me if I am wrong.