Remove Duplicates from Sorted Array In CPP, C, JAVA,PYTHON,C#,JS

With a sorted array arr[] of size n, the aim is to reorganize the array so that every unique element shows at the beginning in sorted sequence. Return also the length of this unique sorted subarray.

Note: Since they have no effect on the outcome, the items following the unique ones can be in any sequence and have any value.

Example

Input: arr[] = [2, 2, 2, 2, 2]
Output: [2]
Explanation: All the elements are 2, So only keep one instance of 2.


Input: arr[] = [1, 2, 2, 3, 4, 4, 4, 5, 5]
Output: [1, 2, 3, 4, 5]

Input: arr[] = [1, 2, 3]
Output: [1, 2, 3]
Explanation : No change as all elements are distinct.

Using Hash Set – Works for Unsorted Also – O(n) Time and O(n) Space

• Save already handled elements in a hash set or dictionary.
• Starting the index of result array as 0.
• Review the input array. Put an element at the result index and then add it to the hash set if it isn’t there already.

C++

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

int removeDuplicates(vector<int>& arr) {
  
    // To track seen elements
    unordered_set<int> s; 
  
    // To maintain the new size of the array
    int idx = 0;  

    for (int i = 0; i < arr.size(); i++) {
        if (s.find(arr[i]) == s.end()) { 
            s.insert(arr[i]);  
            arr[idx++] = arr[i];  
        }
    }
 
    // Return the size of the array 
    // with unique elements
    return s.size(); 
}

int main() {
    vector<int> arr = {1, 2, 2, 3, 4, 4, 4, 5, 5};
    int newSize = removeDuplicates(arr);
    for (int i = 0; i < newSize; i++) 
        cout << arr[i] << " ";
    return 0;
}

Java

import java.util.HashSet;

class GfG {

    static int removeDuplicates(int[] arr) {
        
        // To track seen elements
        HashSet<Integer> s = new HashSet<>();
        
        // To maintain the new size of the array
        int idx = 0;  

        for (int i = 0; i < arr.length; i++) {
            if (!s.contains(arr[i])) { 
                s.add(arr[i]);  
                arr[idx++] = arr[i];  
            }
        }

        // Return the size of the array 
        // with unique elements
        return idx;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 2, 3, 4, 4, 4, 5, 5};
        int newSize = removeDuplicates(arr);

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

Python

def removeDuplicates(arr):
    
    # To track seen elements
    seen = set()
    
    # To maintain the new size of the array
    idx = 0

    for i in range(len(arr)):
        if arr[i] not in seen:
            seen.add(arr[i])
            arr[idx] = arr[i]
            idx += 1

    # Return the size of the array 
    # with unique elements
    return idx

if __name__ == "__main__":
    arr = [1, 2, 2, 3, 4, 4, 4, 5, 5]
    newSize = removeDuplicates(arr)

    for i in range(newSize):
        print(arr[i], end=" ")

C#

using System;
using System.Collections.Generic;

class GfG {
    static int removeDuplicates(int[] arr) {
        
        // To track seen elements
        HashSet<int> s = new HashSet<int>();
        
        // To maintain the new size of the array
        int idx = 0;

        for (int i = 0; i < arr.Length; i++) {
            if (!s.Contains(arr[i])) { 
                s.Add(arr[i]);
                arr[idx++] = arr[i];
            }
        }

        // Return the size of the array 
        // with unique elements
        return idx;
    }

    static void Main() {
        int[] arr = {1, 2, 2, 3, 4, 4, 4, 5, 5};
        int newSize = removeDuplicates(arr);

        for (int i = 0; i < newSize; i++) {
            Console.Write(arr[i] + " ");
        }
    }
}

JavaScript

function removeDuplicates(arr) {
    
    // To track seen elements
    const s = new Set();
    
    // To maintain the new size of the array
    let idx = 0;

    for (let i = 0; i < arr.length; i++) {
        if (!s.has(arr[i])) {
            s.add(arr[i]);
            arr[idx++] = arr[i];
        }
    }

    // Return the size of the array 
    // with unique elements
    return idx;
}

// Driver code
const arr = [1, 2, 2, 3, 4, 4, 4, 5, 5];
const newSize = removeDuplicates(arr);

console.log(arr.slice(0, newSize).join(' '));

Output

12345

Anticipated Method – O(n) Time and O(1) Space

The array is sorted hence we do not have to have a hash set. Every incident of an element would be consecutive. We so mostly have to find whether the current element is exactly the same as the previous one or not.

Step by step application:

• Start with idx = 1 (idx is going to contain the index of the next different item). We start idx with 1 since, except from the first item, nothing exists before it.
• Go over the array looping from i = 0 to n-1.
• Assign arr[idx] = arr[i] and increase idx at every index i should arr[i] deviate from arr[i-1].
• Ar[] has the distinct elements in the first idx places following the loop.

C++

#include <iostream>
#include <vector>
using namespace std;

int removeDuplicates(vector<int>& arr) {
    int n = arr.size();
    if (n <= 1)
        return n;

      // Start from the second element
    int idx = 1; 
  
    for (int i = 1; i < n; i++) {
        if (arr[i] != arr[i - 1]) {
            arr[idx++] = arr[i];
        }
    }
    return idx;
}

int main() {
    vector<int> arr = {1, 2, 2, 3, 4, 4, 4, 5, 5};
    int newSize = removeDuplicates(arr);
    for (int i = 0; i < newSize; i++) 
        cout << arr[i] << " ";
    return 0;
}

C

#include <stdio.h>

int removeDuplicates(int arr[], int n) {
    if (n <= 1)
        return n;
    
      // Start from the second element
    int idx = 1;
  
    for (int i = 1; i < n; i++) {
        if (arr[i] != arr[i - 1]) {
            arr[idx++] = arr[i];
        }
    }
    return idx;
}

int main() {
    int arr[] = {1, 2, 2, 3, 4, 4, 4, 5, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int newSize = removeDuplicates(arr, n);
    
    for (int i = 0; i < newSize; i++) 
        printf("%d ", arr[i]);

    return 0;
}

JAVA

class GfG {

    static int removeDuplicates(int[] arr) {
        int n = arr.length;
        if (n <= 1)
            return n;
        
          // Start from the second element
        int idx = 1; 
      
        for (int i = 1; i < n; i++) {
            if (arr[i] != arr[i - 1]) {
                arr[idx++] = arr[i];
            }
        }
        return idx;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 2, 3, 4, 4, 4, 5, 5};
        int newSize = removeDuplicates(arr);

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

Python

def removeDuplicates(arr):
    n = len(arr)
    if n <= 1:
        return n

    # Start from the second element
    idx = 1  
    
    for i in range(1, n):
        if arr[i] != arr[i - 1]:
            arr[idx] = arr[i]
            idx += 1

    return idx

if __name__ == "__main__":
    arr = [1, 2, 2, 3, 4, 4, 4, 5, 5]
    newSize = removeDuplicates(arr)

    for i in range(newSize):
        print(arr[i], end=" ")

C#

using System;

class GfG {
    static int removeDuplicates(int[] arr) {
        int n = arr.Length;
        if (n <= 1)
            return n;
        
          // Start from the second element
        int idx = 1; 
        for (int i = 1; i < n; i++) {
            if (arr[i] != arr[i - 1]) {
                arr[idx++] = arr[i];
            }
        }
        return idx;
    }

    static void Main() {
        int[] arr = {1, 2, 2, 3, 4, 4, 4, 5, 5};
        int newSize = removeDuplicates(arr);

        for (int i = 0; i < newSize; i++) {
            Console.Write(arr[i] + " ");
        }
    }
}

JavaScript

function removeDuplicates(arr) {
    const n = arr.length;
    if (n <= 1)
        return n;
    
    // Start from the second element
    let idx = 1; 
    for (let i = 1; i < n; i++) {
        if (arr[i] !== arr[i - 1]) {
            arr[idx++] = arr[i];
        }
    }

    return idx;
}

// Driver code
const arr = [1, 2, 2, 3, 4, 4, 4, 5, 5];
const newSize = removeDuplicates(arr);

console.log(arr.slice(0, newSize).join(' '));

Output

12345