Question 2: 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.

Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int val = ...; // Value to remove
int[] expectedNums = [...]; // The expected answer with correct length.
                            // It is sorted with no values equaling val.

int k = removeElement(nums, val); // Calls your implementation

assert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

If all assertions pass, then your solution will be accepted.

Example 1:

Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints:

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 50
• 0 <= val <= 100

My Solution :

My Planning is to choose two pointers and check four conditions:

1. If the element at index i is the target value while the element at the index j is not, we swap them.
2. If the element at index i is not the target value and the element at the index j is the target value, we increment i and k, and decrement j. This condition is optimal, indicating correct positioning.
3. If both elements are the target values, we simply decrease the index j since it’s positioned correctly.
4. If neither element is the target value, we increment the index i, as it’s in the correct position.

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int i=0, j= nums.size()-1;
        int k=0;

        if(j == -1){
            return 0;
        }
        while(i<=j){
            if(nums[i] == val && nums[j] != val){
                nums[i] ^= nums[j];
                nums[j] ^= nums[i];
                nums[i] ^= nums[j];
            }
            else if(nums[i]!=val && nums[j]== val){
                i++;
                j--;
                k++;
            }
            else if(nums[i] == val && nums[j] == val){
                j--;
            }
            else{
                i++;
                k++;
            }
        }

        return k;
    }
};

Time Complexity : O(n)

Space Complexity : O(1)

Optimal Solution

How Does It Work?

1. Iterating Through the List:
   • The method starts by initializing two variables: i and n.
   • i is used to keep track of where we should place elements that we want to keep after removing val.
   • n stores the total number of elements in the list.
2. Removing Elements:
   • Next, we loop through each element of the list using a for loop. We use a variable j to keep track of the current position in the list.
   • Inside the loop, we check if the current element nums[j] is not equal to the value we want to remove (val).
   • If nums[j] is not equal to val, we copy this element to the position indicated by i and then increment i.
   • This effectively means we’re skipping over the elements we want to remove and copying only the elements we want to keep to the beginning of the list.
3. Returning the Result:
   • Finally, we return the value of i, which indicates the new length of the list after removing val.

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

Time Complexity : O(n)

Space Complexity : O(1)