Problem Statement
You are given an integer array nums and an integer val. Your task is to remove all occurrences of val from numsin-place, meaning you should modify the array directly. The relative order of the elements may change.
After removing all instances of val, return the number of elements that are not equal to val.
You do not need to worry about the elements that are beyond the new length of the array after removal. The goal is to modify the array in-place such that only the elements that are not equal to val remain in the first part of the array.
LeetCode Link
Constraints
0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100Examples
Example 1:
Input: [3, 2, 2, 3], val = 3
Output: 2
Explanation:
After removing all occurrences of val (which is 3), the array could look like [2, 2]. The length of the modified array is 2.Example 2:
Input: [0, 1, 2, 2, 3, 0, 4, 2], val = 2
Output: 5
Explanation:
After removing all occurrences of val (which is 2), the array could look like [0, 1, 4, 0, 3]. The length of the modified array is 5.Example 3:
Input: [1, 1, 1, 1], val = 1
Output: 0
Exaplanation:
After removing all occurrences of val (which is 1), the array becomes empty, so the length is 0.Different Approaches
1️⃣ Two Pointer (Optimal - When Order Doesn't Matter)
Intuition:
We can overwrite elements equal to val from the end since we don't care about the order.
Idea:
- Use two pointers:
i(start of array)n(effective array size)
- When
nums[i] == val, replacenums[i]withnums[n-1]and reducen. - Else, increment
i.
Code:
int removeElement(vector<int>& nums, int val) {
// Step 1: Initialize index `i` to start from the beginning of the array
int i = 0;
// Step 2: `n` keeps track of the current size of the array (as we remove elements)
int n = nums.size();
// Step 3: Loop through the array while `i` is less than the current size `n`
while (i < n) {
// Step 4: If the current element equals the value to remove
if (nums[i] == val) {
// Step 5: Replace it with the last element in the current range
nums[i] = nums[n - 1];
// Step 6: Decrease the size of the array (`n`) by 1
// (This effectively removes the last element we just copied)
--n;
// Step 7: Do NOT increase `i` here, because the new element at index `i`
// (swapped from the end) needs to be checked again
} else {
// Step 8: If it's not the target value, move to the next element
++i;
}
}
// Step 9: Return the new size of the array after removing all `val` elements
return n;
}
Complexity Analysis:
- Time Complexity:
O(n) - Space Complexity:
O(1)
2️⃣ Two Pointer (Stable Order)
Intuition:
Keep the order of remaining elements unchanged.
Approach:
- We need to traverse through the array and whenever we encounter an element that is not equal to
val, we should overwrite the elements in place, starting from the beginning of the array. - We can maintain a pointer
ito track where the nextnon-valelement should be placed. - We iterate over the array with a second pointer
j, and for every element that is not equal toval, we copy it to the indexiand incrementi.
At the end of the process, i will represent the number of elements that are not equal to val, and the first i elements of the array will be the modified array without val.
Dry Run:
Initialization:
val = 3
+-----+-----+-----+-----+
nums = | 3 | 2 | 2 | 3 |
+-----+-----+-----+-----+
0 1 2 3
i = 0Iterate over the nums with j from 0 to n - 1
i = 0
j = 0 (loop)
val = 3
+-----+-----+-----+-----+
nums = | 3 | 2 | 2 | 3 |
+-----+-----+-----+-----+
0 1 2 3
^
|
i
j
Check if nums[j] != val
nums[0] != 3
3 != 3
False
So, do nothingi = 0
j = 1 (loop)
val = 3
+-----+-----+-----+-----+
nums = | 3 | 2 | 2 | 3 |
+-----+-----+-----+-----+
0 1 2 3
^ ^
| |
i j
Check if nums[j] != val
nums[1] != 3
2 != 3
True
set nums[i] = nums[j]
nums[0] = nums[1]
nums[0] = 2
increment i (i = 1)i = 1
j = 2 (loop)
val = 3
+-----+-----+-----+-----+
nums = | 2 | 2 | 2 | 3 |
+-----+-----+-----+-----+
0 1 2 3
^ ^
| |
i j
Check if nums[j] != val
nums[2] != 3
2 != 3
True
set nums[i] = nums[j]
nums[1] = nums[1]
nums[1] = 2
increment i (i = 2)i = 2
j = 3 (loop)
val = 3
+-----+-----+-----+-----+
nums = | 2 | 2 | 2 | 3 |
+-----+-----+-----+-----+
0 1 2 3
^ ^
| |
i j
Check if nums[j] != val
nums[2] != 3
3 != 3
False
So, do nothing,Final State:
i = 2
j = 4 (out of bounds)
+-----+-----+-----+-----+
nums = | 2 | 2 | 2 | 3 |
+-----+-----+-----+-----+
0 1 2 3
^ ^
| |
i j
i represents the new length of the array after removing all occurrences of val.
Even though nums[2] still holds 2 from a previous step, it’s not considered part of the new array length. Only the first i elements are relevant.Code:
#include <iostream>
#include <vector>
using namespace std;
int removeElement(vector<int>& nums, int val) {
int i = 0; // Pointer for the next position to place non-val elements
// Traverse through the array
for (int j = 0; j < nums.size(); j++) {
if (nums[j] != val) {
nums[i] = nums[j]; // Place the non-val element at index i
i++; // Move i forward
}
}
return i; // i is the new length of the array after removing val
}
int main() {
vector<int> nums = {3, 2, 2, 3};
int val = 3;
int length = removeElement(nums, val);
cout << "New length: " << length << endl; // Output should be 2
cout << "Modified array: ";
for (int i = 0; i < length; i++) {
cout << nums[i] << " "; // The array should be [2, 2]
}
cout << endl;
return 0;
}Complexity Analysis:
- Time Complexity:
O(n), wherenis the size of the array. We only iterate through the array once. - Space Complexity:
O(1), as the operation is done in-place without using extra space.