https://leetcode.com/problems/contains-duplicate/
This one always tricks me – even though the problem is really straightforward, I have spent a lot of time trying to find a solution better than O(n) time.
But given the constraint -> -109 <= nums[i] <= 109 – optimal solution cannot be better than O(n) time. Also, the optimal solution ends up being O(n) space as well, since we have to use a Set or a Map data structure to record previously seen numbers.
If we can’t allocate O(n) space: there are two possible solutions. One approach could be to use two loops -> select a number and check if that numbers appears again in the rest of the array -> this would be a O(n^2) solution.
The other solution first sorts the input (which would take O(n logn) time) and then iterates over the sorted array to detect equal neighbors. Swift uses Timsort -> which takes O(n) space, but we could implement selection sort which runs in O(1) space – however I would not expect that in an interview (hopefully).
If we relax the constraint to:
- Only allow positive numbers with a known upper bound (m)
- We are allowed to modify the input
In this case, we could solve the problem in O(n) time and O(1) space -> this approach works by moving numbers to their ‘correct’ indexes (e.g. moving the number 2 to index 2 -> which would need moving the number at index 2 to its correct position). If we ever find a number already at its correct position – we know that we have found a duplicate.
Indrajit Shanbhag 