Why is my python code so slow (leetcode)?

Question

Given an array of integers, every element appears twice except for one. Find that single one.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

class Solution:
    # @param {integer[]} nums
    # @return {integer}
    def singleNumber(self, nums):
        prev = []
        for i,j in enumerate(nums):
            if j in prev:
                nums[i] = -j
            else:
                prev.append(j)
        return sum(nums)

It's a question from leetcode and actually the one with highest AC rate. However, as my code goes, it tells me Time Limit Exceeded and could not been accepted. Could any one analyze my code including the complexity? Thank you so much.

Upadate: Thank you all and I have changed the "prev" from a list to a set, which works nicely!

class Solution:
    # @param {integer[]} nums
    # @return {integer}
    def singleNumber(self, nums):
        prev = set([])
        for i,j in enumerate(nums):
            if j in prev:
                nums[i] = -j
            else:
                prev.add(j)
        return sum(nums)

However I am still looking for solutions that requires no extra memories as the question describes.

Update: I used another way trying to solve the problem but receives a Time Exceeded again.

class Solution:
    # @param {integer[]} nums
    # @return {integer}
    def singleNumber(self, nums):
        for i,j in enumerate(nums):
            if j in set(nums[:i+1]):
                nums[i] = -j
        return sum(nums)

Actually I an kinda confused that does the slice like nums[:i+1] create a separate list every loop? So is the creation of list the most time consuming here? I used set instead of list so this may reduce the cost for searching.

Try using set instead of an array (or simply xor all values together) — Peter de Rivaz, May 18 '15 at 18:14
Try replacing the list `prev` with a set. This should reduce search-complexity from O(n) which makes the whole problem O(n**2) down to O(1). — deets, May 18 '15 at 18:15
Hint: the answer to the final sentence is "yes". You don't need a list or a set, or any other collection that grows in size. — Kevin, May 18 '15 at 18:16
Hint: you can do an in-place sort over the list without using extra memory — sirfz, May 18 '15 at 18:28
@Sir_FZ: Yeah but sorting is O(n*log(n)) which is not linear — aldeb, May 18 '15 at 18:37
Are the numbers from [1,n]? If so, you can do it *very, very cleanly*. — erip, May 18 '15 at 18:45
@therealprashant the first comment was edited (and xor wasn't in the first version) — Eric Levieil, May 18 '15 at 19:28
@StefanPochmann the first comment was edited (and xor wasn't in the first version) — Eric Levieil, May 18 '15 at 19:28
@EricLevieil It's not visible right now (only says "1 hour ago"), but I'm quite certain therealprashant posted his comment about half an hour after that first comment, and comments are only editable for five minutes, so it was already there when he posted. Or am I missing something? — Stefan Pochmann, May 18 '15 at 19:38

score 5 · Accepted Answer · answered May 18 '15 at 18:44

5

@Peter's answer is brilliant:

def singleNumber(nums):
    unique = 0
    for num in nums:
        unique ^= num
    return unique

answered May 18 '15 at 18:44

Brent Washburne

12,904
4
60
82

Doesn't using a foreach loop in Python require O(n) addition memory? – erip May 18 '15 at 18:50
4

@erip: Python foreach loops requires O(n) **time** complexity, not space complexity. So the answer fits perfectly the requirements. – aldeb May 18 '15 at 18:55
where is he storing the numbers @erip – therealprashant May 18 '15 at 18:56
My mistake. I thought Python made a copy of the list behind the scenes, but after reading through the docs, it seems it's not the case. – erip May 18 '15 at 19:08
这是按位异或，异或操作符是顺序无关的，所以 A^B^A^C^B=A^A^B^B^C=0^C=C，所以一串异或之后剩下的值就是unpaired。数学和数电还是挺重要的，真不是故意设置壁垒啊。 – Decula Oct 15 '18 at 19:20

score 3 · Answer 2 · answered May 18 '15 at 18:43

3

Xor is the way to go. Xor of two similar element is 0 and hence all dups will vanish resulting the non repeated element to be present in res.

x=[1,1,2,3,2,4,4,5,5]
res=x[0]
for i in xrange(1,len(x)):
    res^=x[i]

print res

answered May 18 '15 at 18:43

therealprashant

701
15
27

This is really bad. Compare to Brent's answer. – Stefan Pochmann May 18 '15 at 19:10
1

Could you explain me how? Thanks – therealprashant May 18 '15 at 19:11
How to compare it to Brent's answer? I think the differences are clear. Special treatment of the first number is pointless, and the useless index-looping is very ugly and unpythonic. – Stefan Pochmann May 18 '15 at 19:13
Oh! You are right in this. Thanks I will surely keep this in mind @stefanpochmann – therealprashant May 18 '15 at 19:14
@Stefan Pochmann procedure vs OO ? – Decula Oct 15 '18 at 19:23

Shashank · Answer 3 · 2015-05-18T19:06:00.280

3

Here is an alternative, functional way of writing the XOR-solution.

from operator import xor

def single_number(nums):
    return reduce(xor, nums)

In Python 3.x, (which apparently Leetcode doesn't use) you'll need to import the reduce function from the functools module.

edited May 18 '15 at 19:06

answered May 18 '15 at 18:51

Shashank

13,713
5
37
63

1

Oh that's very clean, thank you~~ – tonyabracadabra May 18 '15 at 18:57
2

Leetcode only has Python 2 :-) – Stefan Pochmann May 18 '15 at 19:04
I tried this, but it's roughly 1.7 times slower for an input of 11 and 2.35 times slower for size 2001 – tennabey May 18 '15 at 19:22
@tennabey Slower than what? – Stefan Pochmann May 18 '15 at 19:57
1

@tennabey Functional programming solutions are not necessarily the fastest solutions (though in some cases, like with JVM 8, they often can be, since parallelization across multiple cores can be applied in the background). Performance depends on implementation and other things. This answer was just to show a clean way of writing it. – Shashank May 18 '15 at 20:06
@StefanPochmann - slower than the `for` loop solutions. @Shashank - of course, but I'm pretty sure the goal here is efficiency. – tennabey May 18 '15 at 20:59
@tennabey I'm pretty sure the goal here is efficiency in the sense of not using quadratic runtime that's too slow to get accepted at leetcode. I got 44ms there with the reduce solution, which is among the fastest Python solutions, and I see an accepted solution with about 850ms. Also, in my own tests, the reduce solution was only up to about 15% slower, depending on size. – Stefan Pochmann May 18 '15 at 22:40

Moritz · Answer 4 · 2015-05-18T20:40:01.877

You can use cython (I used it now the second time, so maybe there is still improvement possible):

Create a file singleNumber.pyx with following content:

def singleNumber(list nums, int nn):
cdef int i, ii, np
cdef list prev = []

for i in xrange(nn):
    np = len(prev)
    for ii in xrange(np):
        if nums[i] == prev[ii]:
            nums[i] = - prev[ii]
        else:
            prev.append(nums[i])
return sum(nums)

Create a file setup.py with following content:

from distutils.core import setup
from Cython.Build import cythonize

setup(
    ext_modules=cythonize('singleNumber.pyx'),
)

Compile it: python setup.py build_ext --inplace

import singleNumber as sn
arr = [i + 1 for i in range(1000)]
%timeit sn.singleNumber(arr,len(arr))

Result : 100000 loops, best of 3: 15.4 µs per loop

Using the XOR function gives me: 10000 loops, best of 3: 82.1 µs per loop

EDIT:

I do get different results if I use the XOR solutions compared to the original function !

from operator import xor

def singleNumber_xor(nums):
    return reduce(xor, nums)

arr = [i + 1 for i in range(10000)]
singleNumber_xor(arr)

Gives me: 10000

The original function:

def singleNumber_orig(nums):
    prev = set([])
    for i,j in enumerate(nums):
        if j in prev:
            nums[i] = -j
        else:
            prev.add(j)
    return sum(nums)

singleNumber_orig(arr)

Gives me: 50005000

Why is my python code so slow (leetcode)?

4 Answers4

Linked