Remove Element
LeetCode #27 · Easy · Arrays · C++ solution with worked-out approach and complexity analysis.
Approach
Two-pointer (fast-slow)
Use 'k' as the position to write the next element that is not equal to val. Iterate through the array; when nums[i] != val, copy it to nums[k] and increment k. This works in O(n) time and O(1) extra space.
Time
O(n)
Space
O(1)
Problem description(from LeetCode)
Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements can be changed. After removal, return the new length k. Elements beyond the first k elements are not important.
Examples
Example 1
- Input:
- nums = [3,2,2,3], val = 3
- Output:
- k = 2, nums = [2,2,_,_]
- Note:
- Your function should return k = 2, with the first two elements of nums being 2.
Constraints
- •0 <= nums.length <= 100
- •0 <= nums[i] <= 50
- •0 <= val <= 100
C++ Solution
solution.cpp
class Solution {
public:
int removeElement(vector<int> &nums, int val) {
int k = 0;
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] != val) {
nums[k++] = nums[i];
}
}
return k;
}
};