Easy understandable solution using HashMap


  • 0
    H
    public List<Integer> largestDivisibleSubset(int[] nums) {
            List<Integer> res = new ArrayList<Integer>();
            Arrays.sort(nums);
            if(nums.length == 0){
                return res;
            }
            Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
            for(int n : nums){
                map.put(n, new ArrayList<Integer>());
            }
            int maxIndex = 0;
            int maxCount = 0;
            for(int i = 0; i < nums.length; i++){
                map.get(nums[i]).add(nums[i]);
                for(int j = 0; j < i; j++){
                    if(nums[i] % nums[j] == 0){
                        if(map.get(nums[j]).size() + 1 > map.get(nums[i]).size()){
                            map.get(nums[i]).clear();
                            map.get(nums[i]).addAll(map.get(nums[j]));
                            map.get(nums[i]).add(nums[i]);
                            if(map.get(nums[i]).size() > maxCount){
                                maxCount = map.get(nums[i]).size();
                                maxIndex = i;
                            }
                        }
                    }
                }
            }
            return map.get(nums[maxIndex]);
        }
    

Log in to reply
 

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