Remove Duplicates from Sorted Array II

class Solution {
public:
    int processDuplicates(vector<int>& elements) {
        if (elements.empty()) return 0;

        int read = 1;       // Index for reading elements
        int write = 1;      // Index to write to the array
        int currentCount = 1;  // Current number duplicates count

        while (read < elements.size()) {
            if (elements[read] == elements[read - 1]) {
                currentCount++;
                if (currentCount > 2) {
                    read++;
                    continue;
                }
            } else {
                currentCount = 1;
            }
            elements[write] = elements[read];
            write++;
            read++;
        }

        elements.resize(write);
        return write;
    }
};

The given C++ code provides a solution for removing excess duplicates from a sorted array, allowing a maximum of two occurrences for each element. Below is the step-by-step breakdown of how the code operates:

1. Define a method processDuplicates that receives a reference to a vector of integers.
2. Check if the input vector elements is empty. If yes, return 0 as there are no elements to process.
3. Initialize two pointers:
   • read starts at 1, used for reading through the vector.
   • write also starts at 1, used to indicate the position to write the allowed duplicates into the array.
4. Set currentCount to 1 to track the frequency of the current element.
5. Begin a loop to iterate through the array starting from the second element:
   • Increment the currentCount if the current (read pointer) and previous element (read-1) are the same.
   • If currentCount exceeds 2, skip the current element by incrementing the read pointer and continue to next iteration.
   • If a new element is encountered (or currentCount is acceptable), reset currentCount to 1, and copy the element at the read pointer to the position indicated by the write pointer.
   • Increment both write and read pointers.
6. After the loop, reduce the size of the input vector to the value of write pointer which indicates the number of elements in the modified array.
7. Return the length of the modified array from the method.

This solution efficiently maintains two pointers and controls the number of allowed duplicates in a single linear pass, ensuring that space complexity is minimized, with changes made in-place.

class Solution {

    public int eliminateDuplicates(int[] elements) {
        if (elements.length == 0) {
            return 0;
        }

        int read = 1;
        int write = 1;
        int frequency = 1;

        while (read < elements.length) {
            if (elements[read] == elements[read - 1]) {
                frequency++;
                if (frequency > 2) {
                    read++;
                    continue;
                }
            } else {
                frequency = 1;
            }
            elements[write] = elements[read];
            write++;
            read++;
        }

        return write;
    }
}

The Java program presented tackles the problem of removing excess duplicates from a sorted array, where each element can appear at most twice. Follow these straightforward steps in the code to understand the functionality:

1. Check if array is empty, if so, return 0.
2. Initialize two pointers, read and write, both set to the index 1, and frequency to count the occurrences of each element, starting at 1.
3. Use a loop to iterate through the array:
   • Compare the current element with the previous one.
   • If they are the same, increment the frequency.
   • If frequency is greater than 2, just move the read pointer forward and continue to next iteration.
   • If a new element is found or the frequency of the current element is less than or equal to 2, reset frequency to 1, and write the value of read pointer's element to the write pointer's position.
   • Move both pointers forward.
4. After completing loop, write pointer represents the length of the modified array without excess duplicates.
5. Return the new length of the array as indicated by the write pointer.

This method efficiently adjusts the array in-place to ensure no element occurs more than twice, while only utilizing a single pass through the array and O(1) extra space for the frequency and pointer variables.

class Solution:
    def remove_extra_duplicates(self, numbers: List[int]) -> int:
        if not numbers:
            return 0
        
        current = 1
        insertPosition = 1
        occurrences = 1
        
        while current < len(numbers):
            if numbers[current] == numbers[current - 1]:
                occurrences += 1
                if occurrences > 2:
                    current += 1
                    continue
            else:
                occurrences = 1
            numbers[insertPosition] = numbers[current]
            insertPosition += 1
            current += 1
        
        del numbers[insertPosition:]
        return len(numbers)

This solution defines a Python class Solution which includes a method remove_extra_duplicates to tackle the issue of removing extraneous duplicates from a sorted array, allowing at most two occurrences of each number. The method works as follows:

• Initialize insertPosition and current pointers to the index 1, and occurrences to 1 to track the number of occurrences of the current number.
• Iterate over the list of numbers using the current pointer:
  • If the current number equals the previous number, increment the occurrences counter.
  • If occurrences exceeds 2, skip the current element by simply incrementing the current pointer without updating the insertPosition.
  • If the current number does not equal the previous one, reset the occurrences to 1.
  • Assign the current number to the position indicated by insertPosition and increment both insertPosition and current.
• After completing the iterations, the numbers after the insertPosition index are redundant and are removed using del numbers[insertPosition:].
• Finally, return the modified length of the array using len(numbers), which represents the length of the array with at most two occurrences of each number.

This method ensures that the array retains up to two duplicates of each element while maintaining sorted order without requiring additional space for the result, as the modifications are done in-place.