Thoughts about a two pointer array problem - #27 LeetCode

Wenhan — Tue, 09 Jul 2019 16:42:54 +0000

Please check the link first for the details of the problem.
Remove Element

Given an array nums and a value val, remove all instances of that value in-place and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Given nums = [3,2,2,3], val = 3, your function should return length = 2, with the first two elements of nums being 2. It doesn't matter what you leave beyond the returned length.

The first thought to this problem was a naive solution — to create another array for filtered values. However, under the requirement of memory usage. We have to modify the input array in place.
The output should be a number N which represents the valid length of the array, which means the first N elements should not have the val.

I decided to use two pointer method to solve this problem.

[ ] Why? With two pointers index, targetIndex, index representing the index of nums loop function and targetIndex representing the result array index which starts from 0. Imagine you are operating a new array based on the original array, you are just moving the qualified values forward into the new array. In the loop of nums, if nums[index] is not equal to val, we move the values to the new array, nums[targetIndex] = nums[index] and increment the targetIndex by 1 to expand the new array. If nums[index]is equal to val we just skip the the value movement, so the new array will only include the qualified values.

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    const arrLength = nums.length;
    if (arrLength === 0)
        return 0;
    let targetIndex = 0;
    for(let index = 0; i < arrLength; index++) {
        if (nums[index] !== val)
            nums[targetIndex++] = nums[index];}
    return targetIndex;
};

DEV Community: Wenhan

Thoughts about a two pointer array problem - #27 LeetCode