Each element can appear only once or twice.
Example 1: Given nums = [1, 1, 1, 2, 2, 3, 3, 3] The function should return 6, because [1, 1, 2, 2, 3, 3]. As each element can appear only twice.
The solution is simple.
We shall 2 variables, one will hold the new length and other is used to iterate over the array.
As we are allowed at max 2 duplicates, we check the third element with the element 2 steps back of it. If the element is same then there exists an element that is repeated 3 times.
If if array[iter] == array [len-2], then array [iter]== array [len-2]== array [len-1]
Below is the pseudo code:
while (iterator < array_len) { if (array[iterator] != array[new_len-2]) { array[new_len++] = array[iterator]; } iterator++; }
We shall understand the algorithm with the help of an example:
Input: [1, 1, 1, 2, 2, 3]
pass = 1 Initial array = 1 1 1 2 2 3 iterator = 2 new_len = 2 if (array[iterator] != array[new_len-2]) if (1 != 1) false Hence iterator++ final array after pass 1 = 1 1 1 2 2 3
pass = 2 iterator = 3 new_len = 2 Initial array = 1 1 1 2 2 3 if (array[iterator] != array[new_len-2]) if (2 != 1) true then array[new_len++] = array[iterator]; iterator++ final array after pass 2 = 1 1 2 2 2 3
pass = 3 iterator = 4 new_len = 3 Initial array = 1 1 2 2 2 3 id (array[iterator] != array[new_len-2]) if (2 != 1) true then array[new_len++] = array[iterator]; iterator++ final array after pass 3 = 1 1 2 2 2 3
pass = 4 iterator = 5 new_len = 4 if (array[iterator] != array[new_len-2]) if (3 != 2) true then array[new_len++] = array[iterator]; iterator++ final array after pass 4 = 1 1 2 2 3 3 iterator = 5. Hence the result
Solution in C++
#include<iostream> #include<vector> using namespace std; int removeDuplicates(int array[], int array_len) { // If the array len is less than or equal to 2 then no need to search for duplicate if (array_len <= 2) { return array_len; } // as we are allowed up to 2 duplicates, we start from the third element. // then we check the third element with the element 2 steps before it. If it is same, // it means it is the 3rd duplicate element. int new_len = 2; int iterator = 2; while (iterator < array_len) { if (array[iterator] != array[new_len-2]) { array[new_len++] = array[iterator]; } iterator++; } return new_len; } int main() { int arr[] = {1, 1, 1, 2, 2, 3}; int array_len = 6; int result = removeDuplicates(arr, array_len); cout<<"The length of the array after the duplicates are removed = "<< result <<endl; }
Output:
The length of the array after the duplicates are removed = 5