Remove Duplicates from Sorted Array using O(1) Auxiliary Space (LeetCode)

Question

This is my function

class Solution {

public:

    int removeDuplicates(vector<int>& nums) {

        auto i = nums.begin();
        int prev = *i;
        i++;

        for(;i!=nums.end();i++){

            if(*i == prev){
                nums.erase(i);
            }
            prev = *i;
        }

        return (int)nums.size();
    }
};

It is calling the vector by reference so we have to return length of the modified vector which is without duplicates.

What is wrong with it and how to improve the answer?

Recommended reading: [Iterator invalidation rules](https://stackoverflow.com/questions/6438086/iterator-invalidation-rules) — user4581301, Aug 07 '20 at 16:49
@user4581301 The title says "Remove Duplicates from **Sorted** Array" — MikeCAT, Aug 07 '20 at 16:52
BTW, there is no requirement that a C++ program can only execute functions via classes. IMHO, this should be a free standing function. The `main` is an example of a free standing function. — Thomas Matthews, Aug 07 '20 at 17:23
Agree with @ThomasMatthews ,but in this case you're stuck. Online Judges require you to meet their specified requirements exactly. — user4581301, Aug 07 '20 at 18:19
@OP -- if the array is sorted, there is a better solution than the one you've attempted. First, `std::unique` already does this work for you, and if you see how it is [implemented](https://en.cppreference.com/w/cpp/algorithm/unique), you should see that it simply copies the unique element into the non-unique element position while traversing the array. Then the only thing left to do is one single `erase`, where you are erasing from the last unique position + 1 until the end of the array (which is what `vector.erase` would have done). — PaulMcKenzie, Aug 07 '20 at 18:37
@OP -- Since your solution repeatedly calls `erase`, and you're using online judge competition sites to test your code, remember that these sites have questions that are designed to give time-out errors if the input is very large. For example, if the string contained thousands of characters and many duplicates, your solution may give a time out error due to the calls to `erase` for every duplicate found. Thus a more safer solution would be to copy the values similar to `std::unique`, and then do one single erasure at the end. — PaulMcKenzie, Aug 07 '20 at 18:42

score 3 · Accepted Answer · answered Aug 07 '20 at 16:52

3

std::vector::erase will invalidate iterators and return new iterator, so you should catch the returned iterator.

Try this:

class Solution {

public:

    int removeDuplicates(vector<int>& nums) {

        auto i = nums.begin();
        int prev = *i;
        i++;

        for(;i!=nums.end();){

            if(*i == prev){
                i = nums.erase(i);
            } else {
                prev = *i;
                i++;
            }
        }

        return (int)nums.size();
    }
};

or simpler one:

#include <algorithm>

class Solution {

public:

    int removeDuplicates(vector<int>& nums) {

        auto i = std::unique(nums.begin(), nums.end());
        nums.erase(i, nums.end());

        return (int)nums.size();
    }
};

answered Aug 07 '20 at 16:52

MikeCAT

73,922
11
45
70

what does i = nums.erase(i) mean?? – Saheel Das Aug 07 '20 at 17:54
i mean what does it return to i? – Saheel Das Aug 07 '20 at 17:54
It will return an iterator pointed at the next element (or end of vector) of the erased element. – MikeCAT Aug 07 '20 at 17:55

Emma · Answer 2 · 2020-08-07T17:26:35.163

Without using erase, this'd also pass through:

// Most of headers are already included;
// Can be removed;

#include <cstdint>
#include <vector>

// Start
static const struct Solution {
    using SizeType = std::uint_fast32_t;
    static const int removeDuplicates(std::vector<int>& nums) {
        SizeType len = std::size(nums);
        SizeType count = 0;

        for (auto i = 1; i < len; ++i) {
            if (nums[i] == nums[i - 1]) {
                ++count;

            } else {
                nums[i - count] = nums[i];
            }
        }

        return len - count;
    }
};

References

For additional details, please see the Discussion Board which you can find plenty of well-explained accepted solutions in there, with a variety of languages including efficient algorithms and asymptotic time/space complexity analysis^{1, 2}.

Remove Duplicates from Sorted Array using O(1) Auxiliary Space (LeetCode)

2 Answers2

References