My AC simple iterative java/python solution


  • 136

    the basic idea is, to permute n numbers, we can add the nth number into the resulting List<List<Integer>> from the n-1 numbers, in every possible position.

    For example, if the input num[] is {1,2,3}: First, add 1 into the initial List<List<Integer>> (let's call it "answer").

    Then, 2 can be added in front or after 1. So we have to copy the List<Integer> in answer (it's just {1}), add 2 in position 0 of {1}, then copy the original {1} again, and add 2 in position 1. Now we have an answer of {{2,1},{1,2}}. There are 2 lists in the current answer.

    Then we have to add 3. first copy {2,1} and {1,2}, add 3 in position 0; then copy {2,1} and {1,2}, and add 3 into position 1, then do the same thing for position 3. Finally we have 2*3=6 lists in answer, which is what we want.

    public List<List<Integer>> permute(int[] num) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        if (num.length ==0) return ans;
        List<Integer> l0 = new ArrayList<Integer>();
        l0.add(num[0]);
        ans.add(l0);
        for (int i = 1; i< num.length; ++i){
            List<List<Integer>> new_ans = new ArrayList<List<Integer>>(); 
            for (int j = 0; j<=i; ++j){            
               for (List<Integer> l : ans){
            	   List<Integer> new_l = new ArrayList<Integer>(l);
            	   new_l.add(j,num[i]);
            	   new_ans.add(new_l);
               }
            }
            ans = new_ans;
        }
        return ans;
    }
    

    python version is more concise:

    def permute(self, nums):
        perms = [[]]   
        for n in nums:
            new_perms = []
            for perm in perms:
                for i in xrange(len(perm)+1):   
                    new_perms.append(perm[:i] + [n] + perm[i:])   ###insert n
            perms = new_perms
        return perms

  • 12
    H

    I used your idea of adding each next value to every possible position of current list, but have done it with recursion.

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (nums.length == 0) return result;
        
        backtrack(result, nums, new ArrayList<Integer>(), 0);
        
        return result;
    }
    
    private void backtrack(List<List<Integer>> result, int[] nums, List<Integer> currentList, int index) {
        if (currentList.size() == nums.length) {
            result.add(currentList);
            return;
        }
        
        int n = nums[index];
        for (int i = 0; i <= currentList.size(); i++) {
            List<Integer> copy = new ArrayList<Integer>(currentList);
            copy.add(i, n);
            backtrack(result, nums, copy, index + 1);
        }
        
        
    }
    

    I guess both solutions have the same complexity


  • 3
    J

    Very nice solution! you can simply a little bit by removing a couple of lines:

    	public List<List<Integer>> permute(int[] num) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        if (num.length ==0) 
        	return ans;
        ans.add(new ArrayList<Integer>());
        for (int i = 0; i< num.length; ++i){
            List<List<Integer>> new_ans = new ArrayList<List<Integer>>(); 
            for (int j = 0; j<=i; ++j){            
               for (List<Integer> l : ans){
                   List<Integer> new_l = new ArrayList<Integer>(l);
                   new_l.add(j,num[i]);
                   new_ans.add(new_l);
               }
            }
            ans = new_ans;
        }
        return ans;
    }

  • 0
    L

    A tiny improvement for Java solution, we don't really need the special case for the first element. Just ans.add(l0); add the empty list and let the loop starts from 0 for (int i = 0; i< num.length; ++i){ :)


  • 6
    K

    Good idea! I was thinking we can optimize the solution by adding on to a single answer list instead of recreating a new list every time!

    public class Solution {
        public List<List<Integer>> permute(int[] nums) {
            List<List<Integer>> result = new LinkedList<List<Integer>>();
            if(nums.length == 0) return result;
            List<Integer> cur = new LinkedList<Integer>();
            cur.add(nums[0]);
            result.add(cur);
            for(int i = 1; i < nums.length; i++) {
                int curSize = result.size();
                for(int j = 0; j < curSize; j++) {
                    for(int x = 0; x < result.get(j).size(); x++) {
                        List<Integer> newList = new LinkedList<Integer>(result.get(j));
                        newList.add(x, nums[i]);
                        result.add(newList);
                    }
                    result.get(j).add(nums[i]);
                }
            }
            return result;
        }
    }

  • 1
    D

    I used your idea, but have a slightly different starting point before getting into the loop. I think it's logically more clear and don't need to handle corner case when num is empty.

    public List<List<Integer>> permute(int[] num) {
        
        List<List<Integer>> rst = new ArrayList<List<Integer>>();
        
        rst.add(new ArrayList<Integer>());
    
        for (int i = 0; i < num.length; i++) {
            List<List<Integer>> tmpRst = new ArrayList<List<Integer>>();
            for (List<Integer> pm : rst) {
                for (int j = 0; j < pm.size() + 1; j++) {
                    List<Integer> tmpPm = new ArrayList<Integer>(pm);
                    tmpPm.add(j, num[i]);
                    tmpRst.add(tmpPm);
                }
            }
            
            rst = new ArrayList<List<Integer>>(tmpRst);
        }
        
        return rst;
    }

  • 0
    P

    Very well explained. Thanks a ton!


  • 0

    liji94188 is right. We don't need the special case for empty array and the first element.


  • 0
    A

    Hi, Can someone please explain the time Complexity for the above solution? I believe it to be n^3 but I am not sure!
    Thanks in advance.


  • -1
    J

    C++ version:

    class Solution {
    public:
    vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> result;
    vector<int> num;
    num.push_back(nums[0]);
    result.push_back(num);
    for(int i=1;i<nums.size();i++){
    vector<vector<int>> tmp;
    for(int j=0;j<=i;j++){
    for(auto it :result){
    auto it2=it.begin();
    it.insert(it2+j,nums[i]);
    tmp.push_back(it);
    }
    }
    result = tmp;
    }
    return result;
    }
    };


  • 2
    G

    @akshat5 The complexity is proportional to the size of the output (number of permutations). Just imagine that for the first position you have n possible candidates, then for the second position you have n-1 possible candidates (as the one is already taken in the first position), for the 3rd position you have n-2 candidates, etc. Therefore the complexity is O(n!). Also you can think in opposite way: in the beginning you have 1 element, next iteration you create 2 elements from it (add element in the beginning and at the end), so 12 operations, on the next step for each existing element you make 3 operations, so 12*3, etc.


  • 0
    N

    Here is C++ version Running time -16 ms

    vector<vector<int>> permute(vector<int>& nums) {
    	vector<int> curr;
    	vector<vector<int> > ans;
    	if(nums.size()==0)
    		return ans;
    	curr.push_back(nums[0]); // insert first element
    	ans.push_back(curr); // insert the vector with first element
    	for(int i=1;i<nums.size();i++) // start from 2nd element of list
    	{
    		vector<vector<int> > new_ans;
    		for(int j=0;j<=i;j++) // insert nums[i] at 0->i position in result list
    		{
    			for(auto itr = ans.begin();itr!=ans.end();itr++) // get every list from ans to insert num[i]
    			{
    				vector<int> curr1(*itr); // copy the list into new vector
    				curr1.insert(curr1.begin()+j,nums[i]); // insert num[i] at pos j
    				new_ans.push_back(curr1); // insert new list into new ans
    			}
    		}
    		ans = new_ans; // copy ans
    	}
    	return ans;
    }
    

  • 0
    N

    @garik for time complexity I think we should also need to consider inserting into list and copying list so complexity should be greater than !n


  • 0
    C

    loop itself would be n^3, and copy would be n, insertion would be logn, Can I assume it would be n^4logn?


  • 0
    J

    @cbmbbz nice solution for using an iterative instead of recursive method


  • 0
    Z

    nice solution


  • 0
    H

    @neer1304 Yes, greater than N!


  • 1
    Y

    @cbmbbz said in My AC simple iterative java/python solution:

    then do the same thing for position 3

    typo here... should be position 2


  • 0
    J

    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
    I'm confused about the space complexity...I will say space is O(N!)<- or total # of output intuitively, but in every fool-i loop, you create a new res, which will be (N-1), and the following for-j & for-list loop, you create new copy of every existing list in the ans....So will it be O(N-1) * O(N!)<- final result => O(N*N!) ?


Log in to reply
 

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