Remove duplicates from Sorted Array

The objective is to rearrange a sorted array arr[] of size n so that every unique element appears at the beginning in sorted order. Return the length of this unique sorted subarray as well.

Note: Since they have no bearing on the outcome, the items that follow the distinct ones can be in any sequence and have any value.

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.

Table of Content

• Using Hash Set – Works for Unsorted Also – O(n) Time and O(n) Space
• Expected Approach – O(n) Time and O(1) Space

Hash Set Utilization: Effective for Unsorted Additionally, O(n) Space and O(n) Time

• Store previously processed elements in a dictionary or hash set.
• Set the result array’s index to zero upon initialization.
• Go through the array of inputs. Put an element at the result index and add it to the hash set if it isn’t already there.

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

1 2 3 4 5