Blog Details

Remove Duplicated from Sorted Array

1. Problem

Given a sorted array nums, 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 by modifying the input array in-place with O(1) extra memory.

2. Examples

Given 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 returned length.
Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

It doesn't matter what values are set beyond the returned length.

3. Solution

Two possible solutions, I think I can solve this problem.

#1. Use Java built-in HashSet, loop the array to the Set. The duplicated elements will be removed. The set.size() will be final length of the result. But we can use extra space.

#2. Since the array is in the ascending order, we can run the overriding the already looped elements by the rest elements. Use one integer to control the new index in the array, add if condition to check if the element is not duplicated, add it to the array.

class Solution{
    public int removeDuplicated(int[] nums) {
        int curIndex = 0;
        for(int i = 1; i < nums.length; i++) {
            if(nums[i] != nums[curIndex]) {
                nums[++curIndex] = nums[i];
            } 
        }
        return curIndex + 1; // add element in index = 0;
    }
}