Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Given nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.

It doesn’t matter what you leave beyond the returned length.

Example 2:

Given nums = [0,0,1,1,1,1,2,3,3],

Your function should return length = 7, with the first seven elements of nums being modified to 0, 0, 1, 1, 2, 3 and 3 respectively.

It doesn’t matter what values are set beyond the returned length.

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 exist 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

The length of the array after the duplicates are removed = 5

Solution in C++

/*
* File     :  Remove_Duplicates_from_Sorted_Array.cpp
*/
#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