4
\$\begingroup\$

For a function to determine which element has been removed from a shuffled array, I came up with:

def finder(arr1, arr2):
  l = len(arr1) - 1 
  result = list(arr1)
  for i in range(l):
    current = arr1[i]
    if current in arr2:
      result.remove(current)
      arr2.remove(current)
  return result[0]

In the solution for my course it says:

The naive solution is go through every element in the second array and check whether it appears in the first array. Note that there may be duplicate elements in the arrays so we should pay special attention to it. The complexity of this approach is \$O(N^2)\$, since we would need two for loops.

However doing the other way round, i.e. as I've done above seems to avoid a nested for loop, and is therefore linear as far as I can tell. Am I missing something? Have I made an error in my code or my analysis of its efficiency?

\$\endgroup\$
4
\$\begingroup\$

As the other answers have explained, your implementation is still \$O(n^2)\$.

There are other issues with it too that are worth pointing out.

  • When you find an element of arr1 not in arr2, you could return immediately. This will imply that you can get rid of the result list, the l variable, and iterate over elements of arr1 directly instead of using a range.

  • Whenever possible, it's better to iterate over elements directly instead of using indexes. The loop could have been written as for current in arr1[:-1]:, getting rid of the i variable, and also the l, thanks to the :-1 range.

  • The implementation modifies arr2. That's a side effect, and it doesn't seem very realistic. You should check your specs if that's acceptable, otherwise you should work with a copy instead.

  • The names are terrible. Consider these alternatives:

    • finder -> find_missing
    • arr1 -> orig
    • arr2 -> shuffled
  • As per PEP8, it's recommended to use 4 spaces to indent instead of 2.

Applying the above tips, and with some doctests:

def find_missing(orig, shuffled):
    """
    >>> find_missing([0, 1, 2, 3], [0, 1, 3])
    2
    >>> find_missing([0, 1, 2, 3], [0, 1, 2])
    3
    >>> find_missing([1, 2, 3], [1, 3])
    2
    >>> find_missing([2, 3], [2])
    3
    >>> find_missing([3], [])
    3
    >>> find_missing([1, 2, 2, 2, 3], [3, 2, 2, 1])
    2
    """
    copy = list(shuffled)
    for current in orig:
        if current not in copy:
            return current
        copy.remove(current)
\$\endgroup\$
7
\$\begingroup\$

When you don't know how long a built-in function call will take, then the TimeComplexity page on the Python wiki comes to the rescue. This tells us that both item in list and list.remove(item) take time proportional to the length of the list.

So although current in arr2 and result.remove(current) are single expressions in Python, in fact each of them has a loop hidden inside it, and this makes the overall runtime \$Θ(n^2)\$.

If you're having trouble with the analysis, there's no substitute for actually running the code and timing how long it takes on different inputs! This is really easy to do, for example, you might write:

from random import randrange
from timeit import timeit

def test(n):
    """Time finder on lists of length n."""
    a = list(range(n))
    b = list(a)
    del b[randrange(n)]
    return timeit(lambda:finder(a, b), number=1)

and then:

>>> for i in range(5):
...     n = 10000 * 2 ** i
...     print(n, test(n))
... 
10000 0.020456696045584977
20000 0.07089142000768334
40000 0.361092661973089
80000 1.5187797680264339
160000 6.356738713919185

You can see that when \$n\$ doubles, the runtime increases by around four times, which is what we expect for an \$Θ(n^2)\$ algorithm. Here's a plot showing a least-squares fit of the measurements collected above to the function \$t = an^2\$, and you can see that the fit is pretty good:

\$\endgroup\$
3
\$\begingroup\$

Not because you don't see a for-loop doesn't mean that it doesn't exist.

Ask yourself the question about what if current in arr2 does. It loops through the array, doesn't it?

A faster way to handle this assignment might be to use another data structure, such as a HashSet.

\$\endgroup\$
  • 2
    \$\begingroup\$ HashSet is a Java/C# data structure; in Python the corresponding data structure is a plain set. \$\endgroup\$ – Gareth Rees Jan 14 '17 at 15:54
3
\$\begingroup\$

Your analysis is indeed incorrect. The "second" for loop is hidden in the existence check (current in arr2) that runs in \$O(n)\$.

An easier way to go would be to count the amount of each element in both arrays and subtract them. The one staying at a difference of 1 instead of 0 is the missing element.

Counting elements is easy, just run a collection.Counter over the array and it's done. Subtraction is as easy as Counters does expose a subtract method.

The code can thus be:

from collections import Counter


def finder(arr1, arr2):
    counts = Counter(arr1)
    counts.subtract(arr2)
    return max(counts, key=counts.get)

I used max here to stay \$O(n)\$ because I'm unsure of the complexity of counts.most_common().


You should also document the function using docstrings, for instance, to make sure which parameter is which.

\$\endgroup\$
  • 3
    \$\begingroup\$ It's worth noting that use of Counter requires the elements to be hashable, whereas the code in the post only requires them to be comparable for equality. \$\endgroup\$ – Gareth Rees Jan 14 '17 at 16:19
  • \$\begingroup\$ @GarethRees True. I considered making a comment about that but forgot to put it in. I'll let yours there then. \$\endgroup\$ – Mathias Ettinger Jan 14 '17 at 16:26
  • \$\begingroup\$ Counter.most_common(k) takes time \$Θ(n \log k)\$ since it calls heapq.nlargest. See the implementation. \$\endgroup\$ – Gareth Rees Jan 14 '17 at 17:30
  • \$\begingroup\$ @GarethRees So, since \$log(1) = 0\$, it is \$\mathcal{O}(0)\$ for \$k=1\$? \$\endgroup\$ – Graipher Jan 15 '17 at 0:41
  • 1
    \$\begingroup\$ @Graipher: I find that max is slightly faster than most_common(1), but all I wanted to do here was to point out that there is no reason to be scared of Counter.most_common. \$\endgroup\$ – Gareth Rees Jan 15 '17 at 12:04

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.