CODEWITHSUNDEEP
pythonoptimization
Jason Donnald
Jason Donnald

Reputation: 2316

Optimizing index difference of equal values for time complexity

I have this code that finds the smallest difference between the indices of equal values in a list. (It finds the smallest "distance" between equal values.) I want to optimize its time complexity. My code currently runs in O(N^2).

def func(arr):
    length = len(arr)
    res = 0
    for i and j in range(length):
            if arr[i] == arr[j]:
                res = min(res,i-j)
    return res

How can I optimize it?

Upvotes: 0

Views: 72

Answers (2)

niemmi
niemmi

Reputation: 17263

Here's a simple solution that has O(n) time complexity. For every item in the array it will store the first index it's found from and then later retrieves it to calculate the difference:

def func(arr):
    d = {}
    return max(i - d.setdefault(x, i) for i, x in enumerate(arr))

Update: If the items on the list are not hashable or sortable then you need to compare them all against each other and that can be only done in O(n^2) time. You could improve the original code by starting the inner loop from i+1 which would also get rid of abs. Another improvement would be to call max only once instead of after every match:

def func(arr):
    gen = (j - i for i in range(len(arr) - 1) for j in range(i + 1, len(arr))
           if arr[i] == arr[j])
    return max(gen, default=0)

Note that above only works on Python 3.x because max on 2.x doesn't support default parameter.

Update: The most efficient algorithm I could come up with to cover the scenario of unhashable/sortable items is to compare all pairs with difference of len(arr) - 1 and if you don't find a match then compare pairs of len(arr) - 2 and so forth. This is of course still O(n^2) in case that all items on the list are unique:

def func(arr):
    for i in range(len(arr) - 1, 0, -1):
        for j in range(len(arr) - i):
            if arr[j] == arr[j+i]:
                return i

    return 0

Upvotes: 6

Alec
Alec

Reputation: 1469

You can get a bit of a speed up by bringing that max() out to the top and using list comprehensions (although you'll still need to tackle the O notation complexity):

def func(arr):
    return max([abs(i - j)
                 for i in range(len(arr))
                   for j in range(len(arr))
                     if arr[i] == arr[j]])

Upvotes: 0

Related Questions