How to remove duplicate elements from a sorted array

Question

Given a sorted array A of size N, delete all the duplicates elements from A. Note: Don't use set or HashMap to solve the problem. example:

Input:

N = 5
Array = {2, 2, 2, 2, 2}

Output: 2

Explanation: After removing all the duplicates only one instance of 2 will remain.

I have tried the below code. Please tell me what's wrong with the code?

int remove_duplicate(int arr[],int N){
        // code here
        int index=0;
        for(int i=1;i<N;i++){
            if(arr[i]!=arr[i-1]){
                arr[index]=arr[i-1];
                index++;
            }
        }
        return index+1;
    }

Why not use java stream api? `Arrays.stream(arr).distinct().toArray();` will return an int array with distinct values. — Fussel, Jul 24 '21 at 10:32
You could put the `Array` into a `Set` that should remove duplicates, so long as you have appropriate `hashcode` and `equals` definitions. Personally I would probably use a `Set` as my container knowing I need to remove duplicates. — Gavin, Jul 24 '21 at 12:55

score 3 · Answer 1 · answered Jul 24 '21 at 10:44

You could replace some duplicate elements and set the length at the end.

This approach mutates the array.

const
    remove_duplicate = array => {
        let j = 0;
        for (let i = 0; i < array.length; i++) {
            if (array[j - 1] !== array[i]) array[j++] = array[i];
        }
        array.length = j;
        return array;
    };
    
console.log(...remove_duplicate([2, 2, 2]));    
console.log(...remove_duplicate([1, 1, 2, 2, 3, 4, 5, 5]));

Itay · Answer 2 · 2021-07-24T13:43:51.147

Overkill using binary tree

BinaryTree binaryTree = new BinaryTree();
for (int i = 0; i < n; i++){
            //add or insert function need to check that the key isn't in the stracture
            binaryTree.Add(arr[i]); 
        }

binaryTree.TraverseInOrder(binaryTree.Root);

You need to implement some of the classes. Check this example:

c-binary-search-tree-implementation

For more on Inorder output for binaryTree: binary-tree-from-inorder-traversal

score 1 · Answer 3 · answered Jul 24 '21 at 10:43

Look here: https://www.geeksforgeeks.org/duplicates-array-using-o1-extra-space-set-2/

// Java program to print all elements that
// appear more than once.
import java.util.*;
class GFG {
 
    // function to find repeating elements
    static void printRepeating(int arr[], int n)
    {
        // First check all the values that are
        // present in an array then go to that
        // values as indexes and increment by
        // the size of array
        for (int i = 0; i < n; i++)
        {
            int index = arr[i] % n;
            arr[index] += n;
        }
 
        // Now check which value exists more
        // than once by dividing with the size
        // of array
        for (int i = 0; i < n; i++)
        {
            if ((arr[i] / n) >= 2)
                System.out.println(i + " ");
        }
    }
 
    // Driver code
    public static void main(String args[])
    {
        int arr[] = { 1, 6, 3, 1, 3, 6, 6 };
        int arr_size = arr.length;
 
        System.out.println("The repeating elements are: ");
 
        // Function call
        printRepeating(arr, arr_size);
    }
}

score 1 · Answer 4 · answered Jul 24 '21 at 10:44

Try this:

 int remove_duplicate(int arr[],int N){
            
     int index=0;
     for(int i=1;i<N;i++){
         if(arr[i]!=arr[index]){ //change index
            index++; //swapt next line
            arr[index]=arr[i]; 
          }
      }
            return index+1;
 }

score 1 · Answer 5 · answered Jul 24 '21 at 11:16

you can check my answer here - and it works perfectly https://stackoverflow.com/a/32931932/3052125

Here is the main logic to remove the duplicates - arr is the sorted array provided to you with duplicate elements -

    // Logic for removing the duplicate elements
    int compare = 0;
    arr[compare] = arr[0];

    for (int i = 1; i < size; i++) {
        if (arr[compare] != arr[i]) {
            compare++;
            arr[compare] = arr[i];
        }
    }

WJS · Answer 6 · 2021-07-24T16:48:08.343

Given a sorted array A of size N, delete all the duplicates elements from A

Well, that implies returning an array with duplicates deleted.

int[] v = { 1, 1, 1, 2, 2, 2, 2,3 };
v = remove_duplicates(v);
System.out.println(Arrays.toString(v));

prints

[1, 2, 3]

The method. This works by copying the unique values toward the front of the passed array. So this does alter that array.


public static int[] remove_duplicates(int[] v) {
    int current = 0;    
    for (int i = 0; i < v.length; i++) {
        if (v[i] != v[current]) {
            v[++current] = v[i];
        }
    }
    // Now return the front portion of the array that contains the distinct
    // values.  You could also just create a new array and copy the elements 
    // using a loop.
    return Arrays.copyOf(v, current+1);
}

How to remove duplicate elements from a sorted array

6 Answers6