Thursday, January 5, 2012

Find the First Duplicated Integer in an Array Without Using Extra Memory

Question: there is a size-N array of integers whose values range from 1 to N. Some integers are duplicated. Find the first duplicate and its index without using any extra memory (not even O(1)).
Solution: there are a few keys in the question that we should consider:
  1. The array size is a finite number N which is also the upper limit for any integer inside the array. Hence, if the array size is 10, then there are ten elements in the array and each of those elements is between 1 and 10.
  2. Some elements are just duplicates. That means the array may not contain all numbers between 1 and N.
  3. We need to find only the first duplicate. Thus, as soon as we discover one, we can stop.
  4. No extra memory is allowed, not even O(0). That means we can't use any extra storage or declare any new variable inside our algorithm because that is O(1).
To solve this problem, we must keep track of elements in order to figure out which one is duplicate. However, regardless of method, we must not use any extra memory. Here is where we must depend on the information given by the problem.
We know that each element's value is between 1 and N, so if we increase that value by (N + 1), the modulus of that value and N + 1 is still the same. For example, modulus of 2 and (N + 1) is 2 and modulus of 2 + N + 1 is still 2. Thus, we can mark a visited element by adding N + 1 into its value or any element's value in the array because that doesn't change its modulus with N + 1 at all!
Furthermore, we know that each element's value is between 1 and N. Hence, we can use each element's value as a key and the element at array[key] as the mark. For example, if the current element is 4 then we can check if its value has been visited, and thus a duplicate, by looking at the value of the element at index 4 in the array, if the current element is 2 the we check the value of the element at index 2 in the array, and so on.
One final point, we need to traverse the array and check each element, so we need a loop that run till we find the duplicate or till we reach the end of the array. The problem with such loop is that it needs additional counter / sentinel value as the loop's termination condition! That requires memory allocation. Fortunately, we know that the first element is not a duplicate because there is no other element in front of it. Thus, we can use the first element in the array as our counter.
This algorithm is short but difficult to understand without doing an example, so lets take a look at the algorithm implementation and go straight to an example:

http://codesam.blogspot.com/2011/04/find-first-duplicated-integer-in-array.html

Reactions:

1 comment:

  1. let the array be 3 1 2 1 3 4

    first repeated integer is 3 here

    start from the first and go till the end

    add n+1 to the a[a[i]] where i is the current index.

    iterate again dividing the values by n+1 if values comes 1 . the remainder is the repeated one.

    ReplyDelete