Replacement for erase() in a loop for O(N) complexity vs O(N^2)

[final plank]

        int end = nums.size() - 1;
        int start = 0;
        
        while (start < end) {
            if (nums[start] == k) {
                nums.push_back(nums[start]);
                nums.erase(nums.begin() + start);
            }
        }

Given a value of k I want to be able to send it to the end of an array and remove it from where it was
I'm only showing the part where id like optimized but I don't know what else to use aside from erase()
I don't want to use erase() because it would give me a O(N^2) complexity when I want to try and achieve a O(N) complexity
Thanks

[abstract iron]

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question use !howto ask.

[acoustic sierra]

For your "k", does that means that you will only be removing a single value? Or are you asking how if we need to remove multiple values from many spots, and then only do the shifting operation a single time?

[final plank]

I am iterating through an array and removing all instances of value k from many spots yes

[acoustic sierra]

Ahhhhh I see

Yes that can be done. Although it may be a bit of work.

So one idea would be to have an auxiliary array where you record every index that needs to be erased, and then after you've "tagged" all of those spots, then the algorithm would be the following:

aaaaaaaakaaaaaakaaaakkkkaaakkaaaaaaa
        ^      ^    ^^^^   ^^
0000000001111111222223456666788...

So, with this information you start at the first instance of k, move over by 1, and then start shifting values over by 1 spot until you hit the next k, then you move one to the right just like before and now you start moving all the values down by 2 (since 2 k's have been replaced) until you hit the 3rd k, then move one to the right and move all values by 3, etc

[final plank]

I'll try and give it a shot. Thank you

[acoustic sierra]

No problem, best of luck! 😄

Oh, also, while this would use more memory during the operation, a way easier method would be to make a brand new array with the same capacity and simply read in all of the values from the first array one by one, simply not doing the copy operation for any instances of k. And they even have builtins for that one 🙂

[final plank]

haha yea but I was trying to make a challenge for myself and only use in-place methods rather than just creating a blank array with the size of the given one

Thanks for the tips though I appreciate them

[acoustic sierra]

No problem! 😄

[abstract iron]

@final plank Has your question been resolved? If so, type !solved :)