Find element that has been removed from a shuffled array

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:

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.

You 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 substract 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. Substraction is as easy as Counters does expose a substract method.

The code can thus be:

from collections import Counter


def finder(arr1, arr2):
    counts = Counter(arr1)
    counts.substract(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.

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)