Home > Applied Algorithms, Sorting > Determine if there are any duplicates in an array which can have values from 1 to N

Determine if there are any duplicates in an array which can have values from 1 to N

This one seems to be simple. The first approach that jumps up is the shitty O(n^2) method. Ofcourse you are intelligent enough to discard the idea. Moving on, you recall having read an overview of sorting algorithms on allaboutalgorithms. Oh yes! That would work wouldn’t it?

Certainly. One way to solve this problem is to sort the array in time O(n lg n) and then traverse through the array once comparing adjacent elements and seeing if they are equal (since duplicates will always end up being together after you sort the data-set).

But what if an interviewer asks you to solve it with an algorithm having less time complexity but gives you the freedom to use some space? You should now make use of the fact that the question specifically says the elements of the array would lie between 1 and N. Remember the concept of counting that we used in counting sort? We can use the same here. Define an array of N elements (initially all zero). Then move through your array once and increment the corresponding position of the discovered element in your extra array. This array will finally hold the counts of the number of occurrences of each element between 1 and N in the array. Now all you need to do is move through this new array and see if any position has a value > 1. That would signify that duplicates do exist in the array. In this way, the problem is solved with time complexity O(n) and space complexity of O(n).

Nice! Another new concept learned. Another problem solved. You can move on now! 🙂

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: