Java DFS Solution 86 ms with explanation


  • 3

    My solution uses DFS on the array after it is sorted in ascending order. Why sort in ascending order?
    Let's pretend our input had the following values {1,6,2,3,4,8,24,9,48} in this order . Suppose we are looking at the pair 6 and 3. We know that 6%3=0 but that doesn't mean every multiple of 3 in 3s longest subset is also a multiple of 6. For example, 9 is a multiple of 3 but not 6. However, we do know that every multiple of 6 is also a multiple of 3, hence by ordering the array such that 6 occurs after 3 we can recursively get the largest subsets of multiples of 6 (that will be comprised of values >=6) BEFORE forming longest subset of multiples of 3. . Repeat the same process for 9 (another multiple of 3) and so on and keep track of the largest subset that we can add 3 to. Cache the results so as to avoid repeated computation. For example, the subset {24,48} contains multiples of 1,2,3,4 and 6.By caching we avoid recomputing this subset for each of the aforementioned values.

    public class Solution {
            public List<Integer> largestDivisibleSubset(int[] nums) {
                
                if(nums==null||nums.length==0)
                {
                    return Collections.<Integer>emptyList();
                }
                if(nums.length==1)
                {
                    List<Integer> ls=new ArrayList<Integer>(1);
                    ls.add(nums[0]);
                    return ls;
                }
               Arrays.sort(nums);
        
             HashMap<Integer,List<Integer>> mp=new HashMap<Integer,List<Integer>>();
             List<Integer> maxSubset=null;
             for(int i=0;i<nums.length;i++)
             {
                 List<Integer> ls=null;
                    if(!mp.containsKey(i))
                    {
                        ls=dfs(i,nums,mp);
                        
                        
                    }else
                    {
                        ls=mp.get(i);
                    }
                    
                    if(maxSubset==null||ls.size()>maxSubset.size())
                    {
                        maxSubset=ls;
                    }
            }
            return maxSubset;
        }
        
         private List<Integer> dfs(int idx, int[] arr,HashMap<Integer,List<Integer>> mp)
         {
             if(mp.containsKey(idx))
             {
                 return mp.get(idx);
             }
             List<Integer> ls=new ArrayList<Integer>();
             
             for(int i=idx+1;i<arr.length;i++)
             {
                 if((arr[i]%arr[idx])==0)
                 {
                    List<Integer> r=dfs(i,arr,mp);
                    if(r.size()>ls.size())
                    {
                        ls=r;
                    }
                    
                 }
             }
            
             ls=new ArrayList<Integer>(ls);
             ls.add(0,arr[idx]);
             mp.put(idx,ls);
             return ls;
            
         }
        }

Log in to reply
 

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