Return first duplicate

Question

This is a problem from Codesignal.

The guaranteed constraints are 1 <= a.length <= 10^5, and 1 <= a[i] <= a.length.

You have to return the first duplicate encoutered in a, or -1 if no duplicate is found.

def firstDuplicate(a):

    b = [0] * 100001
    for num in a:
        if b[num] == 1:
            return num
        else:
            b[num] = 1
    return -1

Is there a better way to do this? Perhaps faster or using less memory? The unused 0 index in the b array also doesn't feel very clean.

Answer 1

Memory

Your list implementation uses (depending on your architecture) 8 bytes per list element.

>>> import sys
>>> b = [False] * 100001
>>> sys.getsizeof(b)
800064

Note: This is just the memory of the list structure itself. In general, the contents of the list will use additional memory. In the "original" version, this would be pointers to two integer constants (0 and 1); in the "original_improved" version, it would be storing pointers to the two boolean singletons (False and True). Since we're only storing references to two objects in each case, this additional memory is insignificant, so we'll ignore it.

---

800kB of memory is not a huge amount, but to be polite, we can reduce it:

import array

def aneufeld_array(a):
    b = array.array('b', (0,)) * (len(a) + 1)

    for num in a:
        if b[num]:
            return num
        b[num] = 1

    return -1

Update: bytearray is a better choice than array.array('b', ...)!

def aneufeld_bytearray(a):
    b = bytearray(len(a) + 1)

    for num in a:
        if b[num]:
            return num
        b[num] = 1

    return -1

The bytearray(size) creates a tightly packed of bytes. Unlike lists, which can store different kinds of things in each element of the list, the bytearray, as its name implies, will only store bytes.

With this new structure, we now use only 1 byte per flag, so around 100kB of memory:

>>> b = bytearray(100001)
>>> sys.getsizeof(b)
100058

Performance wise, this solution is close to the original speed, so we're not giving up any significant speed while reducing the memory load to around 12.5%.

---

We can still do better. Using an entire byte for a single flag is wasteful; we can squeeze 8 flags into each byte. The bitarray class does all of the heavy lifting for us:

import bitarray

def aneufeld_bitarray(a):
    b = bitarray.bitarray(len(a) + 1)
    b.setall(False)

    for num in a:
        if b[num]:
            return num
        b[num] = True

    return -1

This gets us down to 12.5kB for the bit-array of flags. Unfortunately, this additional memory optimization comes with an additional speed hit, due to the bit packing and unpacking. The performance is still better than "Sriv_improved" performance, and we're using only 1/64th of the original memory requirement.

---

Timing, on my machine:

 4.94 ms   4.62 ms   4.55 ms  original
 3.89 ms   3.85 ms   3.84 ms  original_improved
20.05 ms  20.03 ms  19.78 ms  hjpotter92
 9.59 ms   9.69 ms   9.75 ms  Reinderien
 8.60 ms   8.68 ms   8.75 ms  Reinderien_improved
19.69 ms  19.69 ms  19.40 ms  Sriv
13.92 ms  13.99 ms  13.98 ms  Sriv_improved
 6.84 ms   6.84 ms   6.86 ms  aneufeld_array
 4.76 ms   4.80 ms   4.77 ms  aneufeld_bytearray
12.71 ms  12.65 ms  12.57 ms  aneufeld_bitarray

Answer 2

I'll propose an alternate implementation, because dictionaries are good at storing key-value pairs and you don't care about the value:

def first_duplicate(given_list):
    seen = set()
    for value in given_list:
        if value in seen:
            return value
        seen.add(value)
    return -1

A set will buy you basically the same behaviour as the "keys of a dictionary" for these purposes.

Answer 3

Benchmark and slightly improved versions of some solutions.

Congratulations, in the worst case (a = list(range(1, 10**5 + 1))) your original solution is about 2-4.5 times faster than the solutions in the previous answers:

 5.45 ms   5.46 ms   5.43 ms  original
 4.58 ms   4.57 ms   4.57 ms  original_improved
25.10 ms  25.59 ms  25.27 ms  hjpotter92
11.59 ms  11.69 ms  11.68 ms  Reinderien
10.33 ms  10.47 ms  10.45 ms  Reinderien_improved
23.16 ms  23.07 ms  23.02 ms  Sriv
17.00 ms  16.97 ms  16.94 ms  Sriv_improved

Done with Python 3.9.0 64-bit on Windows 10 64-bit.

original_improved is yours but faster by not doing == 1 and by using False instead of 0, as that's fastest to recognize as false. And for smaller input lists it takes less space as it makes b smaller accordingly.

Code:

from timeit import timeit
from collections import defaultdict

def original(a):
    b = [0] * 100001
    for num in a:
        if b[num] == 1:
            return num
        else:
            b[num] = 1
    return -1

def original_improved(a):
    b = [False] * (len(a) + 1)
    for num in a:
        if b[num]:
            return num
        b[num] = True
    return -1

def hjpotter92(given_list):
    seen = defaultdict(bool)
    for value in given_list:
        if seen[value]:
            return value
        seen[value] = True
    return -1

def Reinderien(given_list):
    seen = set()
    for value in given_list:
        if value in seen:
            return value
        seen.add(value)
    return -1

def Reinderien_improved(given_list):
    seen = set()
    seen_add = seen.add           # Suggestion by Graipher
    for value in given_list:
        if value in seen:
            return value
        seen_add(value)
    return -1

def Sriv(a):
    for i in a:
        if a[abs(i) - 1] > 0:
            a[abs(i) - 1] *= -1
        else:
            return abs(i)
    else:
        return -1

def Sriv_improved(a):
    for i in map(abs, a):
        if a[i - 1] > 0:
            a[i - 1] *= -1
        else:
            return i
    else:
        return -1

funcs = original, original_improved, hjpotter92, Reinderien, Reinderien_improved, Sriv, Sriv_improved

a = list(range(1, 10**5+1))

tss = [[] for _ in funcs]
for _ in range(4):
    for func, ts in zip(funcs, tss):
        t = min(timeit(lambda: func(copy), number=1)
                for copy in (a.copy() for _ in range(50)))
        ts.append(t)
    for func, ts in zip(funcs, tss):
        print(*('%5.2f ms ' % (t * 1000) for t in ts[1:]), func.__name__)
    print()

Answer 4

Perhaps, using a dictionary to keep account of already seen values?

from collections import defaultdict

def first_duplicate(given_list):
    seen = defaultdict(bool)
    for value in given_list:
        if seen[value]:
            return value
        seen[value] = True
    return -1

---

1. Function name should be lower_snake_case.
2. defaultdict initialises with default value as False. You can pass None instead of bool
3. Use better/descriptive names of variables.
4. Since if clause is returning a value, using the else clause is not needed.

Answer 5

Note that all the elements are positive, and the values are not greater than the length.
There is a very clever method to find the solution in these cases.

The idea is to mark the values by turning a[value] negative.
If a duplicate exists, it will encounter a[duplicate] as negative.

Here's the implementation:

for i in a:
    if a[abs(i) - 1] > 0:
        a[abs(i) - 1] *= -1

    else:
        print(abs(i))
        break

else:
    print(-1)

Make sure to turn the values to 0-based indexing though!

This approach is O(N) time complexity and O(1) extra space complexity.

Answer 6

Using list comprehension, make a list of the numbers occurring more than once

i for i in a if a.count(i) > 1

Return the first match or -1 if no match was found

next((i for i in a if a.count(i) > 1), -1)