leetcode-150

2. Remove Element

Problem Statement

---

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

---

Solution

Algorithm Explanation

The goal is to remove all occurrences of val from the array nums in-place and return the count of remaining elements. The algorithm should ensure that the first k elements of nums contain only elements not equal to val. The order of elements can be changed, and elements beyond k are not relevant.

Approach: Two-Pointer Technique

1. Use Two Pointers:
   • A writeIndex pointer to track where the next non-val element should be placed.
   • A readIndex pointer to iterate over the array.
2. Traverse the Array (readIndex):
   • If nums[readIndex] is not equal to val, move it to nums[writeIndex] and increment writeIndex.
3. Final Step:
   • Return writeIndex, which represents the count of elements that are not equal to val.

Time & Space Complexity

• Time Complexity: (O(n)) (We iterate through the array once)
• Space Complexity: (O(1)) (No extra space is used apart from variables)

---

JavaScript Implementation

function removeElement(nums, val) {
    let writeIndex = 0; // Pointer to place the next valid element

    for (let readIndex = 0; readIndex < nums.length; readIndex++) {
        if (nums[readIndex] !== val) {
            nums[writeIndex] = nums[readIndex];
            writeIndex++;
        }
    }
    
    return writeIndex;
}

Example Usage

let nums1 = [3, 2, 2, 3];
let val1 = 3;
let k1 = removeElement(nums1, val1);
console.log(k1, nums1.slice(0, k1)); // Output: 2, [2, 2]

let nums2 = [0, 1, 2, 2, 3, 0, 4, 2];
let val2 = 2;
let k2 = removeElement(nums2, val2);
console.log(k2, nums2.slice(0, k2)); // Output: 5, [0, 1, 3, 0, 4]

How the Code Works

1. Initialize writeIndex = 0 (starting position for non-val elements).
2. Loop through the array (readIndex from 0 to nums.length - 1):
   • If nums[readIndex] !== val, copy nums[readIndex] to nums[writeIndex] and increment writeIndex.
3. Return writeIndex, which represents the new length of the filtered array.

Previous

Next

This site is open source. Improve this page.