Array manipulation
Duplicates
Data structures
Sorting algorithms
Programming techniques

Move duplicates to the end of a sorted array

Master System Design with Codemia

Enhance your system design skills with over 120 practice problems, detailed solutions, and hands-on exercises.

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)O(n), where nn is the number of elements in the array.
  • Space Complexity: As the rearrangement is done in-place, the space complexity is O(1)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.

Course illustration
Course illustration

All Rights Reserved.