Remove Duplicates from Sorted Array

In this blog, we will discuss the different approaches to remove duplicates from sorted array. Before starting with the approaches, let’s see how these types of questions help you to grab your dream job.

You need to be familiar with the kinds of questions that will be asked in your technical interviews if you want to succeed in the hiring process for a product-based corporation like Google, Amazon, or Microsoft. These businesses rely on their interview process to choose individuals with an in-depth understanding of computer science and engineering fundamentals as the race for engineering talent heats up every year. In order to do this, they employ a range of examinations to aid them in learning about both their fundamental comprehension of computer science and their capacity for handling challenging issues. We’ll look at one of these issues in this post and offer remedies along with the related code.

How to Remove Duplicates from Sorted Array?

Given an integer array sorted in non-decreasing order, remove the duplicates such that the unique element appears only once.

For example :

Array = {2,3,4,4,5,6,6,6,8,8}
Output= 6

Solution Approaches to Remove Duplicates from Sorted Array

There are three ways to deal with this problem. Following are some detailed explanations of both, along with C++, Java, and Python source codes:

Method 1: Brute force approach using extra memory

We could make a new array the same size as the original array, compare each value with its neighbour, and then remove duplicates in parallel. If a match was found, we would add the value to the auxiliary array and take away one instance of it from the primary array.

In order to be able to return the total number of different values after our process is finished, we will also keep track of how many unique values are currently present in the original array. Finally, we will return our original array after copying all of its contents back into the auxiliary array.

Algorithm

  • Create an auxiliary array of the same size as original
  • Compare each element of the original array with its neighbour element
  • If elements do not match
    • Copy the unique element into an auxiliary array maintaining the count variable
    • Copy the elements of the auxiliary array back to the original array
  • Return the new size of the array
#include <iostream>
using namespace std;

int removeDuplicates(int arr[], int n)
{
    if (n == 0 || n == 1)
        return n;

    int temp[n];

    int j = 0;
    for (int i = 0; i < n - 1; i++)
        if (arr[i] != arr[i + 1])
            temp[j++] = arr[i];

    temp[j++] = arr[n - 1];

    for (int i = 0; i < j; i++)
        arr[i] = temp[i];

    return j;
}

int main()
{
    int arr[] = { 1, 2, 2, 3, 4, 4, 4, 5, 5,6 };
    int n = sizeof(arr) / sizeof(arr[0]);

    n = removeDuplicates(arr, n);

    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";

    return 0;
}

class Main {
    static int removeDuplicates(int arr[], int n)
    {
        if (n == 0 || n == 1)
            return n;

        int[] temp = new int[n];

        int j = 0;
        for (int i = 0; i < n - 1; i++)
            if (arr[i] != arr[i + 1])
                temp[j++] = arr[i];

        temp[j++] = arr[n - 1];

        for (int i = 0; i < j; i++)
            arr[i] = temp[i];

        return j;
    }

    public static void main(String[] args)
    {
        int arr[] = { 1, 2, 2, 3, 4, 4, 4, 5, 5, 6, 7 };
        int n = arr.length;

        n = removeDuplicates(arr, n);

        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
    }
}

def removeDuplicates(arr, n):

    if n == 0 or n == 1:
        return n

    temp = list(range(n))

    j = 0;
    for i in range(0, n-1):

        if arr[i] != arr[i+1]:
            temp[j] = arr[i]
            j += 1

    temp[j] = arr[n-1]
    j += 1
    
    for i in range(0, j):
        arr[i] = temp[i]

    return j

arr = [1, 2, 2, 3, 4, 4, 4, 5, 5, 6, 6, 7]
n = len(arr)

n = removeDuplicates(arr, n)

for i in range(n):
    print ("%d"%(arr[i]), end = " ")

Time Complexity
The given code has an O(N) time complexity, where N is the array’s size. Additionally, because we are building an auxiliary array that is the same size as the original array, the space complexity of the solution is O(N).

Method 2: Optimal approach using index pointer

The same methodology as the method above is used in this method. But the main distinction is that we’ll do in-place swaps rather than using the auxiliary array. Create the count variable in this case to contain the number of unique entries. The location of where to insert the next element in the same array will also be maintained with the aid of this count variable.

Algorithm

  • Create a counter variable to point to the index of unique elements.
  • Compare the element with its neighbour element
  • If elements do not match
    • Consider the first element as unique and consider its pointer in the counter variable
    • Keep comparing the other element with its neighbour element
  • As a result, the final array will consider only the unique element in the array
#include<iostream>
using namespace std;


int removeDuplicates(int arr[], int n)
{
    if (n==0 || n==1)
        return n;

    int j = 0;

    for (int i=0; i < n-1; i++)
        if (arr[i] != arr[i+1])
            arr[j++] = arr[i];

    arr[j++] = arr[n-1];

    return j;
}

int main()
{
    int arr[] = {1, 2, 2, 3, 4, 4, 4, 5, 5, 8};
    int n = sizeof(arr) / sizeof(arr[0]);

    
    n = removeDuplicates(arr, n);

    for (int i=0; i<n; i++)
        cout << arr[i] << " ";

    return 0;
}
class Main
{
    static int removeDuplicates(int arr[], int n)
    {
        if (n == 0 || n == 1)
            return n;
    
        int j = 0;
    
        for (int i = 0; i < n-1; i++)
            if (arr[i] != arr[i+1])
                arr[j++] = arr[i];
    
        arr[j++] = arr[n-1];
    
        return j;
    }
    
    public static void main (String[] args)
    {
        int arr[] = {1, 2, 2, 3, 4, 4, 4, 5, 5, 9, 9};
        int n = arr.length;
        
        n = removeDuplicates(arr, n);

        for (int i=0; i<n; i++)
        System.out.print(arr[i]+" ");
    }
}

Time Complexity
The preceding approach has an O(N) time complexity, where N is the array’s element count. The reason is that in order to compare the items and identify the unique elements, we traverse the complete array only once. Additionally, because we do not need any additional space to eliminate duplicates from the sorted array, the space complexity of the preceding approach is O(1).

Method 3: Two-pointer

Here, a sorted array may be used to our benefit. Two points, I and j, can be used. Up to the point where nums[i] == nums[j], we keep increasing j.

Algorithm:

  • return if nums size <= 1
  • set i = 0
  • Loop for j = 1; j < nums.size(); j++
    • if nums[j] != nums[i]
    • i++
    • nums[i] = nums[j]
  • return i + 1

Lets dry-run our algorithm to see how the solution works.

nums = [0,0,1,1,1,2,2,3,3,4]

Step 1: length = nums.size()
        = 10

Step 2: length <= 1
        10 <= 1
        false

Step 3: i = 0

Step 4: Loop for j = 1; 1 < 10
        nums[i] != nums[j]
        nums[0] != nums[1]
        0 != 0
        false
        j++
        j = 2

Step 5: Loop for j = 2; 2 < 10
        nums[i] != nums[j]
        nums[0] != nums[2]
        0 != 1
        true
        i++
        i = 1
        nums[i] = nums[j]
        nums[1] = nums[2]
        nums[1] = 1
        j++
        j = 3

Step 6: Loop for j = 3; 3 < 10
        nums[i] != nums[j]
        nums[1] != nums[3]
        1 != 1
        false
        j++
        j = 4

Step 7: Loop for j = 4; 4 < 10
        nums[i] != nums[j]
        nums[1] != nums[4]
        1 != 1
        false
        j++
        j = 5

Step 8: Loop for j = 5; 5 < 10
        nums[i] != nums[j]
        nums[1] != nums[5]
        1 != 2
        true
        i++
        i = 2
        nums[i] = nums[j]
        nums[2] = nums[5]
        nums[2] = 2
        j++
        j = 6

Step 9: Loop for j = 6; 6 < 10
        nums[i] != nums[j]
        nums[2] != nums[6]
        2 != 2
        false
        j++
        j = 7

Step 10: Loop for j = 7; 7 < 10
         nums[i] != nums[j]
         nums[2] != nums[7]
         2 != 3
         true
         i++
         i = 3
         nums[i] = nums[j]
         nums[3] = nums[7]
         nums[3] = 3
         j++
         j = 8

Step 11: Loop for j = 8; 8 < 10
         nums[i] != nums[j]
         nums[3] != nums[8]
         3 != 3
         false
         j++
         j = 9

Step 12: Loop for j = 9; 9 < 10
         nums[i] != nums[j]
         nums[3] != nums[9]
         3 != 4
         true
         i++
         i = 4
         nums[i] = nums[j]
         nums[4] = nums[9]
         nums[4] = 4
         j++
         j = 10

Step 13: Loop for j = 10; 10 < 10
         false

Step 14: return i + 1
         return 4 + 1 = 5
#include<iostream>
using namespace std;

 int removeDuplicates(int nums[], int n) {
        if(n <= 1){
            return n;
        }

        int i = 0;

        for(int j = 1; j < n; j++){
            if(nums[j] != nums[i]){
                i++;
                nums[i] = nums[j];
            }
        }

        return i + 1;
    }
    
int main()
{
    int arr[] = {1, 2, 2, 3, 4, 4, 4, 5, 5, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
 
 
    n = removeDuplicates(arr, n);
 
    for (int i=0; i<n; i++)
        cout << arr[i] << " ";
 
    return 0;
}

The above method's time complexity is O(N) and its space complexity is O(1).

Conclusion
So with this we came to the end of this article. We have discussed three methods to remove duplicates from sorted array. We hope you will understand the concept clearly.

Leave a Reply

Your email address will not be published. Required fields are marked *