1

Can anyone help me conceptually understand what options are available to me for the following:

I have an array of int elements, I'm looking for a way that I can see if any of these are duplicates. I am trying to keep time complexity in mind, and want a solution that is in O(n) time.

With this specific boundary in mind, I cannot use a nested for-loop to iterate through all n elements, since this array may contain tens of thousands of indicies.

Any ideas or suggestions that might help me?

vsminkov
  • 10,912
  • 2
  • 38
  • 50
drewp
  • 13
  • 4
  • 2
    If you sort them (O(n log n)), then once they are sorted, you only have to compare adjacent items. (Assuming you are looking for duplicates.) – khelwood Aug 31 '16 at 12:48
  • 1
    What do you mean "any of these match"? Match what? Do you mean find duplicates? – RealSkeptic Aug 31 '16 at 12:49
  • Yes I am looking for duplicate elements. – drewp Aug 31 '16 at 12:49
  • 1
    If all your ints are in a fairly constrained range, you can go through it once (O(n)) and keep counts of the occurrences of each value. – khelwood Aug 31 '16 at 12:53

1 Answers1

2

Make HashSet<T> set from your T[] array. If 

set.size() != array.length

then you have duplicates

Making HashSet has O(n) complexity.

Do not forget about equals and hashcode overriding in T.

Sergei Rybalkin
  • 3,337
  • 1
  • 14
  • 27