python - Fastest way to return duplicate element in list and also find missing element in list? -

so code shown below. input list 1 duplicate item , 1 missing item.the answer list of 2 elements long ,first of duplicate element in list , second missing element in list in range 1 n. example =[1,4,2,5,1] answer=[1,3] code below works.

am , wrong complexity being o(n) , there faster way of achieving in python? also, there way can without using space.

note:the elements may of order 10^5 or larger

    n = max(a)     answer = []     seen = set()     in a:         if in seen:             answer.append(i)         else:             seen.add(i)      in xrange(1,n):         if not in a:             answer.append(i)     print ans 

you indeed correct complexity of algorithm o(n), best can achieve. can try optimize aborting search finish duplicate value. worst case duplicate @ of list , still need traverse completely.

the use of hashing (your use of set) solution. there lot other approaches, instance use of counters. won't change assymptotic complexity of algorithm.

as @emisor advices, can leverage information have list 1 duplicate , 1 missing value. might know if have list no duplicate , no missing value, summing elements of list result in 1+2+3+..+n, can rewritten in mathematical equivalent (n*n+1)/2

when you've discovered duplicate value, can calculate missing value, without having perform:

for in xrange(1,n):     if not in a:         answer.append(i) 

since know sum if values present: total = (n*n+1)/2) = 15, , know value duplicated. taking sum of array a = [1,4,2,5,1] 13 , removing duplicated value 1, results in 12.

taking calculated total , subtracting calculated 12from results in 3.

this can written in single line:

(((len(a)+1)*(len(a)+2))/2)-sum(a)-duplicate