Java DFS solution 62ms by considering the problem as finding the longest path in a DAG


  • 4

    By considering each number as a node and its multiples as connected nodes. We can obtain a DAG. For example, [1,3,4,6] can form a DAG with edges of 1->3, 1->4, 1->6, 3->6. So, the answer is the longest path of 1->3->6.

    This is very similar to the Topological sorting question which should be solved in O(|E|+|V|), linear running time. However, the bottleneck is that the edges are not given and we need to find those edges using O(|V|^2). Therefore, we need to find a better way to find the edges from a current node to all its connected nodes.

    The idea is that we store all numbers in a TreeSet so they can be searched by order instead of going from small to large one by one. The advantage is that we can jump through the numbers that are not a multiple of the current node. i.e. use above example, when stop at 3, we can jump to 6 directly without visiting 4 by knowing the next multiple of 3 is 3X2=6. And, the next multiple is 3X3 and so on.

    However, this is not enough when we have the case of the big gap, ie, [2, 10000, 10000001]. If we adding factor by one each time, it will take long long time. Therefore, here is the TreeSet coming handy. We find the ceiling of 4 to obtain 10000. In addition, we increase the factor to 10000/2 +1 for next round.

    On the side node, this implementation use O(logN) to search the next multiple. A better implementation is to search only the TreeSet which only has numbers greater than the current number by cutting down the TreeSet. Or, using a sorted array and call Arrays.binarySearch(start, end, value).

    public class Solution {
        TreeSet<Long> mem = new TreeSet<Long>();
        long max = 0;
        List<Integer> ret = new ArrayList();
        Map<Long, List<Integer> > visited = new HashMap<>();
       
        public List<Integer> helper(long cur) {
            if (cur > max || ! mem.contains(cur) ) return null;
            if (visited.containsKey(cur)) return visited.get(cur);
            List<Integer> list = new ArrayList<>();
            long i=2; // the factor for the next multiple of current value
            while ( mem.ceiling(cur*i) != null ) { // no more multiple
                // use O(log N) to find next multiple
                long next = mem.ceiling(cur*i);
                if ( next % cur == 0 ) {
                    List<Integer> temp = helper(next);
                    if (temp != null  && temp.size() > list.size() )
                        list = new ArrayList(temp);
                }
                i=(next/cur)+1; // increase the factor based on the gap. 
            }
            list.add((int)cur);
            visited.put(cur, list);
            return list;
        }
        
        public List<Integer> largestDivisibleSubset(int[] nums) {
            if (nums==null || nums.length ==0) return ret;
            int len = nums.length;
            if (len == 1) { 
                ret.add(nums[0]);
                return ret;
            }
            for (int num : nums) {
                mem.add((long)num);
            }
            max = mem.last();
            for (int num : nums) { 
                List<Integer> temp = helper((long)num);
                if (temp != null  && temp.size() > ret.size() )
                    ret = new ArrayList(temp);
            }
            return ret;
        }
    }

Log in to reply
 

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