The question is very unrealistic... how often do you know there is exactly one duplicate in a list? Much more common is there are zero or more duplicates. Her

The question is very unrealistic... how often do you know there is exactly one duplicate in a list? Much more common is there are zero or more duplicates. Here is what I came up with: - We need a way to record what has been already seen - A hash-map could work, but I think we can be more efficient - We know that all elements are less than the array length in size... - So we can allocate a single array of flags with the same length as the input - The flag for value `n` is at position `n` in this array let findDuplicates xs = let seen = Array.create (Seq.length xs) false let mutable duplicates = [] for x in xs do if seen[x] then duplicates <- x :: duplicates else seen[x] <- true duplicates I'm pretty sure this is O(n)? I think it's interesting that the mathematical trick (sum of numbers 1 to n formula) does not work in the more realistic variant. This fact is probably why leet-code problems are so disconnected from the real world. It's like AI for board-games.