4
\$\begingroup\$

I read the solution to this question, which seems to be the same target. My solution is (I'm sure) not the quickest, but some test case is apparently taking longer than 4s. I did a test case with 10,000 random integers and it completed in just over .33 seconds, so I'm trying to find what would result in this code hanging.

Here are the requirements:

Given an array a that contains only numbers in the range from 1 to a.length, find the first duplicate number for which the second occurrence has the minimal index. In other words, if there are more than 1 duplicated numbers, return the number for which the second occurrence has a smaller index than the second occurrence of the other number does. If there are no such elements, return -1.

Example

For a = [2, 1, 3, 5, 3, 2], the output should be firstDuplicate(a) = 3.

There are 2 duplicates: numbers 2 and 3. The second occurrence of 3 has a smaller index than the second occurrence of 2 does, so the answer is 3.

For a = [2, 4, 3, 5, 1], the output should be firstDuplicate(a) = -1.

My solution:

def firstDuplicate(a):
    currentdupe = -1
    dist = len(a)
    if len(a) == 0: return -1
    if len(a) == 1: return -1
    if len(a) == 2 and a[0] == a[1]: return a[0]
    else:
         #new list
         b = list(a)
         b.sort()

         #check each double in the sorted range
         for x in (range(len(b)-1)):
             if b[x] == b[x+1]:
                 #if distance is less than last found, use this one
                 if a[a.index(b[x])+1:].index(b[x]) < dist:
                     dist = a[a.index(b[x])+1:].index(b[x])
                     currentdupe = b[x]
         return currentdupe

Even in a worst case of 9,998 values of '1' and 2 values of '2', it still ran in just over .5s. When it runs a test case I get "Program exceeded the 4s time limit." How can this be?

\$\endgroup\$
  • \$\begingroup\$ try range -> xrange maybe they use python 2 \$\endgroup\$ – Caridorc May 30 '18 at 13:38
3
\$\begingroup\$

Review

  1. Adhere PEP8

    • functions and variable should be snake_case
    • Avoid multiple statements on one line
      if len(a) == 0: return -1 
      
    • Indentation matters, and an indentation of 4 spaces is the standard
  2. You don't need all these guard clauses

    if len(a) == 0: return -1
    if len(a) == 1: return -1
    if len(a) == 2 and a[0] == a[1]: return a[0]
    
  3. The else: does nothing here, only adds an extra indentation level

  4. When you need both the index and the item it is better to enumerate!

    for x in (range(len(b)-1)):
    
  5. For timing, see the Time complexity for python

    You use some expensive operations while this can be done is a single loop

    • .sort() O(n log n)
    • .index() is O(n)

Note: Look for example at vnp's solution

\$\endgroup\$
  • \$\begingroup\$ This is definitely more efficient, but produced a small difference: when more than 2 of a value are found, but the smallest space between them happens after another number in the list, it is kept because some instance is found first when creating the map. For instance: Input of [1, 2, 2, 1, 1] returns 1 instead of 2 because 1 has a distance of 0 at some point and has an element appear first, where 2 has a distance of 0 before 1 does. \$\endgroup\$ – jlehenbauer May 30 '18 at 14:54

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.