CODEWITHSUNDEEP
python-3.xalgorithm
merry-go-round
merry-go-round

Reputation: 4615

Difference between these two algorithms

Problem is to return removed duplicated numbers in array. link

This is solution.

    dict1={}
    arr=[]
    for i in nums:
        if i not in dict1:
            dict1[i]=1
            arr.append(i)
    nums[:]=arr
    return len(nums)

This is my approach... Why is it not working? 

    hash = {}
    for num in nums:
        if num in hash:
            nums.remove(num)
        hash[num] = num
    return len(nums)

I've been working on this problem more than 30 minutes :(

Upvotes: 1

Views: 59

Answers (1)

phoxis
phoxis

Reputation: 61910

From an algorithm point of view, the second one does not look good as the remove have a higher time complexity than the hash insertion and deletion. Therefore, the removal time is more than O(1). The first implementation uses an additional list. Also, instead of maintaining another array you can also do list (hash.keys ()) and return it.

Python list removal is O(n) for both average and amortized case (check https://wiki.python.org/moin/TimeComplexity?), but dict operation is O(1) in average case and O(n) amortized time. In this case I marking the elements in a dict and then returning the keys is a better idea.

Although, in this case I think using a set set to mark the unique items may be a better idea, as it will not only be faster, but also lighter on memory.

From the code point of view, do not modify a list which you are iterating through, unless you access and modify the list using index and take care of the list modification and index manipulation yourself.

Upvotes: 3

Related Questions