Complexity Analysis
def find_duplicates(arr):
arr.sort()
dupes = []
for i in range(1, len(arr)):
if arr[i] == arr[i-1]:
dupes.append(arr[i])
return dupesWhat is the time and space complexity?
Work it out before scrolling down.
Time
O(n log n)
Space
O(1)
How to derive it
Sorting is O(n log n). The linear scan afterward is O(n). Since O(n log n) dominates O(n), total time is O(n log n). The sort is in-place (Python's Timsort uses O(n) space internally, but for analysis we often treat .sort() as O(1) extra space). The output list doesn't count toward auxiliary space.