Java Solution beats 100% so far (just so far)


  • 1
    M

    My thinking process is pretty straightforward. When we iterate the array, if we could know all the existing subsequences whose last elements are equal or smaller than current number, we could generate all subsequences ending with current number by simply appending current number to those found subsequences.
    To achieve this, we could directly come up with a data structure to store previously generated subsequences, and to make it more efficient, we could choose a map, specifically TreeMap will be a good choice.
    Then the most tricky part is how to avoid the duplicate subsequences in our result. For example, [1,2,2,3], with this approach, the workflow will be:

    1. [1(cur), 2, 2, 3] 
        Storage: 
        {
          1:[1]
        }
    2. [1, 2(cur), 2, 3]
        Storage: 
        {
           1: [[1]],
           2: [[1,2],[2]]
       }
    3. [1, 2, 2(cur), 3] 
       Storage:
       {
          1: [[1]],
          2: [[1,2],[2]]
          2: [[1,2], [1,2,2],[2,2]] // is this correct?
       }
    

    We know both 1 and 2 are smaller or equal than 2 in third step above, but should we append 2 to the tails of both of subsequences ending with 1 and 2. We should not, In this case, the trick is that we don't create new subsequences for those whose last elements is equal to current number, we just append the 2 in current subsequence to override previous ones. So in third step, it will be:

    3. [1, 2, 2(cur), 3] 
       Storage:
       {
          1: [[1]],
          2: [[1,2,2],[2,2],[1,2],[2]] // remember to add [2] in the list
       }
    

    The code is below. As we know that the final result would have 2^n subsequences, the worst runtime for this algorithm will still be O(2^n).

     public class Solution {
        public List<List<Integer>> findSubsequences(int[] nums) {
            int n = nums.length;
            
            TreeMap<Integer, List<List<Integer>>> map = new TreeMap<>();
            for (int i = 0; i < n; i ++) {
                
                List<List<Integer>> cur = map.get(nums[i]); // the list of sequences ending with current number
                if (cur == null) {
                    cur = new ArrayList<>();
                    map.put(nums[i], cur);
                }
                int size = cur.size();
                // retrieve all subsequences ending with the number smaller or equal than current number
                Map<Integer, List<List<Integer>>> submap = map.headMap(nums[i], true); 
                final int id = i;
                final List<List<Integer>> curList = cur;
                submap.forEach((k, v) -> {
                    if (k == nums[id]) {
                        for (int j = 0; j < size; j ++) {
                            curList.get(j).add(nums[id]); // directly append the number in current subsequence
                        }
                    } else {
                        for (List<Integer> list : v) {
                            List<Integer> nl = new ArrayList<>(list);
                            nl.add(nums[id]);
                            curList.add(nl);
                        }
                    }
                });
                // Add current number as a list with single element for later use
                List<Integer> single = new ArrayList<>();
                single.add(nums[i]);
                cur.add(single);
            }
            
            List<List<Integer>> res = new ArrayList<>();
            for (List<List<Integer>> list : map.values()) {
                list.remove(list.size() - 1); // remove the list with single element
                res.addAll(list);
            }
            return res;
        }
    }
    
    

    Comments are welcome. If the description are hard to understand, please let me know.


  • 0
    S

    @mgispk
    I love this solution, with clearer explanation than higher voted ones.


  • 0
    S

    I changed a little with an array replacing TreeMap.

        public List<List<Integer>> findSubsequences(int[] nums) {
            List<List<Integer>>[] res = new List[201];
            for (int x : nums) {
                if (res[x+100]==null)
                    res[x+100] = new ArrayList<>();
                for (List<Integer> l : res[x+100])
                    l.add(x);
                for (int i=0; i<x+100; ++i) {
                    if (res[i]==null) continue;
                    for (List<Integer> l : res[i]) {
                        List<Integer> cur = new ArrayList<>(l);
                        cur.add(x);
                        res[x+100].add(cur);
                    }
                }
                List<Integer> l = new ArrayList<>();
                l.add(x);
                res[x+100].add(l);
            }
            
            List<List<Integer>> finalRes = new ArrayList<>();
            for (List<List<Integer>> lists : res)
                if (lists!=null) {
                    lists.remove(lists.size()-1);
                    finalRes.addAll(lists);
                }
            
            return finalRes;
        }
    

Log in to reply
 

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