3ms C++ O(nlog(n)) Solution Using the STL


  • 0
    I
    int removeElement(vector<int>& nums, int val) {
            std::vector<int>::iterator search_index;
            
            while ((search_index = std::find(nums.begin(), nums.end(), val)) != nums.end()) {
                nums.erase(search_index);
            }
            return nums.size();
        }
    

  • 0
    A

    @ivan-guerra You are not aware that for vector erase, STL actually relocates all elements after erase point. Besides, nobody says the vector is sorted. Your actual complexity is O(n^2), given the worst case that every element must be erased. Terrible.


  • 0

    @ayuanx Why are you talking about sortedness? Did @ivan-guerra's O(nlog(n)) claim successfully confuse you into thinking that find is binary search?


  • 0
    A

    @StefanPochmann I was trying to follow his thinking where he assumed log(n).


  • 0
    I

    Yeah, looking at it I forgot that vector's must shift elements on erase. Also, std::find is not to be confused with bsearch. std::find has linear complexity. The post definitely has inaccuracies.

    Shouldn't be hard to see how you would get to an O(n(log(n)):

    1. Sort list (Cost O(nlog(n)))
    2. Perform a binary search n times removing elements as you go (Cost O(log(n)) * O(n) =
      O(nlog(n))).

    Overall cost of O(nlog(n)) + O(nlog(n)) = O(2nlog(n)) = O(nlog(n)). Yes, depending on what language and DS you pick erasing has a cost as well you would need to factor in. You could avoid that by keeping a list of "deleted" elements and then subtracting the size of original list and "deleted" list to get the answer. This is not meant to be the best answer (FYI they give the best answer in the editorial) just an alternative.


  • 0
    A

    @ivan-guerra But why bother O(nlogn) anyway when O(n) is easily achievable? At worst, you only need to scan the whole array once, which is O(n).


  • 0
    I

    There is value in seeing alternatives. Think about it, did you learn quicksort first or did you learn about selection/bubblesort then move on to the more optimal algorithms? These are toy interview problems. In an interview you would discuss alternatives (even the bad ones). Not all posts have to be copies of the editorial meant to brag about "how I got it in 1 line in Python" or my "C++ code runs in 0.0001ms".


Log in to reply
 

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