Remove Duplicates From Sorted Array In C – Using Two Pointers

Remove Duplicates From Sorted Array In c is a tutorial aimed at showing you how to use two pointers to solve the interview question below.

Problem Statement

Given a sorted array arr remove the duplicates in-place such that each element appears only once and returns the new length.

Implement the function removeDuplicates(int arr[], int n) which takes two arguments

arr[] – Sorted array
numsSize – Size of the array

Your task is to remove the duplicates elements from the given sorted array and return the new length. It does not matter what values are set beyond the returned length.

Note: Do not allocate extra space for another array, you should write an in-place algorithm to implement this task.

Example input 1

arr[] = {0,0,0,0,1,1,12,400}

output: 4. That is because after removing duplicates from the array you are supposed to be left with arr[0,1,12,400]

Hint

• First check to make sure that array arr is not empty or has only 1 element; if so just return Size of the array numsSize passed in to removeDuplicates as the second argument
• Initialize variable int i to 0 for traversing the array elements and int len to 0 for calculating new array length which we are required to return
• Compare adjacent elements of the array arr[i] and arr[i + 1], if the value of arr[i] is equal to the value of arr[i + 1], move to the next index i (in other words just continue with the loop) otherwise place value of arr[i] in arr[len] and increment len
• After the loop is completed, place the last element of the array in arr[len] and increment len

The Solution

The code is written in c but you can use same algorithm to write it in whatever language you choose to.

#include <stdio.h>

int removeDuplicates(int* nums, int numsSize){
    if(numsSize == 0 || numsSize == 1)
        return numsSize;
        
    int i=0;
    int len = 0;
    
    for(i=0; i<numsSize-1; i++)
        if(nums[i] != nums[i+1])
            nums[len++] = nums[i];
            
    nums[len++] = nums[numsSize - 1];
    
    return len;
}

int main()
{
    int ary[8] = {0,0,0,0,1,1,12,400};
    int i;
    int sz = sizeof(ary)/sizeof(ary[0]);

    int new_arry_length = removeDuplicates(ary, sz);     
    printf("New lenght is: %d", new_arry_length);
    
    return 0;
}

More Clarification

For our given input, if you go ahead to print the elements of the array arr after execution returns to main function, what you find is that our input array now looks like this arr[] = {0,1,12,400,1,1,12,400}

instead of arr[] = {0,1,12,400} which matches the returned new length 4. The reason is that we are told that It does not matter what values are set beyond the returned length from our problem statement.

For a more detailed output in leetcode though with a different input, see attached image below:

Time and Space Complexity Analysis

• Time complexity is O(n); i.e the algorithm runs in linear time
• Space complexity is O(1)

Conclusion

The two pointer technique algorithm used to remove duplicates from sorted array in C programming is accepted by leetcode; please see status in attached image, and notice that the algorithm runs at 20ms for the given input and is faster than 82.83% of other codes submitted in c for this particular problem statement and the memory usage is 8.4MB which is 79.37% less than the memory other codes submitted for this problem used.