A clean python solution using hashmap


  • 0
    E

    This is a typical backtracking solution with O(n) space. It is short, clean and easy to follow.

    class Solution:
        # @param num, a list of integer
        # @return a list of lists of integers
        def permuteUnique(self, num):
            numPool = {}
            for i in num:
                if i in numPool:
                    numPool[i] += 1
                else:
                    numPool[i] = 1
            return self.dfs(numPool, [[]])
            
        def dfs(self, numDic, filled): 
            returned_list = []
            for eachkey in numDic:
                if numDic[eachkey] > 0:
                    pass_list = [x + [eachkey] for x in filled]
                    numDic[eachkey] -= 1
                    extended_lists = self.dfs(numDic,pass_list)
                    numDic[eachkey] += 1
                    returned_list.extend(extended_lists)
            return returned_list if len(returned_list) > 0 else filled

  • -1
    L

    Very easy to read. But you are using a lot of extra space, generating a lot of lists here (pass_list = [x + [eachkey] for x in filled]), which might make the stack of the recursion function overflow for maintaining the parameters. I think if we have to use extra space, we cam only generate 1 copy of dictionary for each depth of recursion instead of generating multiple copies of lists. Here is the code for a little bit improvement (133ms)

    class Solution:
        # @param num, a list of integer
        # @return a list of lists of integers
        def permuteUnique(self, num):
            if not num:
                return []
            hash_table = {}
            for i in range(len(num)):
                if num[i] not in hash_table:
                    hash_table[num[i]] = 1
    
            return self.permute(num, hash_table)
    
        def permute(self, num, hash_table):
            if len(num) == 1:
                return [num]
            ret = []
            hash_copy = dict(hash_table)
            for i in range(len(num)):
                if num[i] in hash_copy:
                    hash_copy.pop(num[i])
                    for elt in self.permute(num[:i]+num[i+1:], hash_table):
                        ret.append([num[i]]+elt)
            return ret
    

    Or the space complexity can be reduced to O(1) by pre-ordering the input list. It needs O(logN) extra time time but I think it is negligible compared to the whole recursion process. The code can be found at https://leetcode.com/discuss/20099/ac-python-solution-using-sorted-integers

    class Solution:
        # @param num, a list of integer
        # @return a list of lists of integers
        def permuteUnique(self, num):
            if not num:
                return []
            num.sort()
            return self.permute(num)
    
        def permute(self, num):
            if len(num) == 1:
                return [num]
            ret = []
            prev = None
            for i in range(len(num)):
                if prev != num[i]:
                    prev = num[i]
                    for elt in self.permute(num[:i]+num[i+1:]):
                        ret.append([num[i]]+elt)
            return ret

  • 0
    E

    "for i in range(len(num)):
    if num[i] not in hash_table:
    hash_table[num[i]] = 1
    "
    I don't understand how do you count the duplicates?

    "hash_copy = dict(hash_table)" You are actually using O(n^2) space

    Sorting actually need O(nlogn) extra time?

    O(n) space is not avoidable, since the recursion function will stack at most n times, in each stack if you have a local variable, the space complexity will be O(n). And you have one indeed 'prev'

    And further more, you second code sample actually using O(n^2) space, because "num[:i]+num[i+1:]" will create a new list, and worst case it will occupy O(n-1) space.

    "for i in range(len(num)):" and your code is not pythonic.

    " which might make the stack of the recursion function overflow for maintaining the parameters" This is not true since the only copy of the object is in the permuteUnique(), and all the others are merely references.

    In term of run time, the result is actually really noisy. Even that, your "133ms" is slower than mine.


  • 0
    L

    I am not saying that my code is better. The only thing I want to point out is that it might be better if we can reduce the number of the references in the recursive function.
    "This is not true since the only copy of the object is in the permuteUnique(), and all the others are merely references." Hmm, I will spend sometime to find out if it is true, since that's the only thing matters here. Thanks for your reply.


  • 0
    E

    I understand. It's just discussion. It appears that you are not actually familiar with python.


  • 0
    L

    "for i in range(len(num)): if num[i] not in hashtable: hashtable[num[i]] = 1 " I don't understand how do you count the duplicates?

    ->It is the same logic with the second solution with prev, the solution is placing numbers in one position at each step, hashtable is keeping track of whether the same number is already placed in the current position.

    "the only copy of the object is in the permuteUnique(), and all the others are merely references."

    ->It is true that the parameters are reference, however, it does not mean the stack will not overflow (The number of the reference is not critical here).

    1)If we pass immutable objects(like string), we will definitely need more space since when we assign a new value to the parameter new objects are created and maintained.
    2)If we are passing mutable objects(like list or dictionary), it depends on whether we are rebinding the reference. When we simply mutate those mutable objects(e.g. numDic here), we are not allocating new space.When we rebind the mutable reference(eg. filled here), we are actually making the reference point to new objects.Print out id(numDic) and id(filled) to check that.

    I think using a dictionary to keep check of number of the unused elements in num is the best answer for the this problem. Since sorting does need extra time and using num[:i]+num[i+1:] does need extra space.


  • 0
    L
    This post is deleted!

  • 0
    L

    #PermutationII with dictionary
    class Solution:
    # @param num, a list of integer
    # @return a list of lists of integers
    def init(self):
    self.res = []
    self.hash_table = {}

        def _permute(self, num, determined):
            for key in self.hash_table:
                if len(determined) == len(num):
                    self.res.append(determined)
                    return
                if self.hash_table[key] > 0:
                    self.hash_table[key] -= 1
                    self._permute(num, [x for x in determined + [key]])
                    self.hash_table[key] += 1
    
        def permuteUnique(self, num):
            for n in num:
                if n in self.hash_table:
                    self.hash_table[n] += 1
                else:
                    self.hash_table[n] = 1
            self._permute(num, [])
            return self.res

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.