Sometimes wrong answer, sometimes TLE?


  • 0
    W

    My Java code works correctly and fast on my computer, but when submitted to OJ, it sometimes returns wrong answer on

    Input:	[1,1]
    Output:	[[1],[1,1]]
    Expected:	[[1,1]]
    

    Other times it returns TLE on input [1,1,0,0,1,-1,-1,1]

    What could be the cause of this? I have included my code below:
    I'm using a simple recursive algorithm that puts a unused entry on the first spot, and then recursively permute the remaining elements. The work is done in place on the same ArrayList, so no extra storage or time is used.

    public class Solution {
        static ArrayList<ArrayList<Integer>> perms=new ArrayList<ArrayList<Integer>>();
        public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
            
            ArrayList<Integer> numArrayList=new ArrayList<Integer>();
            for (int i=0;i<num.length;i++) numArrayList.add(num[i]);
            permute(0,numArrayList);
            return perms;
            
        }
        
        void permute(int start, ArrayList<Integer> num){
            if (start==num.size()-1){ // completed, add to solution
                perms.add(new ArrayList<Integer>(num));
                return;
            }
            permute(start+1,num);
            HashSet<Integer> used=new HashSet<Integer>();
            used.add(num.get(start));
            for (int i=start+1;i<num.size();i++){
            	if (used.contains(num.get(i))) continue;
                swap(start,i,num);
                permute(start+1,num);
                swap(start,i,num); // restore the original list
                used.add(num.get(i));
    
            }
        }
        
        void swap(int i,int j,ArrayList<Integer>num){
            int tmp=num.get(i);
            num.set(i,num.get(j));
            num.set(j,tmp);
        }
        
    }

  • 0
    W

    Just tried implementing the same thing in Python, and it passed easily.


  • 0
    W

    For comparison, I'm also including my Python code that's passed with no problem. I wonder why the same Java code would not work...

    class Solution:
    # @param num, a list of integer
    # @return a list of lists of integers
    def permuteUnique(self, num):
        self.perms=[]
        self.permute(0,num)
        return self.perms
        
    def permute(self,start,num):
        if start==len(num)-1: 
            self.perms.append(num[:])
            return
        used={num[start]}
        self.permute(start+1,num)
        for i in range(start,len(num)):
            if num[i] in used: continue
            self.swap(start,i,num)
            self.permute(start+1,num)
            self.swap(start,i,num)
            used.add(num[i])
    
    def swap(self,i,j,num):
        tmp=num[i]
        num[i]=num[j]
        num[j]=tmp
    

  • 0
    Y

    Remove:

    used.add(num.get(start));
    

    and change

     for (int i=start+1;i<num.size();i++)
    

    to

     for (int i=start;i<num.size();i++)
    

    I think that will work.


  • 0
    W

    Thanks for the reply. But it doesn't work for me...
    Did you try it?


Log in to reply
 

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