Reduce the array such that each element appears at most 2 times

Given a sorted array arr, remove the duplicates in the array itself such that duplicates appear at most twice in the given array arr and print the new length and modified array arr.

Examples:

Input:
arr[] = {0, 0, 7, 7, 7, 7, 8, 9, 9}
Output:
7
arr[] ={0, 0, 7, 7, 8, 9, 9}
Explanation:
The modified arr does not cantain any element more than twice.

Input:
arr[] = {1, 2, 3, 3, 4, 4, 4, 4, 4 ,9, 9, 9 }
Output:
8
arr[] ={1, 2, 3, 3, 4, 4, 9, 9}

Approach:
The problem requires a simple array traversal and a two-pointer approach.
If the size of a given array is less than or equal to 2, then we simply print the size and the array.

If there are more than 2 elements present in the given array then:

• Take two pointers i and j and put them equal to 2.
• The fast pointer( i ) will be looped from 2 to n(size of arr)
• The slow pointer ( j ) is used as a separate index for the same array arr.
• If the value at index i is not equal to the value at index (j-2), we will update the array arr by incrementing the index j by one.
• else the fast pointer i will keep on incrementing.
• The value of j is the size of the modified array arr.

Implementation in C++:

// C++ program to remove duplicates 
// appearing more than twice 
#include <iostream>
using namespace std;

// This function returns 
// the new size of the modified array.
int removeDuplicates(int arr[], int n) {
    // If the size of the given array is less than 
    // or equal to 2
    if (n <= 2) {
        return n;
    } else {
        // Both pointers initialized to 2
        int i = 2, j = 2;
        for (int i = 2; i < n; i++) {
            // If the value at index i is 
            // not equal to the value at index j-2
            if (arr[i] != arr[j - 2]) {
                // Modifying the array
                arr[j++] = arr[i];
            }
        }
        // Return the size of 
        // modified array
        return j;
    }
}

// Driver code
int main() {
    int arr[] = {0, 0, 7, 7, 7, 7, 8, 9, 9};
    int n = sizeof(arr) / sizeof(arr[0]);

    int new_size = removeDuplicates(arr, n);
    // Print updated size
    cout << new_size << "\n";
    // Print updated array
    for (int i = 0; i < new_size; i++) {
        cout << arr[i] << " ";
    }

    return 0;
}

Output

7
0 0 7 7 8 9 9 

Time Complexity: O(n)
Auxiliary Space: O(1)