Getting "Time Limit Exceeded" although my code runs for under 100 ms


  • 0
    M

    I am getting a "Time Limit Exceeded" error although my code runs on my computer in less than 100 ms for the last executed output. I calculated, and I am getting the correct result too. There may be a better algorithm than the one I use, but it is not running out of time, atleast not for the "last executed input" that is shown. Any idea why?

    public List<List<Integer>> permuteUnique(int[] nums)
    {
    //Step 1: form all combinations of indices of nums that start with with 0

    Set<List<Integer>> indices = new HashSet<List<Integer>>();
    
    Stack<List<Integer>> stack = new Stack<List<Integer>>();
    List<Integer> root = new ArrayList<Integer>();
    root.add(0);
    stack.push(root);
    
    while(!stack.empty())
    {
    	List<Integer> node = stack.pop();
    	
    	if(node.size() < nums.length)
    	{
    		for(int i = 1; i < nums.length; i++)
    		{
    			if(!node.contains(i))
    			{
    				List<Integer> n = new ArrayList<Integer>();
    				n.addAll(node);
    				n.add(i);
    				stack.push(n);
    			}
    		}
    	}
    	else
    		indices.add(node);
    }
    
    //Step 2: Take the indices and cycle over the values of num to cover all permutations
    Set<List<Integer>> permSet = new HashSet<List<Integer>>();
    
    for(List<Integer> indexCombination : indices)
    {
    	Set<Integer> roots = new HashSet<Integer>();
    	for(int i = 0; i < nums.length; i++)
    	{
    		if(roots.add(nums[(indexCombination.get(0)+i)%nums.length]))
    		{
    			List<Integer> temp = new ArrayList<Integer>();
    			for(int val : indexCombination)
    				temp.add(nums[(val+i)%nums.length]);
    			permSet.add(temp);
    		}
    	}
    }
    
    ArrayList<List<Integer>> permList = new ArrayList<List<Integer>>();
    permList.addAll(permSet);
    return permList;
    

    }


Log in to reply
 

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