Remove duplicate array elements with O(N) by not using collections? [duplicate]

StackOverflow https://stackoverflow.com/questions/19762790

Question

Lets say I have an array of integer elements, here I want to remove all the duplicate elements and print the remaining elements with out using any Java.util classes. I solved it using 2 pointers to scan and remove all the duplicates but which takes O(N^2). I just wanted to know is there any algorithm which can finish this task in O(N)?

Example:

Input Array:    [1, 2, 3, 4, 5, 4, 3, 4, 6]
Expected Array: [1, 2, 5, 6]
Was it helpful?

Solution

You could use buckets to achieve O(N) + C (with a HUGE C) but at the cost of storage

  1. Create an array of ints of MAX_INT size called bucket[MAX_INT]
  2. Loop through input array. If value is x, increment bucket[x]++;
  3. Loop through input array again. For every x if bucket[x] == 1, add into expected array.

the bucket[] array can be replaced with a better data structure. But it still achieves O(N)

OTHER TIPS

I would use a Set.

for each item:
  if item is in the Set
    ignore it
  else
    copy it somewhere or output it or whatever
    add it to the Set

That should work for you.

Using a HashSet seems to have O(1) complexity for add and contains (Time complexity of set in Java)

You can sort all the elements with any algorithm like merge sort, quick sort that has a complexity of n lg n. And then use a stack to add elements to it. keep on pushing elements to the stack until you find a duplicate. In case of duplicate elements pop from the stack.it will remove duplicate elements. The total complexity would be O(n lg n). This can be an efficient way to solve the problem.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top