23
\$\begingroup\$

I have completed this question and I am wondering what is the fastest way to solve it.

The question is "There is an array with some numbers. All numbers are equal except for one. Try to find it!"

Example:

find_uniq([ 1, 1, 1, 2, 1, 1 ]) == 2
find_uniq([ 0, 0, 0.55, 0, 0 ]) == 0.55

I came up with the solution:

from collections import Counter

def find_uniq(arr):
    nums = list(Counter(arr).items())
    data = [i for i in nums if i[1] == 1]
    return data[0][0]

I decided on using Counter because I felt comfortable using it but when looking at others answers some use sets and others use counter as well.

I am wondering is my code sufficient and which method to solving this question would lead to the fastest time complexity?

\$\endgroup\$
  • \$\begingroup\$ What should this return for [0, 1]? \$\endgroup\$ – Cireo Jul 26 at 23:10
  • \$\begingroup\$ @Cireo As noted by tinstaafl "The challenge guarantees at least 3 elements. How can you tell which is unique if there are only 2" \$\endgroup\$ – Jacques Jul 27 at 0:37
  • 2
    \$\begingroup\$ "There is an array with some numbers. All numbers are equal except for one. Try to find it!" if arr[0] == arr[1] and arr[0] != arr[2] return arr[2] else return "I tried" \$\endgroup\$ – Acccumulation Jul 27 at 0:47
12
\$\begingroup\$

One of things about the solutions presented so far, is they all require iterating over all the elements at least once.

Using an iterative approach allows you to short circuit the loop when the unique item is found. something like this would work:

def find_uniq(arr):
    for i in range(len(arr)-1):
        if arr[i] != arr[i+1]:
            if i == 0 and arr[i] != arr[i + 2]:
                return arr[i]
            return arr[i + 1]]

Did some thinking and came up with an optimization which improves the time considerably:

def find_uniq(arr):
    for i in range(0,len(arr) - 1, 2):
        if arr[i] != arr[i+1]:
            if i == 0:
                if arr[i] != arr[i + 2]:
                    return arr[i]
                return arr[i + 1]
            else:
                if arr[i] != arr[i-1]:
                    return arr[i]
                return arr[i + 1]
    return arr[-1] 

The complexity of this in the worst case is O(n) the lengthy of the array - 1.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ If your code gets a 2-element array, it access arr[2], which is out of bounds. \$\endgroup\$ – Roland Illig Jul 25 at 7:09
  • 16
    \$\begingroup\$ The challenge guarantees at least 3 elements. How can you tell which is unique if there are only 2 \$\endgroup\$ – tinstaafl Jul 25 at 7:11
  • \$\begingroup\$ This answer breaks for [0, 1, 0, 0, 1, 2]. You will always need to read the whole list, because the unique element could always be the last one. \$\endgroup\$ – Turksarama Jul 25 at 9:47
  • 19
    \$\begingroup\$ @Turksarama That is an invalid input as "All numbers are equal except for one." The code works for [0,0,2]. \$\endgroup\$ – MT0 Jul 25 at 10:01
  • 5
    \$\begingroup\$ Rather disappointing that the by far slowest solution gets the most upvotes and gets accepted. See benchmarks. \$\endgroup\$ – Heap Overflow Jul 25 at 17:24
21
\$\begingroup\$

Benchmarks!

Benchmarks for lists with a thousand or a million elements, with the unique element in the middle of the array to reflect the "typical"/"average" case. The results are times, so lower=faster.

n=1000
0.90 find_uniq_Jacques
1.18 find_uniq_tinstaafl_1
0.59 find_uniq_tinstaafl_2
0.88 find_uniq_GZ0_1
0.14 find_uniq_GZ0_2
0.88 find_uniq_Peilonrayz
0.22 find_uniq_RootTwo
0.26 find_uniq_HeapOverflow_1
0.28 find_uniq_HeapOverflow_2
0.26 find_uniq_HeapOverflow_3
0.09 find_uniq_HeapOverFlow_Codewars
0.06 find_uniq_HeapOverflow_GZ0
0.57 unique_different_ethiy
0.28 find_uniq_KyleG_1
0.25 find_uniq_KyleG_2

n=1000000
0.94 find_uniq_Jacques
1.36 find_uniq_tinstaafl_1
0.68 find_uniq_tinstaafl_2
0.99 find_uniq_GZ0_1
0.19 find_uniq_GZ0_2
0.98 find_uniq_Peilonrayz
0.19 find_uniq_RootTwo
0.23 find_uniq_HeapOverflow_1
0.26 find_uniq_HeapOverflow_2
0.25 find_uniq_HeapOverflow_3
0.09 find_uniq_HeapOverFlow_Codewars
0.04 find_uniq_HeapOverflow_GZ0
0.57 unique_different_ethiy
0.28 find_uniq_KyleG_1
0.22 find_uniq_KyleG_2

Done with Python 3.8.1 32 bit on Windows 10 64 bit.

Benchmark code:

from timeit import timeit
from collections import Counter
from itertools import groupby

solutions = []
def register(solution):
    solutions.append(solution)
    return solution

@register
def find_uniq_Jacques(arr):
    nums = list(Counter(arr).items())
    data = [i for i in nums if i[1] == 1]
    return data[0][0]

@register
def find_uniq_tinstaafl_1(arr):
    for i in range(len(arr)-1):
        if arr[i] != arr[i+1]:
            if i == 0 and arr[i] != arr[i + 2]:
                return arr[i]
            return arr[i + 1]

@register
def find_uniq_tinstaafl_2(arr):
    for i in range(0,len(arr) - 1, 2):
        if arr[i] != arr[i+1]:
            if i == 0:
                if arr[i] != arr[i + 2]:
                    return arr[i]
                return arr[i + 1]
            else:
                if arr[i] != arr[i-1]:
                    return arr[i]
                return arr[i + 1]
    return arr[-1]

@register
def find_uniq_GZ0_1(arr):
    return next(k for k, freq in Counter(arr).items() if freq == 1)

@register
def find_uniq_GZ0_2(arr):
    group_iter = groupby(arr)
    k1, g1 = next(group_iter)
    c1 = len(list(g1))
    k2, g2 = next(group_iter)
    if c1 > 1:
       # Group g1 has more than one element
       return k2
    try:
       # Group g2 has more than one element
       next(g2)
       next(g2)
       return k1
    except StopIteration:
       # Both g1 and g2 has one element
       return k2 if next(group_iter)[0] == k1 else k1

@register
def find_uniq_Peilonrayz(arr):
    return Counter(arr).most_common()[-1][0]

@register
def find_uniq_RootTwo(arr):
    a, b = set(arr)
    return a if arr[:3].count(a) < 2 else b

@register
def find_uniq_HeapOverflow_1(arr):
    a = arr[0]
    if a not in arr[1:3]:
        return a
    for b in arr:
        if b != a:
            return b

@register
def find_uniq_HeapOverflow_2(arr):
    dupe = sorted(arr[:3])[1]
    for x in arr:
        if x != dupe:
            return x

@register
def find_uniq_HeapOverflow_3(arr):
    a = arr[0]
    for b in arr:
        if b != a:
            return b if a in arr[1:3] else a

@register
def find_uniq_HeapOverFlow_Codewars(arr):
    arr.sort()
    return arr[-(arr[0] == arr[1])]

@register
def find_uniq_HeapOverflow_GZ0(arr):
    group_iter = groupby(arr)
    k1, _ = next(group_iter)
    k2, g2 = next(group_iter)
    next(g2)
    return k1 if k2 in g2 else k2

@register
def unique_different_ethiy(iterable):
    # assert isinstance(iterable, Iterable)
    # assert len(iterable) > 2
    if iterable[0] != iterable[1]:
        return iterable[0] if iterable[1] == iterable[2] else iterable[1]
    else:
        for element in iterable[2:]:
            if element != iterable[1]:
                return element

@register
def find_uniq_KyleG_1(arr):
    common = arr[0]
    if common not in arr[1:3]:
        return common
    for a, b in zip(arr[1::2], arr[2::2]):
        if a != b:
            if a == common:
                return b
            else:
                return a
    return arr[-1]

@register
def find_uniq_KyleG_2(arr):
    iterator = iter(arr)
    common = next(iterator)
    if common not in arr[1:3]:
        return common
    for a, b in zip(iterator, iterator):
        if a != b:
            if a == common:
                return b
            else:
                return a
    return arr[-1]

# Run the benchmarks
for e in 3, 6:
    n = 10**e
    number = 10**(7 - e)  # fewer number of runs for larger n
    print(f'{n=}')
    arr = [0] * n
    arr[n // 2] = 1

    # Repeat round-robin to reduce effects of CPU speed changes etc
    timeses = [[] for _ in solutions]
    for i in range(20):
        for solution, times in zip(solutions, timeses):
            arrs = iter([arr[:] for _ in range(number)])
            t = timeit(lambda: solution(next(arrs)), number=number)
            times.append(t)
        print(i, end=' ')
    print()
    for solution, times in zip(solutions, timeses):
        print('%.2f' % min(times), solution.__name__)
    print()
| improve this answer | |
\$\endgroup\$
  • 3
    \$\begingroup\$ Thank you for the comparisons I was also curious. \$\endgroup\$ – Jacques Jul 25 at 20:10
  • 2
    \$\begingroup\$ Thanks for improving my solution and the benchmarking effort. Since the runtime of early-exit solutions depends on the position of the distinguished element, it is better to test different kinds of inputs. More specifically, you may conduct three kinds of tests and output the corresponding runtimes: (1) best-case: the distinguished element occurs at the beginning; (2) worse-case: the distinguished element occurs at the end; (3) average-case: generate all possible inputs (i.e. one input for each occuring position of the distinguished element) and take the average runtime. \$\endgroup\$ – GZ0 Jul 25 at 22:52
  • 1
    \$\begingroup\$ @HeapOverflow (1) Best-case scenarios are relevant because tinstaafl's iterative solution is supposed to rank better in those cases. (2) Worst-case scenarios could also result in a different ranking. Meanwhile, they reflect the differences of implementation overhead, which is independent of the differences caused by the choice of early-exiting. If you don't have much time, it is fine that you only show the average-case scenarios. But then you need to be VERY careful in your conclusion and explicitly mentions that the winner is based on a comparison of average-case runtime. \$\endgroup\$ – GZ0 Jul 26 at 0:50
  • 2
    \$\begingroup\$ @GZ0 Yes, best-case is "relevant" for determining who's fastest at best-cases. But who cares about that? These best-cases are irrelevantly rare and even when they do occur, they contribute irrelevantly little to the overall time. So they're irrelevant² :-) Yes, worst-case should result in a different ranking, but again, the complexity class is the same for average and worst, and worst-case should take only about twice the time, so worst-case is not really that interesting. In my opinion we care about worst case when it's both realistic that it actually occurs and it's catastrophic. I had a ... \$\endgroup\$ – Heap Overflow Jul 26 at 10:58
  • 1
    \$\begingroup\$ ... again, factor 2. Not that interesting even if you do have reason to believe the distribution is heavily biased towards worst-cases. For Timsort there is reason to believe that "best-cases" do occur. As Wikipedia says, "Timsort was designed to take advantage of runs of consecutive ordered elements that already exist in most real-world data". And besides such "real-world data", it's also good for little coding challenges like this one where all allowed inputs are best-cases for Timsort. \$\endgroup\$ – Heap Overflow Jul 26 at 14:12
13
\$\begingroup\$

No matter how the array is traversed, the distinguished element can occur at the end of the traversal. Therefore, it is necessary to go through the entire array in the worst case and there does not exist an algorithm that can have a better worst-case time complexity than \$n\$. However, in practise, the actual runtime of your implementation can be improved, as well as the average-case time complexity.

Firstly, your solution converts the key-value pairs of Counter(arr) into a list. Assuming the input is well-formed, this conversion is unnecessary since it is sufficient to return the first key that has a corresponding frequency value of 1. The improved implementation is as follows:

def find_uniq(arr):
    return next(k for k, freq in Counter(arr).items() if freq == 1)

Secondly, creating a Counter requires going through the entire input array. In most cases, this can be avoided by returning the distinguished element once it is found, as mentioned in the previous answer. This approach improves the average-case time complexity by a constant factor of 2. Note that if the time complexity is described using the \$O(\cdot)\$ and \$\Theta(\cdot)\$ notations there is no difference, since these notations only characterize the asymptotic order of growth of runtime given the input size. More explanations can be found here.

A Python-specific efficient implementation of this improved approach is to use the itertools.groupby function, as shown in the following. It avoids an explicit for-loop in Python, which is typically slower than an implicit-loop-based implementation, such as Counter(arr).

from itertools import groupby

def find_uniq(arr):
    group_iter = groupby(arr)
    k1, g1 = next(group_iter)
    c1 = len(list(g1))
    k2, g2 = next(group_iter)
    if c1 > 1:
       # Group g1 has more than one element
       return k2
    try:
       # Group g2 has more than one element
       next(g2)
       next(g2)
       return k1
    except StopIteration:
       # Both g1 and g2 has one element
       return k2 if next(group_iter)[0] == k1 else k1

Update: @HeapOverflow provides an improved version of this implementation in his answer.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ How about O(n-1)? That's better than O(n). \$\endgroup\$ – tinstaafl Jul 25 at 7:14
  • 8
    \$\begingroup\$ @tinstaafl O(n-1) is the same as O(n). If an algorithm is O(n), it means the runtime is upper-bounded by a linear function of the input size n when n is sufficiently large. Actual runtimes of both 2n and 0.01n are both O(n). I have edited my answer to be more accurate. \$\endgroup\$ – GZ0 Jul 25 at 7:47
  • 1
    \$\begingroup\$ I was going to say "improves the average-case time complexity" should maybe just be "average-case time", but I guess we can say "complexity" and be more specific than "complexity class" (big-O or theta) where you drop all constant factors and smaller terms. I also wanted to point out that an early-out improves the best-case time to O(1), when the first 3 elements differ. (Or with SIMD, if the first 4 elements aren't all equal, then you only have to look at 1 vector.) Also +1 for the Python specific ways of reducing interpreter overhead, which is massive for CPython. \$\endgroup\$ – Peter Cordes Jul 25 at 14:35
  • 2
    \$\begingroup\$ An improved version of your second solution is now by far the fastest :-) \$\endgroup\$ – Heap Overflow Jul 25 at 21:40
7
\$\begingroup\$

You can use .most_common to remove the need for the list comprehension. This makes the code easier to read. You will still need to use [0] as it will return a tuple of the key and the value.

def find_uniq(arr):
    return Counter(arr).most_common()[-1][0]
| improve this answer | |
\$\endgroup\$
7
\$\begingroup\$

Another one going only as far as necessary, with O(1) to check whether the first value is the outlier and otherwise simple O(n) to search for the outlier.

def find_uniq(arr):
    a = arr[0]
    if a not in arr[1:3]:
        return a
    for b in arr:
        if b != a:
            return b

Slight variation, getting the duplicate value from the first three and then searching the non-dupe:

def find_uniq(arr):
    dupe = sorted(arr[:3])[1]
    for x in arr:
        if x != dupe:
            return x

Another variation, finding a difference pair first:

def find_uniq(arr):
    a = arr[0]
    for b in arr:
        if b != a:
            return b if a in arr[1:3] else a

Optimized version of this, also O(n) because, you know, Timsort:

def find_uniq(arr):
    arr.sort()
    return arr[-(arr[0] == arr[1])]

Optimized version of GZ0's groupby solution, faster and taking only O(1) space:

def find_uniq(arr):
    group_iter = groupby(arr)
    k1, _ = next(group_iter)
    k2, g2 = next(group_iter)
    next(g2)
    return k1 if k2 in g2 else k2
| improve this answer | |
\$\endgroup\$
6
\$\begingroup\$

A Counter is basically a "multiset". The question doesn't ask for a count of the numbers, so counting them may be extra overhead. Here's an possible set implementation:

def find_uniq(arr):
    a, b = set(arr)
    return a if arr[:3].count(a) < 2 else b

Both implementations pass through the list once, so they are O(n) time complexity. Your list comprehension, my .count(a), and @Peilonrays' .most_common() are insignificant for large n.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

First, check that there are, at least, 3 elements otherwise this is undefined!

Personally, I would check the first and second elements:

  1. If different: one of them is the one you are looking for. Compare with third element.
  2. If equal: iterate over all elements until you find it.

This seems to be the most optimal solution:

from collections.abc import Iterable

def unique_different(iterable):
    assert isinstance(iterable, Iterable)
    assert len(iterable) > 2
    if iterable[0] != iterable[1]:
        return iterable[0] if iterable[1] == iterable[2] else iterable[1]
    else
        for element in iterable[2:]:
            if element != iterable[1]:
                return element
```
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Why do n comparisons when you only need ~n/2? We can compare every pair of elements until we find a non-matching pair, then "short-circuit" and return whichever element is unique.

def find_uniq(arr):
    common = arr[0]
    if common not in arr[1:3]:
        return common
    for a, b in zip(arr[1::2], arr[2::2]):
        if a != b:
            if a == common:
                return b
            else:
                return a
    return arr[-1]

A further improvement would be to use iter to avoid copies of arr being made in the zip statement.

def find_uniq(arr):
    iterator = iter(arr)
    common = next(iterator)
    if common not in arr[1:3]:
        return common
    for a, b in zip(iterator, iterator):
        if a != b:
            if a == common:
                return b
            else:
                return a
    return arr[-1]
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Good point, focusing on the number of comparisons. I'll add it to my benchmark later. Might be faster than my similar solution because of the fewer comparisons, but going through zip might make it slower. \$\endgroup\$ – Heap Overflow Jul 30 at 11:25
  • 1
    \$\begingroup\$ In general, my guess is the groupby and the timsort solutions will be the fastest, purely because they are both super tight C code that is written to take advantage of long runs of data. My version might be beneficial if your compare is expensive enough. Because the test data is an array of the exact same object instance ([0]*n), comparisons are almost free. \$\endgroup\$ – Kyle G Aug 3 at 15:48
  • 1
    \$\begingroup\$ Right, my test data is rather artificial. Then again, so is the problem :-). (And the original test case generator at Codewars also does pretty much the same.) \$\endgroup\$ – Heap Overflow Aug 3 at 21:03
0
\$\begingroup\$

This is my first time posting here, so please let me know if there are any conventions I'm missing.

Here is my solution, which doesn't need to traverse the entire array except by using the built-in sum() function:

def find_uniq(listToSearch):
    if len(listToSearch) < 3:
        return 'Cannot have one unique value unless there are at least three values.'
    
    #out of three values, minimum of two must be the same
    if listToSearch[0] == listToSearch[1]:
        commonValue = listToSearch[0]
    elif listToSearch[0] == listToSearch[2]:
        commonValue = listToSearch[0]
    elif listToSearch[1] == listToSearch[2]:
        commonValue = listToSearch[1]
    else:
        return 'Array has more than one unique value'
    
    numberOfCommonItems = len(listToSearch) - 1;
    uniqueValue = sum(listToSearch) - numberOfCommonItems * commonValue
    return uniqueValue

These are the test cases I've tried:

find_uniq([ 1, 1, 1, 2, 1, 1 ])
find_uniq([ 0, 0, 0.55, 0, 0 ])
find_uniq([ 0, 0, -0.55, 0, 0 ])
find_uniq[ 1, 1.0, 1, 2, 1, 1 ])

And these are the outputs:

2
0.55
-0.55
2.0

This solution is O(n) as it only has to perform one extra addition per extra element of the array. Besides that, assuming the data format is valid, there are a maximum of four if statements, one multiplication operation and one subtraction operation.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Fails 40% of the test cases at Codewars. \$\endgroup\$ – Heap Overflow Jul 26 at 10:37
  • \$\begingroup\$ I've never been on Codewars. How do I find the test cases? \$\endgroup\$ – Mehmet Jul 26 at 10:56
  • \$\begingroup\$ I don't think you can see the test cases before you solved it, but if you paste your code there and click ATTEMPT, you'll see the issue. \$\endgroup\$ – Heap Overflow Jul 26 at 11:21
  • 1
    \$\begingroup\$ Welcome to Code Review. What we do here is examine the code in the original post and the the author of the original post how that code can be improved. It isn't until the last paragraph of your answer that you come close to to reviewing the code. Alternate solutions are not considered good answers on Code Review. \$\endgroup\$ – pacmaninbw Jul 26 at 13:47

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.