Problem Description
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 firstk
elements ofnums
contain the elements which are not equal toval
. The remaining elements ofnums
are not important as well as the size ofnums
. - Return
k
.
Examples
Example 1: Input: nums = [3,2,2,3], val = 3 Output: 2, nums = [2,2,_,_] Explanation: Your function should return k = 2, with the first two elements of nums being 2. It does not matter what you leave beyond the returned k (hence they are underscores). Example 2: Input: nums = [0,1,2,2,3,0,4,2], val = 2 Output: 5, nums = [0,1,4,0,3,_,_,_] Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4. Note that the five elements can be returned in any order. It does not matter what you leave beyond the returned k (hence they are underscores).
Python Solution
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
# Initialize the pointer for next position to place non-val element
k = 0
# Iterate through the array
for i in range(len(nums)):
# If current element is not val, place it at position k
if nums[i] != val:
nums[k] = nums[i]
k += 1
return k
Java Solution
class Solution {
public int removeElement(int[] nums, int val) {
// Initialize the pointer for next position to place non-val element
int k = 0;
// Iterate through the array
for (int i = 0; i < nums.length; i++) {
// If current element is not val, place it at position k
if (nums[i] != val) {
nums[k] = nums[i];
k++;
}
}
return k;
}
}
C++ Solution
class Solution {
public:
int removeElement(vector& nums, int val) {
// Initialize the pointer for next position to place non-val element
int k = 0;
// Iterate through the array
for (int i = 0; i < nums.size(); i++) {
// If current element is not val, place it at position k
if (nums[i] != val) {
nums[k] = nums[i];
k++;
}
}
return k;
}
};
JavaScript Solution
/**
* @param {number[]} nums
* @param {number} val
* @return {number}
*/
var removeElement = function(nums, val) {
// Initialize the pointer for next position to place non-val element
let k = 0;
// Iterate through the array
for (let i = 0; i < nums.length; i++) {
// If current element is not val, place it at position k
if (nums[i] !== val) {
nums[k] = nums[i];
k++;
}
}
return k;
};
C# Solution
public class Solution {
public int RemoveElement(int[] nums, int val) {
// Initialize the pointer for next position to place non-val element
int k = 0;
// Iterate through the array
for (int i = 0; i < nums.Length; i++) {
// If current element is not val, place it at position k
if (nums[i] != val) {
nums[k] = nums[i];
k++;
}
}
return k;
}
}
Complexity Analysis
- Time Complexity: O(n) where n is the length of the input array
- Space Complexity: O(1) as we modify the array in-place
Solution Explanation
This solution uses a two-pointer approach:
k
: Points to the position where we'll place the next element that's not equal to vali
: Iterates through the array
Key points of the solution:
- We only move elements that are not equal to val
- Elements equal to val are effectively "skipped"
- The order of remaining elements might change
- We don't need to worry about elements beyond position k
The approach is optimal because:
- It works in-place without requiring extra space
- Each element is examined exactly once
- Elements are moved at most once
- We don't need to maintain the relative order of elements