Move duplicates to the end of a sorted array
Data Structures & Algorithms practice on Codemia
Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.
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:
- Initialization: Start with two pointers: `i` at the beginning and `j` one position ahead.
- 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`.
- 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 , where is the number of elements in the array.
- Space Complexity: As the rearrangement is done in-place, the space complexity is .
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.
Related reading
- moving an object from point to point in a linear path
- Multi-Class SVM one versus all
- Multi-start and Multi-end shortest path set
- multi-way merge vs 2-way merge
- Moving messages between queues rabbitMQ
- Multi-Class SVM. Binary Decision Tree. Issues with LIBSVM
- Multiple Consensus in Simple Paxos
- Multiple Date range comparison for overlap how to do it efficiently?

DSA Fundamentals
Master algorithmic patterns and data structures through hands-on LeetCode-style problems - from arrays and hashing to dynamic programming and advanced graphs.
View the courseTrack what you have practised
A free account saves your progress, solutions and study plan across every problem on Codemia.
Data Structures & Algorithms practice on Codemia
Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.