2

I was asked to write a method that accepts a sorted array, removes any duplicate elements found in the array and then places a 0 at the end of the array for every duplicate element found.

It is also supposed to return the number of unique elements found in the array.

Here is my method:

public static int removeDups(int[] arr) {
    int j = 0;
    int i = 1;
    int numDups = 0;

    while(i < arr.length) {
        if (arr[i] == arr[j]) {
            i++;     
            numDups++;       
        } 
        else {
            arr[++j] = arr[i++];
        }   
    }

    for (int k = j+1; k < arr.length; k++) {
        arr[k] = 0;     
    }

    return (j); 
}

It successfully finds all the duplicate numbers in the array and places the correct number of 0s at the end, but it doesn't always return the correct value for the number of unique elements.

For example, for the array:

{ 6 10 19 21 23 26 27 36 38 45 }

the number of unique elements should be 10, but it returns 9.

What am I doing wrong?

16
  • @TimBiegeleisen I can't use that method since I'm not allowed to use nested loops and any element in the array can be moved at most once. Oct 5, 2015 at 3:12
  • Can't you just return j + 1? That's what your doing when you set k = j + 1 to add the zeroes. Oct 5, 2015 at 3:22
  • You are using j to keep the index of last unique number. So the count of unique numbers is j + 1. Just return j + 1 at the end. Oct 5, 2015 at 3:23
  • @JonnyHenly If I return (j+1), the value returned is still wrong and not equal to the number of unique elements. Oct 5, 2015 at 3:24
  • You said it returns 9 but should return 10, 9 + 1 ='s 10. That's just for the example array you provided us with, what does an array with duplicates look like before and after? Oct 5, 2015 at 3:26

4 Answers 4

1

As it can be seen, j is used as the index of the last unique element.

In an array, i'th index is actually the i + 1'th element counted from 1.

So, you have to return j + 1 instead of j from your method.

1

Here is a solution to your problem. It keeps track of two pointers, one which only advances when a value gets written to the array, and the other which touches every element of the array in sequential order. When one or more duplicates are encountered, the second pointer keeps advancing, while the first pointer stays put, waiting to write a non-duplicate value. Finally, the code iterates over the remainder of the array from the first pointer, writing out zeroes until the end.

public static int removeDups(int[] arr) {
    if (arr == null) {
        return null;
    }

    if (arr.length == 0 || arr.length == 1) {
        return arr;
    }

    int prevIndex = 0;

    for (int i=1; i < arr.length; ++i) {
        if (arr[prevIndex] != arr[i]) {
            arr[prevIndex+1] = arr[i];
            ++prevIndex;
        }
    }

    for (int i=prevIndex+1; i < arr.length; ++i) {
        arr[i] = 0;
    }

    return prevIndex+1;
}

int[] arr = {1, 2, 3, 3, 4, 5, 6, 6, 6, 10};
removeDups(arr);
System.out.println(Arrays.toString(arr));

Output:

[1, 2, 3, 4, 5, 6, 10, 0, 0, 0]

This code has been tested using IntelliJ and it appears to be working.

8
  • @RockAndaHardPlace Please review this answer, thanks. Oct 5, 2015 at 4:11
  • This does work to remove the duplicates and place the 0s, but it doesn't return the number of unique elements. Oct 5, 2015 at 4:13
  • Theoretically, this should work, just like @Lahiru's answer should work, but for me it is still returning the wrong value. Though this is probably because of an unrelated problem. Thanks anyway! Oct 5, 2015 at 4:19
  • Your code has a number of problems. Do you want me to start with your code instead and attempt an answer? Oct 5, 2015 at 4:23
  • Sure, if you'd like to, @Tim! Oct 5, 2015 at 4:34
0

Try this!

static int getUniqueElements(int [] sortedArr){

        int duplicateCount = 0;
        int [] tempArr = sortedArr;
        int j=0;
        boolean isNewValue = true;
        for(int i=1;i<tempArr.length;i++){
            if(sortedArr[j] != tempArr[i]){
                isNewValue = true;
                sortedArr[++j] = tempArr[i];
            }else{
                if(isNewValue){
                    isNewValue = false;
                    duplicateCount++;
                }
            }
        }

        for(j++;j<sortedArr.length;j++){
            sortedArr[j] = 0;
            duplicateCount++;
        }

        return (sortedArr.length-duplicateCount);

    }
    public static void main(String[] args) {
        int[] arr = {1, 3, 3, 3, 3, 6, 6, 7, 8, 8};
        System.out.println("Unique Count:"+ getUniqueElements(arr));
        System.out.println(Arrays.toString(arr));
    }

OutPut:

Unique Count:2
[1, 3, 6, 7, 8, 0, 0, 0, 0, 0]

Since in the given array 1,7 are unique.

Note: tried with your example array {6, 10, 19, 21, 23 ,26 ,27 ,36 ,38, 45 } also

0
0

My solution is as(assuming elements can repeat only twice):

public static int removeDups(int[] arr) {       
    int i = 0;
    int numDups = 0;
    while (i < arr.length - 1 - numDups) {          
        if (arr[i] == arr[i + 1]) {
            numDups++;
            for (int m = i + 1; m < arr.length - numDups; m++) {
                arr[m] = arr[m + 1];
            }
            arr[arr.length - numDups] = 0;
        }           
        i++;
    }
    return arr.length-numDups;
}

Not the answer you're looking for? Browse other questions tagged or ask your own question.