Find duplicates in an array, without using any extra space

by

If there is no additional information, this question seems to be unsolveable, as this is the Element Distinctness Problem, which is unsolveable with the restrictions you provided, in the required time.

you can allow:

(1) more memory and use a hashtable / hashset and meet the O(n) time criteria. [iterate the array, check if an element is in the hash table, if it is you have dupes, otherwise – insert the element into the table and continue].

(2) more time, sort the array [O(nlogn)] and meet the sub-linear space criteria. [After sorting, iterate over the array, and for each a[i] , a[i+1] , check if they are identical. If you did not find an identical pair, you have no dupes]

EDIT: The proof for this claim is a bit lengthy, and needs mathematical notation that are not supported here (sidenote: we really need tex support), but the idea is if we model our problem as an Algebraic Computation Tree (which is a fair assumption when no hashing is allowed, and constant space at out disposal), then, Ben Or proved in his article Lower Bounds For Algebraic Computation Trees (1983) (published in prestiged ACM), that element distinctness is Omega(nlogn) problem under this model. Lubiw showed that the same conclusion also applies when limiting ourselves to integers in 1991: A Lower Bound for
the Integer Element Distinctness Problem, but these articles conclude that under the algebraic tree computation model – Integer Distinctness Problem is Omega(nlogn) Problem.

More Related Contents:

  1. Complexity of absolute difference and sum
  2. C++ Sorting Algorithms [closed]
  3. Sum a number with divisors to get another number
  4. Reverse the ordering of words in a string
  5. Getting the closest string match
  6. Converting a Uniform Distribution to a Normal Distribution
  7. Can hash tables really be O(1)?
  8. How to compute Discrete Fourier Transform?
  9. Difference between Big-O and Little-O Notation
  10. Diff Algorithm? [closed]
  11. Efficient list intersection algorithm
  12. Leap year calculation
  13. Backtracking in A star
  14. What is dynamic programming? [closed]
  15. Puzzle: Find largest rectangle (maximal rectangle problem)
  16. How can I calculate the age of a person in year, month, days?
  17. Performing Breadth First Search recursively
  18. Find the index of a given permutation in the sorted list of the permutations of a given string
  19. What is the most efficient algorithm to find a straight line that goes through most points?
  20. Sorting a sequence by swapping adjacent elements using minimum swaps
  21. How modern X86 processors actually compute multiplications?
  22. how do I create a line of arbitrary thickness using Bresenham?
  23. Can an array be grouped more efficiently than sorted?
  24. Algorithm for merging two max heaps?
  25. Unbiased random number generator using a biased one
  26. Why is vector array doubled?
  27. maximum subarray of an array with integers [duplicate]
  28. Can brute force algorithms scale?
  29. Find XOR of all numbers in a given range
  30. Best algorithm for matching colours.

Leave a Comment