C++ STL Multiset implementation -- TLE


  • 0
    P

    Hi,

    I've seen some very good solutions in the discussion board (eg. MergeSort based Inversion-Count) to solve this problem, but I've written a simple 5 line solution with O(n lg n) time complexity using STL Multi-Set which fails (Time Limit Exceeded) for an insanely large input. I tried this test-case on my PC and saw it take ~3 seconds.

    I feel this is a simple solution to the problem. I'd really appreciate any suggestions from a second pair of eyes to get this approach to work. Or maybe, OJ needs to be tuned to support this ?

    vector<int> countSmaller(vector<int>& nums) {
        multiset<int> ms;
        vector<int> ans(nums.size(), 0);
         /*insert each number, calculate distance & store it in ans */
        for(int i = nums.size()-1; i >= 0; i--)
            ans[i] = std::distance(ms.begin(), ms.emplace(nums[i]));
        return ans;
    }

  • 1

    That's not O(n lg n) but O(n^2). Because a multiset's iterators aren't random access iterators, so distance takes O(n).


  • 0
    P

    Ah thanks Stefan ! I missed that :)


Log in to reply
 

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