LeetCode. 27. Remove Element

[Link] https://leetcode.com/problems/remove-element/

Approach

Scan nums from left to right and keep a write index for the next value that should remain. When the current value is not val, copy it to nums[write] and advance write. Values equal to val are skipped.

Before each element is processed, the first write positions contain exactly the values unequal to val encountered so far, in their original order. Copying a retained value to the write position cannot disturb any unread element because write never exceeds the current scan position. When the scan finishes, write is the new length and the prefix nums[0..write) is the stable filtered result. The suffix is unspecified and must not be relied on.

The method takes O(N) time and O(1) extra space.

Java

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
    public int removeElement(int[] nums, int val) {
        int write = 0;

        for (int value : nums) {
            if (value != val) {
                nums[write++] = value;
            }
        }

        return write;
    }
}