Fuck LeetCode > Array > 27. Remove Element > Solved in Java, Python, C++, JavaScript, C#, Go, Ruby > Repost or Contribute
LeetCode link: 27. Remove Element, difficulty: Easy.
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
numssuch that the firstkelements ofnumscontain the elements which are not equal toval. The remaining elements ofnumsare not important as well as the size ofnums. - Return
k.
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).
Constraints:
0 <= nums.length <= 1000 <= nums[i] <= 500 <= val <= 100
Hint 1
The problem statement clearly asks us to modify the array in-place and it also says that the element beyond the new length of the array can be anything. Given an element, we need to remove all the occurrences of it from the array. We don't technically need to remove that element per-say, right?
Hint 2
We can move all the occurrences of this element to the end of the array. Use two pointers!
Hint 3
Yet another direction of thought is to consider the elements to be removed as non-existent. In a single pass, if we keep copying the visible elements in-place, that should also solve this problem for us.
Intuition
Two pointers, one on the left and one on the right. The left one points to the head of the array, and the right one points to the tail of the array.- If the value pointed by the left pointer is found to be equal to val, and the value pointed by the right pointer is not equal to val, then swap the two the values.
- This method is easy to think of, but the amount of code is more than the
fast and slow pointers.
Complexity
Time complexity
O(N)
Space complexity
O(1)
Java #
class Solution {
public int removeElement(int[] nums, int val) {
var left = 0;
var right = nums.length - 1;
while (left <= right) {
if (nums[left] != val) {
left += 1;
continue;
}
if (nums[right] == val) {
right -= 1;
continue;
}
nums[left] = nums[right];
left += 1;
right -= 1;
}
return left;
}
}
Python #
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
left = 0
right = len(nums) - 1
while left <= right:
if nums[left] != val:
left += 1
continue
if nums[right] == val:
right -= 1
continue
nums[left] = nums[right]
left += 1
right -= 1
return left
C++ #
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
if (nums[left] != val) {
left += 1;
continue;
}
if (nums[right] == val) {
right -= 1;
continue;
}
nums[left] = nums[right];
left += 1;
right -= 1;
}
return left;
}
};
JavaScript #
var removeElement = function (nums, val) {
let left = 0
let right = nums.length - 1
while (left <= right) {
if (nums[left] != val) {
left += 1
continue
}
if (nums[right] == val) {
right -= 1
continue
}
nums[left] = nums[right]
left += 1
right -= 1
}
return left
};
C# #
public class Solution
{
public int RemoveElement(int[] nums, int val)
{
int left = 0;
int right = nums.Length - 1;
while (left <= right)
{
if (nums[left] != val)
{
left += 1;
continue;
}
if (nums[right] == val)
{
right -= 1;
continue;
}
nums[left] = nums[right];
left += 1;
right -= 1;
}
return left;
}
}
Go #
func removeElement(nums []int, val int) int {
left := 0
right := len(nums) - 1
for left <= right {
if nums[left] != val {
left += 1
continue
}
if nums[right] == val {
right -= 1
continue
}
nums[left] = nums[right]
left++
right--
}
return left
}
Ruby #
def remove_element(nums, val)
left = 0
right = nums.size - 1
while left <= right
if nums[left] != val
left += 1
next
end
if (nums[right] == val)
right -= 1
next
end
nums[left] = nums[right]
left += 1
right -= 1
end
left
end
Other languages
Welcome to contribute code to our GitHub repository, thanks! The location of this solution is 27. Remove Element.Intuition of solution 2: Fast & Slow Pointers Approach
- The
fast and slow pointer approachmeans that both pointers initially point to the head of the array, and then one pointer moves faster. - For this question, under what circumstances should the fast pointer move faster? When the value corresponding to the fast pointer is equal to val. The slow pointer must ensure that each value it passes through is not equal to val.
- The swap of values occurs when the value pointed by the fast pointer is not equal to val, and the value pointed by the slow pointer is equal to val.
- This method is not easy to think of, but it is more concise than
two pointers of left and right.
Complexity
Time complexity
O(N)
Space complexity
O(1)
Java #
class Solution {
public int removeElement(int[] nums, int val) {
var slowIndex = 0;
for (var num : nums) { // This line is the most important. You'd better memorize it.
if (num != val) {
nums[slowIndex] = num;
slowIndex += 1;
}
}
return slowIndex;
}
}
Python #
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
slow_index = 0
for num in nums: # This line is the most important. You'd better memorize it.
if num != val:
nums[slow_index] = num
slow_index += 1
return slow_index
C++ #
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
auto slow_index = 0;
for (auto num : nums) { // This line is the most important. You'd better memorize it.
if (num != val) {
nums[slow_index] = num;
slow_index += 1;
}
}
return slow_index;
}
};
JavaScript #
var removeElement = function (nums, val) {
let slowIndex = 0
nums.forEach((num) => { // This line is the most important. You'd better memorize it.
if (num != val) {
nums[slowIndex] = num
slowIndex += 1
}
})
return slowIndex
};
C# #
public class Solution
{
public int RemoveElement(int[] nums, int val)
{
int slowIndex = 0;
foreach (int num in nums) // This line is the most important. You'd better memorize it.
{
if (num != val)
{
nums[slowIndex] = num;
slowIndex += 1;
}
}
return slowIndex;
}
}
Go #
func removeElement(nums []int, val int) int {
slowIndex := 0
for _, num := range nums { // This line is the most important. You'd better memorize it.
if num != val {
nums[slowIndex] = num
slowIndex += 1
}
}
return slowIndex
}
Ruby #
def remove_element(nums, val)
slow_index = 0
nums.each do |num| # This line is the most important. You'd better memorize it.
if num != val
nums[slow_index] = num
slow_index += 1
end
end
slow_index
end