AC Java Solution using map to track duplicates. No sorting!!!


  • 0
    K

    Map is used to store the max index of the number encountered so far and is passed to the next level.
    Every level starts with index 0 and iterates through all the numbers. However, the stopping condition is that, if the current index of a number is less than the index of that number stored in the map, that number is skipped. Otherwise, the number is added to final result and the map is updated with the max index.
    When the recursive call come back from the previous level, the number is removed from the tempList and the map is updated with the correct index.

    public class Solution {
        public List<List<Integer>> permuteUnique(int[] nums) {
            List<List<Integer>> list = new ArrayList<>();
            backtrack(list, new ArrayList<>(), nums, new HashMap<Integer, Integer>());
            return list;
        }
    
        private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, Map<Integer, Integer> map){
            if(tempList.size() == nums.length){
                list.add(new ArrayList<>(tempList));
            } else{
                for(int i = 0; i < nums.length; i++){
                    // If the index of the number is less than the current max index stored in map, continue.
                    if(tempList.contains(nums[i]) && map.containsKey(nums[i]) && map.get(nums[i]) >= i)
                        continue;
                    tempList.add(nums[i]);
                    // track the current max index of the number from map.
                    int index = i;
                    if(map.containsKey(nums[i])) index = map.get(nums[i]);
                    map.put(nums[i], i);
                    backtrack(list, tempList, nums, map);
                    tempList.remove(tempList.size() - 1);
                    // Update the map with the previous max index of the number. If the number does not exist in tempList, remove from the map
                    if(tempList.contains(nums[i])) map.put(nums[i], index);
                    else map.remove(nums[i]);
                }
            }
        }
    }
    

Log in to reply
 

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