Short iterative Java solution


  • 24
    S

    Hi guys!

    Here's an iterative solution which doesn't use nextPermutation helper. It builds the permutations for i-1 first elements of an input array and tries to insert the ith element into all positions of each prebuilt i-1 permutation. I couldn't come up with more effective controling of uniqueness than just using a Set.

    See the code below!


    public class Solution {
        public List<List<Integer>> permuteUnique(int[] num) {
            LinkedList<List<Integer>> res = new LinkedList<>();
            res.add(new ArrayList<>());
            for (int i = 0; i < num.length; i++) {
                Set<String> cache = new HashSet<>();
                while (res.peekFirst().size() == i) {
                    List<Integer> l = res.removeFirst();
                    for (int j = 0; j <= l.size(); j++) {
                        List<Integer> newL = new ArrayList<>(l.subList(0,j));
                        newL.add(num[i]);
                        newL.addAll(l.subList(j,l.size()));
                        if (cache.add(newL.toString())) res.add(newL);
                    }
                }
            }
            return res;
        }
    }

  • 0
    Z

    newL.add(j, num[i]);
    Above single line can replace 3 lines below:
    List<Integer> newL = new ArrayList<>(l.subList(0,j));
    newL.add(num[i]);
    newL.addAll(l.subList(j,l.size()));


  • 0

    It is very similar to the Permutation I, except you need to use a hash set to determine whether the new list is duplicate.
    Even though this approach is not fast enough, but I like it, it's really straight forward!


  • 1
    F

    I use the same method, but if you iterate from back to front in the inner for loop, and jump out when you encounter the same element, you will not need to use the HashSet to avoid repeating.


  • 0
    S

    could you share code not using set ?


  • 0

  • 0

    +1 "I couldn't come up with more effective controling of uniqueness than just using a Set." Not fast, but really clean and not error-prone~


  • 0
    C

    I like this solution because it's iterative. Unlike dfs, iterative is fast but hard to distinguish duplicates without using hashset.


  • 0
    import java.util.*;
    
    public class Solution {
        public List<List<Integer>> permuteUnique(int[] nums) {
            if (nums.length == 0) return new ArrayList<>();
            Queue<List<Integer>> queue = new LinkedList<>();
            queue.add(Collections.singletonList(nums[0]));
            for (int i = 1; i < nums.length; i++) {
                int queueSize = queue.size();
                while (queueSize-- > 0) {
                    List<Integer> record = queue.poll();
                    for (int j = 0; j <= record.size(); j++) {
                        boolean shouldBreak = j == record.size() || nums[i] == record.get(j);
                        List<Integer> tmp = new ArrayList<>(record);
                        tmp.add(j, nums[i]);
                        queue.add(tmp);
                        if (shouldBreak) break;
                    }
                }
            }
            return new ArrayList<>(queue);
        }
    }
    

    here is my iterative solution with only a queue. FYI.


  • 0

    @sekepw

    Fast iterative solution with O(1) extra space (no Set or any other collection)

    class Solution {
        public List<List<Integer>> permuteUnique(int[] nums) {
            if(nums == null || nums.length == 0)
                return Collections.emptyList();
            int len = nums.length;
            Arrays.sort(nums);
            List<List<Integer>> res = new ArrayList<>();
            List<Integer> list = new ArrayList<>(len);
            for (int n : nums)
                list.add(n);
            res.add(list);
            for(int i = 1; i< len; i++){
                int size = res.size();
                for(int j = 0; j < size; j++){
                    list = res.get(j);
                    // [1,1,2,2], when need to add the 2nd 2, it can only be added after the first 2
                    for(int k = i-1; k >=0; k--){ //Important: descending order
                        if(list.get(k) == list.get(i))
                            break;
                        if(list.get(i) != list.get(k))
                            res.add(swap(list, k, i));
                    }
                }
            }
            return res;
        }
        
        // return a new list with i, j swapped
        private List<Integer> swap(List<Integer> list, int i, int j){
            List<Integer> res = new ArrayList<>(list);
            int tmp = res.get(i);
            res.set(i, list.get(j));
            res.set(j, tmp);
            return res;
        }
    }
    

  • 0
    L

    What's the time complexity for this solution? Is it O(n^3) or O(n^2*n!)?


Log in to reply
 

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