Remove Element

The key idea

Keep a slow write pointer that marks where the next kept value goes. A fast read pointer scans every element; whenever it finds a value that is not val, copy it to the slow pointer and advance the slow pointer. The slow pointer's final position is k, the count of kept elements.

Problem

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.

You must do this using only O(1) extra space.

Constraints

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

Examples

Input: nums = [3,2,2,3], val = 3 Output: 2, nums = [2,2,_,_]

Input: nums = [0,1,2,2,3,0,4,2], val = 2 Output: 5, nums = [0,1,4,0,3,_,_,_]

Complexity

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

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →