Unique elements
Design an efficient algorithm to remove duplicates from an array of integers.
Solution
- Sort the array in O(n logn)
- Then eliminate duplicates since they would be adjacent elements
Code
def eliminate_duplicates(arr)
arr = arr.sort
i = 0
j = 1
while j < n
if arr[j] != arr[j-1]
arr[i] = arr[j-1]
i += 1
end
j += 1
end
arr.truncate(0, i) # trim upto i, rest of the elements are duplicates.
end
Complexity
- Time: O(n logn) to sort the array, O(n) to eliminate duplicates from sorted array
- Space: constance, since its in-place.