Java TreeMap solution


  • 0
    D

    When I was interviewing, I wrote DP solution with 0(n^2), the interviewer was not satisfied. While I forget the solution using binary search + dp. So I came up with a solution using TreeMap.. Hope the interviewer can accept the solution

        TreeMap<Integer, Integer> map = new TreeMap<>();
        
        for (int n : nums) {
            Map.Entry<Integer, Integer> upper = map.ceilingEntry(n);
            Map.Entry<Integer, Integer> lower = map.floorEntry(n);
            if (lower == null && upper == null) {
                // num to shortest len
                map.put(n, 1);
            } else if (lower != null && upper == null) {
                int lower_len = lower.getValue();
                int lower_num = lower.getKey();
                map.put(n, lower_len + 1);                
            } else {
                int upper_len = upper.getValue();
                int upper_num = upper.getKey();
                System.out.println(upper_num);
                map.remove(upper_num);
                map.put(n, upper_len);
            }                                   
        }
        
        
        return map.size();

Log in to reply
 

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