Why using Java TreeSet ends up a time limit exceeds?


  • 0
    J
    public class Solution {
        public List<Integer> countSmaller(int[] nums) {
            List<Integer> output = new ArrayList<Integer>();
            TreeSet<Integer> previouses = new TreeSet<Integer>();
            if(nums.length == 0) {
                return output;
            } else {
                output.add(0);
                previouses.add(nums[nums.length - 1]);
            }
            for(int i = nums.length - 2; i >= 0; i--) {
                previouses.add(nums[i]);
                output.add(previouses.headSet(nums[i]).size());
            }
            Collections.reverse(output);
            return output;
        }
    }
    

    Theoretically, the run time should be O(nlogn).


  • 0

    What makes you think it should be O(nlogn)?

    I'm not sure, but I think your previouses.headSet(nums[i]).size() is likely only O(n), could be optimized to achieve O(logn), but that it would take extra effort/costs that are just not worth it because it's an unusual use case.

    I ran a little test, added three lines:

    public List<Integer> countSmaller(int[] nums) {
        nums = new int[5000];
        for (int i=0; i<nums.length; i++)
            nums[i] = -i;
        ... (rest of your code)
    

    Running that took about 170 ms. Doubling the size to 10000 numbers roughly quadrupled the time to about 650 ms. So looks like your solution is indeed only O(n^2).

    Interesting idea, though. I didn't know headSet before.


  • 0
    Y

    Calling size() on a headSet/tailSet view is linear time operation in Java.
    http://stackoverflow.com/questions/14750374/what-is-complexity-of-size-for-treeset-portion-view-in-java?rq=1


Log in to reply
 

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