0

I was attempting an easy problem that asked me given a std::vector of integers and a value, remove all elements from that vector with that value and return the size of the resulting vector. The code I ended up writing was 

int removeElement(vector<int>& nums, int val) {
    for (int i = 0; i < nums.size(); ) {
        if (nums[i] == val) {
            nums.erase(nums.begin() + i);
        } else {
            i++;
        }
    }
    return nums.size();
}

However, after going through my code, is this solution actually O(n^2) since I'm deleting elements in the vector inside a loop?

Howard Wang
  • 472
  • 6
  • 18
  • 1
    Yes, it is `O(n^2)`. Each time you delete an element all the elements to its right are shifted one place left. – vishal-wadhwa Aug 04 '18 at 07:32
  • Because of the above, you could get _slightly_ better performance, if you iterated from the end of the vector (but it would, still, remain `O(n^2)`). Alternatively, you could consider using different container type, if the usage of `std::vector` doesn't suit your performance needs. – Algirdas Preidžius Aug 04 '18 at 07:35
  • You really should use the [erase-remove idiom](https://en.wikipedia.org/wiki/Erase%E2%80%93remove_idiom) for this sort of thing.... `nums.erase(std::remove(nums.begin(), nums.end(), val), nums.end());` is O(N). – Shawn Aug 04 '18 at 07:45

0 Answers0