LeetCode Remove Element: Swap with Two Pointers

Overview

LeetCode Remove Element: Linear scan the array, swap the element of the given value with the last one in the array that are maintained by two pointers.

LeetCode Remove Element

Given an array and a value, remove all instances of that value in place and return the new length.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Solution: Swap with Two Pointers

Very basic practice of using swap. Using two pointers head pointing to the beginning of the array and tail pointing to the end of the array, advance the head pointer and check whether it should be removed, if so, then just swap(A[head], A[tail]), and move the tail pointer to point to A[tail-1], here you don’t need to advance head immediately since you still need to check the swapped value, if you encounter a value that is not required to be removed, then you advance the head pointer to check the next one. The following code is accepted by LeetCode OJ to pass this Remove Element problem:

class Solution {

    public:
        int removeElement(int A[], int n, int elem) {
            int i = 0;
            while (i < n) {
                if (A[i] == elem) {
                    swap(A[i], A[--n]);
                }
                else
                    ++i;
            }
            return n;
        }
};

The following two Java implementations could be accepted by LeetCode OJ to pass this Remove Element problem as well and you can also check this related problem of linked list for further reference, LeetCode Remove Linked List Elements: Iterative vs Recursive:

1) The first one is similar to the C++ version.

public class Solution {
	private void swap(int [] array,
                          int i, int j) {
		int t = array[i];
		array[i] = array[j];
		array[j] = t;
	}

	public int removeElement(
			int[] nums,
			int val) {

		int j = nums.length;
		int i = 0;

		while (i < j) {
			if (nums[i] == val) {
				swap(nums, i, --j);
			} else {
				++i;
			}
		}
		return j;
	}
}

2) The second one is implemented from another different angle that, treat the input as both the source and the destination array from the starting, and assign all the values that is not equal to the given value to the new array beginning from the start of the input, see the following code:

public class Solution {

    public int removeElemet(int[] nums, int val) {

	int l = 0;

	for (int i = 0; i < nums.length; ++i) {
		if (nums[i] != val) {
			nums[l++] = nums[i];
		}
	}
	return l;
}

Summary

LeetCode Remove Element: Linear scan the array, swap the element of the given value with the last one in the array that are maintained by two pointers.

Written on April 18, 2013