Moving duplicates to the end of a sorted array is an intriguing problem that highlights the confluence of efficiency, simplicity, and ingenuity in algorithm design. This article delves into how to achieve this efficiently, with explanations, examples, and additional insights.

Understanding the Problem

The problem involves taking a sorted array and rearranging the elements such that all duplicate values are moved to the end of the array, maintaining the relative order of the elements. Particularly, only one instance of each unique element should remain in the originally sorted section.

Example

Given an array: `[1, 1, 2, 3, 3, 3, 4, 5, 5]`

The transformed array should be: `[1, 2, 3, 4, 5, 1, 3, 3, 5]`

Technical Explanation

The optimal algorithm leverages the inherent order of the sorted array. By using two pointers, we can efficiently perform in-place modifications. These pointers track the sorted section and identify duplicates as follows:

1. Initialization: Start with two pointers: `i` at the beginning and `j` one position ahead.
2. Traverse and Compare:
   • If the element at `i` is equal to the element at `j`, increment `j` since it's a duplicate.
   • If they are different, increment `i` and assign the value at `j` to `i`.
3. Completion:
   • Continue this until all elements are processed.
   • Now, the section from `i+1` to the end of the array will contain duplicates.

Algorithm Complexity

• Time Complexity: Since each element is processed exactly once, the time complexity is $O(n)$, where $n$ is the number of elements in the array.
• Space Complexity: As the rearrangement is done in-place, the space complexity is $O(1)$.

Sample Code

Here is a Python implementation of this approach:

• Empty Array: The function should return an empty array without any operations.
• Array with One Element: Directly return the array, as no duplicates are possible.
• All Elements Unique: The algorithm will traverse but make no changes to the array.