Remove Duplicates

In this article, we aim to solve the problem of removing duplicates from a sorted array. So this simply means that we have been given an array that is sorted in an ascending order and may have duplicate numbers. We just need to remove the duplicates and return the updated array.

Problem Statement:

Given a sorted array of integers, write a program to remove the duplicates present in the array.

Example:

Arr = [1,2,4,4,5,6,6,9]

Output: Arr = [1,2,4,5,6,9]

The C++ Code to solve this problem is as follows:

Solution 1:

Explanation:

·        In this function we are using a set data structure, named unique. The set data structure can only store unique elements.

·        We then loop through each element of the input array and insert every element into our set.

·        The Set automatically removes duplicates, so unique elements are stored.

Time Complexity: O(nlgn)

Space Complexity: O(N)

Solution 2:

Explanation:

·        We are using the two pointer technique over here. The two pointers here are i and j initialized to index 0 and 1 respectively.

·        The pointer i is used to track position for storing unique elements and j traverses the array for duplicates.

·        If arr[i] is not equal to arr[j], it means a new unique element is found. So then i is incremented, and the new unique element arr[j] is stored at index i.

Time Complexity: O(N)

Space Complexity: O(1)