Question

Suppose we have an unsorted array A of n elements, and we want to know if the array contains any duplicate elements. Clearly outline an efficient method for solving this problem. By efficient, I mean your method should use O(nlogn) key comparisons in the worst case. What is the asymptotic order of the running time of your method in the worst case? Clearly explain how you obtain your result.

Answer 1

Input: k = 3, arr[] = {1, 2, 3, 4, 1, 2, 3, 4}
Output: false
All duplicates are more than k distance away.

Input: k = 3, arr[] = {1, 2, 3, 1, 4, 5}
Output: true
1 is repeated at distance 3.

Input: k = 3, arr[] = {1, 2, 3, 4, 5}
Output: false

Input: k = 3, arr[] = {1, 2, 3, 4, 4}
Output: true