Remove Element

NeetCode: Remove Element · LeetCode: 27. Remove Element · Difficulty: Easy

Given an integer array nums and a value val, remove all occurrences of val in place. The order of the remaining elements may change. Return k, the number of elements not equal to val; the first k slots of nums must hold those elements.

Example

Text

Input:  nums = [3, 2, 2, 3], val = 3               Output: k = 2, first k slots = [2, 2]
Input:  nums = [0, 1, 2, 2, 3, 0, 4, 2], val = 2   Output: k = 5, first k slots = [0, 1, 3, 0, 4]

Brute force: filter into a new array, then copy back

Collect the elements that differ from val into a fresh int[] and copy them back over the front of nums. This needs a second buffer of up to n items. A Java array cannot shrink, so the method returns k and the caller reads only the first k slots. The main method prints those slots with Arrays.copyOf(a, k), which copies the first k elements into a new array.

Java

import java.util.Arrays;

class Solution {
    public int removeElement(int[] nums, int val) {
        int[] kept = new int[nums.length];
        int count = 0;
        for (int x : nums) {
            if (x != val) {
                kept[count++] = x;
            }
        }
        for (int i = 0; i < count; i++) {
            nums[i] = kept[i];
        }
        return count;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] a = {3, 2, 2, 3};
        int k = s.removeElement(a, 3);
        System.out.println(k + " " + Arrays.toString(Arrays.copyOf(a, k)));
        int[] b = {0, 1, 2, 2, 3, 0, 4, 2};
        k = s.removeElement(b, 2);
        System.out.println(k + " " + Arrays.toString(Arrays.copyOf(b, k)));
        int[] c = {};
        k = s.removeElement(c, 1);
        System.out.println(k + " " + Arrays.toString(Arrays.copyOf(c, k)));
    }
}

Output

2 [2, 2]
5 [0, 1, 3, 0, 4]
0 []

Time: O(n). Space: O(n).

Optimal: two pointers, overwrite in place

Let write mark where the next kept element goes. Scan with read; whenever nums[read] != val, store it at nums[write] and advance write. Everything before write is always the kept prefix, and write ends as the answer k. No second buffer is needed.

Java

import java.util.Arrays;

class Solution {
    public int removeElement(int[] nums, int val) {
        int write = 0;
        for (int read = 0; read < nums.length; read++) {
            if (nums[read] != val) {
                nums[write] = nums[read];
                write++;
            }
        }
        return write;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] a = {3, 2, 2, 3};
        int k = s.removeElement(a, 3);
        System.out.println(k + " " + Arrays.toString(Arrays.copyOf(a, k)));
        int[] b = {0, 1, 2, 2, 3, 0, 4, 2};
        k = s.removeElement(b, 2);
        System.out.println(k + " " + Arrays.toString(Arrays.copyOf(b, k)));
        int[] c = {};
        k = s.removeElement(c, 1);
        System.out.println(k + " " + Arrays.toString(Arrays.copyOf(c, k)));
    }
}

Output

2 [2, 2]
5 [0, 1, 3, 0, 4]
0 []

Time: O(n). Space: O(1).

Both are linear in time; the second uses constant memory. Since write <= read, the scan only overwrites slots it has already examined.