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();
}
3ms C++ O(nlog(n)) Solution Using the STL

@ivanguerra 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.

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


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)):
 Sort list (Cost O(nlog(n)))
 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.

@ivanguerra 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).

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".