15
\$\begingroup\$

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.

\$\endgroup\$
  • 5
    \$\begingroup\$ you can use the 0th index with num - 1, also if b[num]: return num is sufficient. \$\endgroup\$ – hjpotter92 Oct 13 at 23:40
  • 1
    \$\begingroup\$ To save some space you can simply do b = [0] * (len(a) + 1). You know the elements are bound by 1 <= a[i] <= a.length so why blindly initialize to the maximum (10^5)... Doing num-1 adds one more operation per iteration and slows down - it is better to just have one slot not used... \$\endgroup\$ – Tomerikoo Oct 14 at 11:12
  • 1
    \$\begingroup\$ The list -- which is essentially one implementation of a set -- could be filled with False and True directly and if b[num] == 1 could be replaced with if b[num]. \$\endgroup\$ – GZ0 Oct 14 at 11:55
  • \$\begingroup\$ Serious question: What does Codesignal really want --- creativity? speed? footprint? I don't want to distract into the standard discussions of "Interview Questions," but maybe knowing the intent of the original question can better guide the answers. \$\endgroup\$ – Carl Witthoft Oct 15 at 12:09
  • \$\begingroup\$ @CarlWitthoft, they don't specify any criteria for optimization (perhaps unfortunately) besides that the solution has to run under 4 seconds, which is effectively the same as no constraint at all. I'm just using those websites to get better at algorithms. I try to optimize for speed and then for memory, knowing there's usually a tradeoff. Then come here for advice on how to do things better. I think for me the main appeal of those websites is the addictive quality that keeps me going all day on this stuff. \$\endgroup\$ – jeremy radcliff Oct 15 at 18:40
8
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ @superbrain My bad - clearly I needed sleep. Fixed it, ... and then completely replaced it bytearray, which is far superior. \$\endgroup\$ – AJNeufeld Oct 15 at 15:32
  • \$\begingroup\$ Yeah, using repeat is better in that sense, although it still costs more space (because the array overallocates) than array.array('b', (0,)) * (len(a) + 1), which is also shorter and about 2000 (!) times faster (for the worst case length). \$\endgroup\$ – superb rain Oct 15 at 16:00
  • \$\begingroup\$ @superbrain Clearly, Python needs an array.array(type, length) constructor, based on all the hoops we're going through to allocate an array of the desired size. \$\endgroup\$ – AJNeufeld Oct 15 at 16:08
  • \$\begingroup\$ @superbrain Updated my times using your array multiplication suggestion. Nice. \$\endgroup\$ – AJNeufeld Oct 15 at 16:16
  • \$\begingroup\$ Ha! Didn't think it would be noticeable in the solution time. I had only tested repeat-vs-multiply in isolation and repeat took about 0.006 seconds, which I thought was irrelevant in the overall solution time, but I forgot that I print the solution times in milliseconds :-) \$\endgroup\$ – superb rain Oct 15 at 16:42
18
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ It's nice and I usually would've written it like this as well, but given that the OP also asked "Perhaps faster or using less memory", I find it worth mentioning that in a worst case like list(range(1, 10**5+1)), this not only takes twice as much time as the original but also five times as much memory. (But I guess neither the 17 upvotes nor the OP's acceptance are concerned about that :-) \$\endgroup\$ – superb rain Oct 15 at 14:28
  • 1
    \$\begingroup\$ @superbrain Certainly; it's not the fastest, but I would venture to say that it's the "most canonical", if there is such a thing. \$\endgroup\$ – Reinderien Oct 15 at 14:35
  • \$\begingroup\$ Yes, I certainly agree with that. Like I said I usually would've written it like this as well (probably have multiple times, even with the same name seen). \$\endgroup\$ – superb rain Oct 15 at 14:38
  • 2
    \$\begingroup\$ This approach applies to arbitrary lists. The OP's approach applies primarily to positive integer lists whose maximum is limited. \$\endgroup\$ – GZ0 Oct 15 at 15:14
  • \$\begingroup\$ @GZ0 That's how it should be advertised :-) Not quite arbitrary, though. Needs hashable elements. \$\endgroup\$ – superb rain Oct 15 at 17:30
14
\$\begingroup\$

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()
| improve this answer | |
\$\endgroup\$
11
\$\begingroup\$

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.
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you for the advice, I didn't know about defaultdict(). Out of curiosity, why is the lower_snake_case better practice? I actually used to do that and switched to camel because that's what they use on that website. \$\endgroup\$ – jeremy radcliff Oct 14 at 1:55
  • 8
    \$\begingroup\$ Because of PEP8. \$\endgroup\$ – Reinderien Oct 14 at 3:18
  • \$\begingroup\$ For a worst case like list(range(1, 10**5+1)) this not only takes about 4.7 as much time as the original (see my answer) but also about 6.6 times as much memory as the original (and even 7.9 times as much in 32-bit Python). \$\endgroup\$ – superb rain Oct 15 at 14:35
7
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ It's not O(1) extra space complexity. The negative integer objects cost space. \$\endgroup\$ – superb rain Oct 14 at 8:53
  • 2
    \$\begingroup\$ Each single int, as long as it's bounded by a constant as it is here, takes constant space. But you don't just have a single one here. If I give you let's say a = list(range(1, N//2+1)) * 2, then you'll create new int objects for the first N/2 elements, which costs Θ(N) extra space. Not O(1). \$\endgroup\$ – superb rain Oct 14 at 9:12
  • 2
    \$\begingroup\$ For example for a = list(range(1, 314159)) * 2, the set solution builds a set of those numbers that takes 8.4 MB extra space, while you build the negations of those numbers and take 8.8 MB extra space: demo. That's with 64-bit Python. On 32-bit Python, it's 4.2 MB for the set and 5.0 MB for your numbers. \$\endgroup\$ – superb rain Oct 14 at 19:11
  • 2
    \$\begingroup\$ Well, in languages like C++ or Java, with primitive types like their int, you'd overwrite the original values with their negations indeed without using extra space. And if I weren't so mean to use a = list(range(1, N//2+1)) * 2 but instead used a = list(range(1, N+1)), then you might also take only O(1) extra space. Because you'd create the new number objects but the original number objects would be deleted since there'd be no references to them anymore. Then the new objects could occupy the memory where the originals were. It's just that my second half references the same objects, ... \$\endgroup\$ – superb rain Oct 14 at 19:31
  • 2
    \$\begingroup\$ Oops, check the demo again. 314159 is larger than allowed. 19661 is allowed and leads to 524 kB for the set and 550 kB for your negatives. That's btw the largest allowed one where set "wins" in this regard. At 19662, the set resizes to 2.1 MB. At the limit, i.e., with a = list(range(1, 50_001)) * 2, the set is still at 2.1 MB and your negatives reach 1.4 MB. So at that limit you do take less extra space than the set. Just not O(1) :-) \$\endgroup\$ – superb rain Oct 14 at 19:41
4
\$\begingroup\$

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)
| improve this answer | |
\$\endgroup\$
  • 3
    \$\begingroup\$ You totally live up to your name :-) \$\endgroup\$ – superb rain Oct 14 at 12:31
  • 2
    \$\begingroup\$ @superbrain How much slower? :) \$\endgroup\$ – JollyJoker Oct 14 at 12:51
  • 1
    \$\begingroup\$ In my answer's benchmark it would take about 17000 times as long as the original solution. Also: > 2? \$\endgroup\$ – superb rain Oct 14 at 12:58
  • 1
    \$\begingroup\$ Edited the 2. Of course I didn't try running it. I'm a bit disappointed the next doesn't prevent it from going through the whole list \$\endgroup\$ – JollyJoker Oct 14 at 13:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.