Find duplicate element in array in time O(n)
algorithm, arrays, java
Solution
We have the original array `int A[N];` Create a second array `bool B[N]` too, of type `bool=false`. Iterate the first array and set `B[A[i]]=true` if was false, else bing!
Problem
I have been asked this question in a job interview and I have been wondering about the right answer. You have an array of numbers from 0 to n-1, one of the numbers is removed, and replaced with a number already in the array which makes a duplicate of that number. How can we detect this duplicate in time O(n)? For example, an array of `4,1,2,3` would become `4,1,2,2`. The easy solution of time O(n2) is to use a nested loop to look for the duplicate of each element.