Find the Repeat
with no space to spare
Problem Statement: Given a list of integers with the following characteristics, find at least one integer that appears more than once in the list.
- The integers are in the range 1..n
- The list has a length of n + 1
Constraint: Space complexity of O(1)
Analysis: The most obvious solution is to iterate through the list and check each element against every other element until there’s a match.
That’s not very efficient at all. O(n²) time, but space complexity is maintained.
But we can do better.
Solution: In order to lower time complexity, we can’t think in terms of elements. There is one source of sorted information with this list: the indexes. And because we know that our list necessarily contains integers only up to the length of the list, we can mentally map the idea of ‘integers’ to the list’s indexes.
This way, we can cut out list in halve and simply check each half for which one contains too many elements compared to how many should be there.
The lesson here is to keep your brain open to every source of information provided by the data set. Even if it’s in the structure itself.
Happy Coding!
