9-line python solution with 1 line to handle duplication, beat 99% of others :-)

  • 40

    Very similar to Permutation I, see explanations in https://leetcode.com/discuss/19510/my-ac-simple-iterative-java-python-solution. To handle duplication, just avoid inserting a number before any of its duplicates.

    def permuteUnique(self, nums):
        ans = [[]]
        for n in nums:
            new_ans = []
            for l in ans:
                for i in xrange(len(l)+1):
                    if i<len(l) and l[i]==n: break              #handles duplication
            ans = new_ans
        return ans

  • 14

    Nice one! Here's an even shorter and I think faster implementation, though. Got it accepted in 100 ms, achieving the coveted "Your runtime beats 100.00% of python submissions." (Well, I tried five times, they were 112, 104, 100, 104 and 116 ms).

    def permuteUnique(self, nums):
        ans = [[]]
        for n in nums:
            ans = [l[:i]+[n]+l[i:]
                   for l in ans
                   for i in xrange((l+[n]).index(n)+1)]
        return ans

    And for fun, a one-liner version:

    def permuteUnique(self, nums):
        return reduce(lambda a,n:[l[:i]+[n]+l[i:]for l in a for i in xrange((l+[n]).index(n)+1)],nums,[[]])

  • 0

    Could you explain how could you come up with this condition to handle duplicate situations?
    I believe it is easy to think of inserting same number nearby, but not the "if i<len(l): break"

  • 2

    It is easy to come up with we should skip the same number we meet. But that only covers intra-perm, like from “2,1” to “2,2,1” and “2,2,1”, how about the inter-perm duplicate, like from “2,1” to “2,1,2” and from “1,2” to “2,1,2”.
    When we first encounter the situation from “2,1” to “2,2,1” and “2,2,1”, if we choose to “continue” and we will insert new “2” into rightmost position to get “2,1,2” which duplicates “2,1,2” later from “1,2”.
    Why? First we start from permutation “---orig_num---” and insert new number from left to right. Once the new number is inserted right of its duplicate number, it looks like “---orig_num---insert_num---”, which can be observed as “---new_num---orig_num---” extended from another permutation “---orig_num---” by inserting insert_num at left position. Because we operate on all permutations generated from previous loop, we can always find a previous permutation to cause inter-permation duplicate.
    Therefore, we should “break”, other than “continue”, after we encounter the first same number.

  • 1

    @StefanPochmann very smart by using (l+[n]).index(n) to eliminate duplicates

  • 0

    Followed your Java solution in Permutation I. But I maintained a cache to keep track of the previous values.

    List<List<Integer>> permutations = new ArrayList<List<Integer>>();
            if(nums.length == 0)
                return permutations;
            HashSet<String> cache = new HashSet<String>();
            List<Integer> t = new ArrayList<Integer>();
            for(int i = 1; i < nums.length; i++){
                List<List<Integer>> temp = new ArrayList<List<Integer>>();
                for(int j = 0; j <= i; j++){
                    for(List<Integer> l : permutations){
                        List<Integer> new_l = new ArrayList<Integer>(l);
                        new_l.add(j, nums[i]);
                permutations = temp;
            return permutations;

    Although this is not very fast method, also using extra memory, but couldn't come up with better solution following your Permutation I solution. Please suggest if you can give better iterative solution following your logic. Thank you in advance.

  • 10

    Very smart way to eliminate the duplicate.
    Here is my understanding about the eliminate process.

    After several times of append and other operations,
    #here I just pay attention to one element, 2's position in the inner list
    We get the current list like below:

    1. [2,x,x,x]
    2. [x,2,x,x]
    3. [x,x,2,x]
    4. [x,x,x,2]
      Of course if we replace the "x" with other elements, there should be several other lists in each row,but the position of "2" should just be same,[0],[1],[2],[3] for each row.
      The approach will traverse each list and insert the new element.
      If the new element is "2", the current "for loop" will break.
      Therefor,after the two loops,the "2" 's position in the list should be:
      It will actually cover all the situation of the two 2's distribution.

  • 0

    Would someone please do me a favor by analyzing the time and space complexity of the implementation? Thank you very much in advance!

  • 0

    @cbmbbz Hi, there! Very nice solution! But one quick question: Since we want to make sure not inserting a number before any of its duplicates, why do we handles the duplication after the insertion? I knew the code works well, but this part is kinda confusing.
    As follow:
    if i<len(l) and l[i]==n: break

  • 0

    @jessicalee I think they will be exponential, as the result set is exponential. For example each digit can be at first, second, third ... last. Then the complexity is O(n^n) where n is the length of the array.

  • -1

    @chenweisomebody Your broken english is really hard to understand.

  • 0

    @ja0b I think the author means 'after'.....you could go through the code to see ...

  • 0

    Very smart thinking! Thanks a lot!

  • 0

    I do not understand why this solution is so fast. Should not the time complexity be O(n3) ?
    Why my solution is so slow? I got beaten by almost everyone.... /cry
    Only 2 for loops. Shouldn`t my code gets a time complexity of O(n2) which is better than most of the answers ? Is it because of the test cases ?

    if len(nums) == 0:
                return []
            if len(nums) == 1:
                return [nums]
            res = []
            for i in xrange(len(nums)):
                m = nums[i]
                leftNums = nums[0:i] + nums[i+1:]
                for j in self.permuteUnique(leftNums):
                    if [m]+j not in res:
            return res

  • -1

    this question is basically brute force

  • 0

    @Ivan_Ouyang I would speculate the "not in" part may be slow on list, and what you do would be traversing a growing res all the time.

Log in to reply

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