Remove Duplicates from Sorted Array with HashSet

Question

I have a problem about this:

The Object shows that Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this in place with constant memory.For example, Given input array nums = [1,1,2], Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn’t matter what you leave beyond the new length.

I use HashSet to do this question but the result always showed [1,1]. I could not figure it out could someone help me to know where is the problem?

My code:

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        Set<Integer> numset = new HashSet<>();
        for(int i:nums){
            numset.add(i);
        }
        return numset.size();
    }
}

Your input [1,1,2] Your answer [1,1] Expected answer [1,2]

Answer 1

Say you have a sorted array:

int[] nums = { 1, 2, 2, 2, 4, 5, 5, 5, 7, 7, 8 };

... walk through nums, at some read position check for being a duplicate,
... (otherwise) write it compact at the write position
... return new length

Overwrite nums.

As I do not want to spoil any satisfaction on coding, go ahead...

Tactics: work a problem out on paper.

Answer 2

• Your solution is not an in-place solution
• Since you are using a Hash Set you are violating the constant memory rule.
• In java we can not shrink the array size once it is initialized.

Therefore here is a simple in-place solution for your problem which has the worst case time complexity of O(n).

public int removeDuplicates(int[] nums){

    int length = nums.length;
    int index = 0;

    for(int i = 0; i < length - 1; i++){
        if(nums[i] == nums[i+1]){
            nums[index++] = nums[i];
        }
    }
    // this is needed because upper for loop runs until i equals to length-2
    // in order to avoid ArrayOutOfBoundException 
    nums[index++] = nums[length-1];

    // for displaying the unique array
    /*
    for(int i = 0; i < index; i++){
        System.out.println(nums[i]);
    }
    */

    return index;
}

Answer 3

Usage of an extra data structure is also violation of the rules you have mentioned i.e. don't allocate extra space for it. Now, since your array is already sorted, the following code will work just fine.

int solution(int[] nums) {
    int size = nums.length;
    if (size == 0 || size == 1) {
        return size;
    }
    int next = 0;

    for (int i = 0; i < size - 1; i++) {
        if (nums[i] != nums[i + 1]) {
            nums[next++] = nums[i];
        }
    }
    nums[next++] = nums[size - 1];

    return next;
}

In the above code we are just maintaining an extra index (next) to keep track of unique elements only and just moving them to the front by overwriting non-unique ones.

Answer 4

• At first, be aware that you cannot shrink Java's classic array in a method after allocated to. Since Java is pass-by-value.
• If you still insist on removing duplicates in-place, you need to put a delimiter like Integer.MAX_VALUE or Integer.MIN_VALUE. Then, until hit the value iterate over either get its size or do operation wherever you need.
• Yet, in-place removing seems not very adequate for this purpose, so I propose that to return new array.

Bizarre solution,

private static int removeDuplicatesWithDelimiter(int[] nums) {
    if (nums.length == 0) return 0;


    Set<Integer> numset = new HashSet<>();
    for(int i : nums){
        numset.add(i);
    }

    int newArraySize = numset.size();

    for (int i = 0; i < newArraySize; ++i) {
        nums[i] = (Integer) numset.toArray()[i];
    }

    nums[newArraySize] = Integer.MIN_VALUE;

    return newArraySize;
}

Better solution,

class ArrayDuplicateTest {

    private static int[] removeDuplicates(int[] list) {
        int newLength = list.length;
        // find length w/o duplicates:
        for (int i = 1; i < list.length; i++) {
            for (int j = 0; j < i; j++) {
                if (list[i] == list[j]) {   // if duplicate founded then decrease length by 1
                    newLength--;
                    break;
                }
            }
        }

        int[] newArray = new int[newLength]; // create new array with new length
        newArray[0] = list[0];  // 1st element goes to new array
        int inx = 1;            // index for 2nd element of new array
        boolean isDuplicate;

        for (int i = 1; i < list.length; i++) {
            isDuplicate = false;
            for (int j = 0; j < i; j++) {
                if (list[i] == list[j]) {  // if duplicate founded then change boolean variable and break
                    isDuplicate = true;
                    break;
                }
            }
            if (!isDuplicate) {     // if it's not duplicate then put it to new array
                newArray[inx] = list[i];
                inx++;
            }
        }
        return newArray;
    }

    public static void main(String[] args) {
        int nums[] = {1, 1, 2, 3, 5, 6,6 ,6};

        int noDup[] = removeDuplicates(nums);

        for (int i : noDup) {
            System.out.println(i + "    ");
        }

        System.out.println("length: " + noDup.length);
    }
}

Answer 5

Another "in-place" solution. As long as there is no requirements to keep duplicate values anywhere and there is no way in Java to shrink array without new array, duplicates replaced with MAX_VALUE and then sorted to the end of array. (see coments in code)

BTW: there is a variable declared during method execution uniqueCount

public int removeDuplicates(int[] nums) {

 if (nums.length == 0) return 0;

// at least one element is unique
int uniqueCount = 1;

for (int i = 0; i < nums.length - 1; i++) {
    if (nums[i] == nums[i + 1]) {
    // duplicate value replaced with Integer.MAX_VALUE to be at the end of array 
    nums[i] = Integer.MAX_VALUE;
    } else {
    // nums[i] is unique
    uniqueCount++;
    }
}
// Re-sort array to move MAX_VALUE elements to the end of array
Arrays.sort(nums);
return uniqueCount;

}