1
$\begingroup$

I was tasked with writing a function that finds the value of an element that is the first duplicate in an array to be encountered. For the array

[2, 1, 3, 5, 3, 2]

The answer is 3, not 2.

for an array like this:

[5, 3, 8, 2]

(no dups) the answer is -1.

I wrote this function:

def solution(a):
    # return if no dups
    if len(set(a)) == len(a):
        return -1

    unique = []
    for e in a:
        if e in unique:
            return e
        else:
            unique.append(e)

    return -1

It does fine with small test inputs but it takes too long on large ones. How can I speed it up?

I tried this same algorithm in Perl on the same data and it processed all the inputs in time.

sub solution {
  my ($a) = @_;
  my %h;
  foreach my $e (@{$a}) {
    if (exists($h{$e})) {
      return $e;
    } else {
      $h{$e}++;
    }
  }
  return -1; 
}
Improve this question
$\endgroup$
8
  • $\begingroup$ Coding questions and Python-specific questions are off-topic here. See cs.stackexchange.com/tags/python/info. Questions about algorithms can be on-topic. $\endgroup$ Commented Feb 22, 2023 at 7:37
  • $\begingroup$ How is it not a question about an algorithm? $\endgroup$ Commented Feb 22, 2023 at 7:39
  • 1
    $\begingroup$ If the answer depends on language-specific details - like the difference in runtime between a dictionary vs list vs set in Python - then it is a matter of implementation, not a matter of algorithm. Or, to put it another way, if you need to include Python code in your question and the answer depends on that Python question, then there is a good chance it is an implementation question. If you can replace all of the code with concise pseudocode, there is a good chance it might be an algorithm question. $\endgroup$ Commented Feb 22, 2023 at 7:51
  • 1
    $\begingroup$ I disagree. I'm talking about the difference between a hash lookup and an array traversal. $\endgroup$ Commented Feb 22, 2023 at 7:55
  • 1
    $\begingroup$ Augment every element with its initial index in the array and sort lexicographically on the value/index pairs. Then with a single pass, you can find all duplicates and keep the smallest second index. E.g. $[2_0,1_1,3_2,5_3,3_4,2_5]\to[1_1,2_0,2_5,3_2,3_4,5_3]$. $2$ and $3$ are duplicates and $3_4$ comes before $2_5$. $\endgroup$ Commented Mar 24, 2023 at 9:26

2 Answers 2

Reset to default
0
$\begingroup$

I changed the unique variable in the python snippet to signify a hash (dictionary in pythonspeak) instead of an array (list in pythonspeak) and it speeds it up enough to deal with all the inputs on time:

def solution(a):
    if len(set(a)) == len(a):
        return -1
    unique = {}
    for e in a:
        if e in unique:
            return e
        else:
            unique[e] = 1
    return -1

hashes lookups are theoretically O(1) and so are faster than array traversals O(N).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Keep in mind that the lookups do no require $O(1)$ time in the worst case, but only in expectation. $\endgroup$ Commented Feb 22, 2023 at 9:03
  • $\begingroup$ Note that the initial test len(set(A)) = len(A) takes considerable time. If the number of possible values is only k then the first duplicate can be expected after sqrt(k) elements, so depending on your data removing the initial check may make things a lot quicker. $\endgroup$ Commented Dec 22, 2023 at 18:47
0
$\begingroup$

Your “unique”, the way you wrote it using [], is an array. Lookup time grows linear with the size of the array when the element you are looking for is not there. That’s why the time will grow quadratic with the index of the first duplicated element.

The answer you got made “unique” a hash table by using {}. Lookup in a hash table is practically constant time, so the time is now linear with the index of the first element not found.

As far as the question goes: it’s very hard to make an array lookup faster. We get around that by not using an array in the first place.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.