Removing Duplicate from Sorted Array using C++

Overview

Removing duplicates is by far one of the most important requirements in many software and real-life applications ranging from information gathering, and research analysis to AI/ML and IoT applications. In this coding challenge put together I4G, I will be looking at how I come to implement duplicate removal from a sorted array using the C++ programming language.

Thought Process

The main task in this challenge is to remove duplicates from already sorted array in ancending order e.g 1, 2, 3, 4, 5, 6, 7 ...

Looking at this from a Linear Search algorithm perspective, we are basically going through each elements of the array and checking if an element says element k is the same with the previous element say j. We, therefore, make use of any element that is not the same as its previous counterpart.

for (int i = 1; i < nums.size(); i++){
 if(nums[i-1] != nums[i]){
                nums[counter] = nums[i];
}

In the case of this task where no extra memory is to be allocated, a simple approach is to use a placeholder variable to keep track of the array elements, this just inserts the array element that is not the same with the previous element into the next array element meaning it overwrites whatever is already at that possition. For example say we have an array [ 2, 2, 3, 4, 4, 5, 5, 6], we loop through the elements of this array, at the third iteration, we come across 3 which is not the same with the previous element, and we set the secod element to be 3 and increment our placeholder array index variable so that if a similar scenerio occurrs again, we will set the third element to the non-duplicate element.

int counter = 1;
        for (int i = 1; i < nums.size(); i++){
            if(nums[i-1] != nums[i]){
                nums[counter] = nums[i];
                counter++;
            }
        }

Conclusion

With this implementation, memory is saved and we have a fast run time. Let N be the size of the input array.

Time Complexity: O(N), since we only have 2 pointers, and both the pointers will traverse the array at most once.

Space Complexity: O(1), since we are not using any extra space.

Acknowledgement I4G10DaysOfCodeChallenge