Remove Element easy

Problem Statement

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The relative order of the elements may be changed.

Since it is impossible to change the length of the array in place, you must return the new length of the array after removing all occurrences of val.

Consider the number of elements to return the new length of the array after removing all occurrences of val as the result, and the array is modified in place.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

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, 1, 3, 0, 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).

Steps

1. Initialization: Use two pointers, k (representing the index for the next element to be placed) and i (representing the index for iterating through the array). Initialize k to 0.

2. Iteration: Iterate through the array using the i pointer.

3. Comparison: For each element nums[i], compare it with the target value val.

4. Placement: If nums[i] is not equal to val, place it at index k of the array (nums[k] = nums[i]) and increment k. This effectively moves non-val elements to the beginning of the array.

5. Return: After iterating through the entire array, k will hold the new length of the array (the number of elements that are not equal to val). Return k.

Explanation

The algorithm uses a two-pointer approach to efficiently remove elements in-place. The k pointer keeps track of the index where the next element that is not equal to val should be placed. The i pointer iterates through the array. When an element different from val is encountered, it is moved to the kth position, and k is incremented. Elements beyond the kth position are irrelevant as they represent the removed elements. The final value of k accurately reflects the number of elements remaining after removing all occurrences of val.

Code

class Solution {
    public int removeElement(int[] nums, int val) {
        int k = 0; // Pointer for the next position to place a non-val element
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[k] = nums[i];
                k++;
            }
        }
        return k;
    }
}

Complexity

• Time Complexity: O(n), where n is the length of the input array. We iterate through the array once.
• Space Complexity: O(1). We use only a constant amount of extra space for the pointers k and i.