Removing Duplicates from a Sorted Array in C++

Removing duplicates from a sorted integer array is a common problem that can be efficiently solved in-place. This ensures minimal additional memory usage and maintains the relative order of elements. Here, I'll explain a C++ solution to this problem step-by-step.

Problem Explanation

Given a sorted integer array nums, we need to remove duplicates such that each unique element appears only once while retaining their original order. The goal is to return the number of unique elements 'i', and the first 'i' elements of the modified array should contain these distinctive elements.

Approach 1: 

To solve this problem, we can use a set. Since a set can only contain unique elements, we will insert each element of the array into a set and then replace the starting elements with the elements of the set. The time complexity for inserting elements into the set is O(nlogn), and for printing the elements of the set, it is O(n). Therefore, the overall time complexity of this approach is O(nlogn) + O(n).

Code:

#include <bits/stdc++.h>

using namespace std;

int removeDuplicates(vector<int> &nums)

{

    set<int> st;

    for (int i = 0; i < nums.size(); i++)

    {

        st.insert(nums[i]);

    }

    int idx = 0;

    for (auto i : st)

    {

        nums[idx] = i;

        idx++;

    }

    return idx;

}

int main()

{

    int n;

    cin >> n;

    vector<int> nums(n);

    for (int i = 0; i < n; i++)

    {

        cin >> nums[i];

    }

    int k = removeDuplicates(nums);

    for (int i = 0; i < k; i++)

    {

        cout << nums[i] << " ";

    }

    return 0;

}

Output:

Approach 2:

The approach uses two standard library functions from the C++ STL: std::unique and std::vector::erase. The std::unique function is used to rearrange the elements in the range [first, last) such that each unique element appears only once and returns an iterator to the end of the unique range. The function works by removing consecutive duplicate elements. It doesn't actually delete elements from the container but moves the duplicates to the end and returns an iterator pointing to the new logical end of the unique sequence. The erase function is used to remove elements from the vector from the iterator returned by std::unique to the actual end of the vector. This effectively trims the vector to contain only the unique elements.

The std::unique function operates in O(n) time complexity, where n is the number of elements in the vector. This is because it makes a single pass through the vector to move the duplicate elements. The erase function also operates in O(n) time complexity in the worst case. This is because erasing elements from the end of the vector involves shifting elements to close the gap, which can take linear time. Overall, the combined time complexity is O(n) + O(n) = O(n), where n is the number of elements in the vector. This makes the approach efficient for removing duplicates from a sorted vector in linear time.

Code:

#include <bits/stdc++.h>

using namespace std;

int removeDuplicates(vector<int> &nums)

{

    nums.erase(unique(nums.begin(), nums.end()), nums.end());

    return nums.size();

}

int main()

{

    int n;

    cin >> n;

    vector<int> nums(n);

    for (int i = 0; i < n; i++)

    {

        cin >> nums[i];

    }

    int k = removeDuplicates(nums);

    for (int i = 0; i < k; i++)

    {

        cout << nums[i] << " ";

    }

    return 0;

}

Output:

Approach 3 (Optimal Solution): 

This approach uses the two-pointer technique to remove duplicates from a sorted array in-place. 

Algorithm:

1. int i = 0; - This pointer i keeps track of the position where the next unique element should be placed.
2. for(int j = 0; j < nums.size(); j++) - The j pointer iterates through the entire array.
3. if(nums[j] != nums[i]) - Check if the current element nums[j] is different from the element at the position i.
4. If they are different, it means nums[j] is a unique element that hasn't been encountered in the current subarray from 0 to i.
5. nums[i + 1] = nums[j]; - Place the unique element nums[j] in the position i + 1.
6. i++; - Increment i to reflect that a new unique element has been placed in the array.
7. After the loop completes, i points to the last unique element. The number of unique elements is i + 1.

Code:

#include <bits/stdc++.h>

using namespace std;

int removeDuplicates(vector<int>& nums) {

        int i = 0;

        for(int j=0;j<nums.size();j++){

            if(nums[j] != nums[i]){

                nums[i+1] = nums[j];

                i++;

            }

        }

        return i+1;

    }

int main()

{

    int n;

    cin >> n;

    vector<int> nums(n);

    for (int i = 0; i < n; i++)

    {

        cin >> nums[i];

    }

    int k = removeDuplicates(nums);

    for (int i = 0; i < k; i++)

    {

        cout << nums[i] << " ";

    }

    return 0;

}

Example Execution:

Consider the input array nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]:

1. Initial state:
• i = 0
• nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
2. Iteration:
• j = 0: nums[0] equals nums[0], no change.
• j = 1: nums[1] equals nums[0], no change.
• j = 2: nums[2] (1) differs from nums[0] (0), update nums[1] to 1, increment i to 1.
• nums = [0, 1, 1, 1, 1, 2, 2, 3, 3, 4]
• j = 3: nums[3] equals nums[1], no change.
• j = 4: nums[4] equals nums[1], no change.
• j = 5: nums[5] (2) differs from nums[1] (1), update nums[2] to 2, increment i to 2.
• nums = [0, 1, 2, 1, 1, 2, 2, 3, 3, 4]
• j = 6: nums[6] equals nums[2], no change.
• j = 7: nums[7] (3) differs from nums[2] (2), update nums[3] to 3, increment i to 3.
• nums = [0, 1, 2, 3, 1, 2, 2, 3, 3, 4]
• j = 8: nums[8] equals nums[3], no change.
• j = 9: nums[9] (4) differs from nums[3] (3), update nums[4] to 4, increment i to 4.
• nums = [0, 1, 2, 3, 4, 2, 2, 3, 3, 4]
3. Final state:
• i = 4
• The unique elements are [0, 1, 2, 3, 4] and the function returns i + 1 = 5.

Output:

Time Complexity:

O(n), where n is the number of elements in the array. This is because we only make a single pass through the array. 

This approach efficiently removes duplicates in a sorted array while maintaining the relative order of the elements.