Why when I use .size() to compute the length of array in the Conditional Determination of for Loop Structures will time out in leetcode?

Question

I noticed a particular timing behaviour while solving LeetCode problem 27. Remove Element:

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.

Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:

• Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
• Return k.

When I submitted the code below, I got a time-out:

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int count=0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]==val){
                for(int j=i;j+1<nums.size();j++){
                    nums[j]=nums[j+1];
                    count+=1;
                }
                i--;
            }
        }
        return nums.size()-count;
    }
};

Then I tried to use a variable to record the value of nums.size() and use it as the loop condition. This time the code finished within the alotted time.

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int count=0,size=nums.size();
        for(int i=0;i<size;i++){
            if(nums[i]==val){
                for(int j=i;j+1<size;j++){
                    nums[j]=nums[j+1];
                    count+=1;
                }
            i--;
            size--;
            }
        }
        return size;
    }
};

I don't understand why this could be such an important difference.

I would like to know the time that .size() uses and its internal code, with its time complexity.

Answer 1

Calling nums.size() on each iteration or storing it in a variable first does not actually make much of a difference. The real issue is that you run into an infinite loop when the last element is the value to remove, as you keep attempting to shift the remaining elements (of which there are none) down over and over. In the second version of your code, you decrement the size when shifting, which precludes going into the section of the vector that contains useless elements not part of the solution.

On another note, since the question states that the size of nums after the method executes doesn't matter, you can directly delete the matching elements from the vector. This can be easily done in one line with std::erase (which has linear time complexity).

int removeElement(vector<int>& nums, int val) {
    std::erase(nums, val);
    return nums.size();
}

Answer 2

The time complexity of vector::size is constant (source code). But as Unmitigated explained, that is not the issue with the first version of your code.

With the working version you're actually lucky that the tests are only with vectors of sizes up to 100, as your algorithm is not efficient: it has a O(²) time complexity in the worst case. To illustrate, if the input nums has 100 elements, and they are all equal to the given val, then your algorithm will move 99 elements, then 98 elements, then 97, ..., so in total there will be 1+2+3+..+99 movements, which is 4950.

There is a hint in the code challenge: "The order of the elements may be changed.". This means that instead of shifting all values that come after an occurrence of val, you could take the last value from the (active part of the) vector and overwrite that occurrence with it. Then reduce the size and you're ready to continue. This eliminates the inner loop you have.

Here is a spoiler implementation of that idea:

class Solution { public: int removeElement(vector& nums, int val) { int size = nums.size(); for (int i = 0; i < size; i++) { if (nums[i] == val) { size--; nums[i] = nums[size]; i--; } } return size; } };

Another approach is to start with size equal to zero, and have i iterate the whole vector, and when there is a "good" nums[i], copy it to the size index, increase size. That way you make the values "jump" to their final destination, and at the end size will be what you want it to be.

Again an implemantation:

class Solution { public: int removeElement(vector& nums, int val) { int size = 0; for (int i = 0; i < nums.size(); i++) { if (nums[i] != val) { nums[size++] = nums[i]; } } return size; } };