Remove duplicates from a sorted array

Question

I have solved the LeetCode Remove Duplicates From Sorted Array problem:

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length. It doesn't matter what you leave beyond the new length.

I was able to come up with a approach but only when I submitted this solution and got it accepted I found that my solution ranked somewhere around 60%, ranked by run-time. i.e) My solution was only faster that 40% of other contestants solution for the same language.

  int removeDuplicates(vector<int>& nums) {
    if (nums.size() == 0)
    {
        return 0;
    }
    auto start = nums.begin(), end = nums.end();
    int last_value = *(nums.end() - 1);
    for (auto it = nums.begin(); it != end;)
    {
        int find_value = *it;
        auto upper = upper_bound(start, end, find_value); //Find the last occurring index of this number 
        iter_swap(start, it);
        ++start;
        if ((upper != end) || ((upper == end) && (find_value == last_value)))
        {
            it = upper;
        }
        else
        {
            ++it;
        }
    }
    return distance(nums.begin(), start);
}

Could you please suggest any performance improvements to this code. And also please go easy on the naming convention and code formatting. This was written for a programming challenge :)

Edit.

The worst case time complexity i believe is O(n Log n) which happens when the entire array is unique. And the best case run time should be O(log n) when the entire array contains duplicates.

Answer 1

You have too many special cases.

Why do you care about what the last_value is? Just checking it != end should be sufficient to terminate the loop.

Then, when you no longer need last_value = *(nums.end() - 1), you can also get rid of the nums.size() == 0 special case.

You have iterators it and start. start is a rather confusing name, since it refers to an iterator that moves along. You could call them src and dest, or in and out, or fast and slow. I'm going with rabbit and turtle.

Swapping with iter_swap() isn't necessary; just a simple assignment will do.

int removeDuplicates(std::vector<int>& nums) {
    std::vector<int>::iterator rabbit, turtle, end = nums.end();
    for ( rabbit = turtle = nums.begin();
          rabbit != end;
          rabbit = std::upper_bound(rabbit, end, *turtle), turtle++ ) {
        *turtle = *rabbit;
    }
    return std::distance(nums.begin(), turtle);
}

I have a suspicion that much of the time, the very next element is already going to be different. It might be worth it to do a quick peek at the next element before going through the trouble of launching a binary search.

Answer 2

So the simplest solutions is to use the available stl function. However there is obviously less to learn there.

#include <algorithm>
#include <vector>

int removeDuplicates(std::vector<int>& nums) {
    nums.erase(std::unique(nums.begin(), nums.end()), nums.end()); ;
    return nums.size();
}