Question

LeetCode Link | 27. Remove Element | Easy

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:

1
2
3
4
5
6
7
8
9
10
11
12
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.

Constrains

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

Examples

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 = [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).

Solution Approach

Method: Fast & slow pointer

Constrains

  • In-Place Modification
  • Return Value Interpretation

The algorithm modifies the array in place, which means it alters the original array. This is important if the original array needs to be preserved for other operations or purposes. Also, the “removal” is conceptual—elements beyond the returned length are still part of the array but are considered irrelevant. This could lead to misunderstandings if the function’s behavior is not properly documented or understood.

Concept Explanation

This is a common technique that used in Array and Linked List as called two-pointer technique or known as the fast-slow pointer method to solve the problem of removing all instances if a specific value from an array in-place.

Two Pointer Definition: There are two pointers used in the algorithm:

  • fastIndex: This pointer iterates through the entire array, checking each element to see if it equals val.
  • slowIndex: This pointer tracks the position where the next element that isn’t equal to val should be placed. It moves only when an element that isn’t the target value is found.

Iteration: The fastIndex iterates through each element of the array (nums). If the current element (nums[fastIndex]) is not equal to val, the algorithm performs two actions:

  • It assigns the value at fastIndex to the position at slowIndex, effectively “saving” the non-target value in the part of the array that forms the result.
  • It increments slowIndex to prepare it for the next non-target value.

Scenario 1: Simple Copy

If nums[fastIndex] is equal to val, fastIndex is incremented without changing slowIndex, effectively skipping the target value and leaving it out of the new, condensed version of the array.

Scenario 2: Skip index if need remove

The loop continues until fastIndex has traversed the entire array. The slowIndex will then represent the length of the new array that does not contain val, and the values from the start of the array to slowIndex - 1 will be the desired elements.

Code

  • Time complexity: O(n)
  • Space complexity: O(1)

TypeScript

1
2
3
4
5
6
7
8
9
10
function removeElement(nums: number[], val: number): number {
    let slowIndex = 0, fastIndex = 0;
    while (fastIndex < nums.length) {
       if (nums[fastIndex] !== val) {
          nums[slowIndex++] = nums[fastIndex];
       }
       fastIndex++;
    }
    return slowIndex;
}

Conclusion

This method is particularly efficient for tasks where elements need to be removed from an array or list without maintaining the order of the other elements, or where the order of the resulting elements does not matter beyond the elements that need to be removed.