Remove Duplicates From Sorted Array II

Share

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

Custom Judge:

The judge will test your solution with the following code:

Java
int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length

int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

If all assertions pass, then your solution will be accepted.

Example 1
Input: nums = [1,1,1,2,2,3]
Output: 5, nums = [1,1,2,2,3,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).
Example 2
Input: nums = [0,0,1,1,1,1,2,3,3]
Output: 7, nums = [0,0,1,1,2,3,3,_,_]
Explanation: Your function should return k = 7, with the first seven elements of nums being 0, 0, 1, 1, 2, 3 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).
Constraints:

Contents

Solution 1 - Move distinct elements to the front of array

In this approach, we are going to apply similar solution as Remove Duplicates From Sorted Array. We will move the distinct elements to the front of the array and ignore remaining, but we keep a count of how many duplicates have seen, if the duplicates are at most two, only then move them to beginning of array.

Implementation steps:
  • We will create three variables dupIndex to track the index of nums array where to move distinct elements to, prevElement to track current indexed element to check whether next coming elements are duplicates or not, and count to keep track how many times the element is repeated.
  • We will initialize dupIndex =1 , since element at 0th index will not have any elements before that, prevElement = nums[0], and count = 1, since we have taken the first element.
  • Then, we will loop through elements of nums array from 1st index and check:
    • If nums[i] is not same as prevElement, that means they are not duplicates, so move element at index i to dupIndex and increment dupIndex, and update the prevElement with current value, also reset count = 1.
    • If nums[i] is same as prevElement, and the count is below 2, then move element at index i to dupIndex and increment dupIndex, and increment count.
  • Finally, return dupIndex, it will be at the position where all distinct elements are moved to its left side.
Java
import java.util.Arrays;

public class RemoveDuplicatesFromSortedArrayII {

    static int removeDuplicates(int[] nums) {
        if (nums.length <= 2) {
            return nums.length;
        }
        int dupIndex = 1;
        int prevElement = nums[0];
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == prevElement && count<2) {
                nums[dupIndex++] = nums[i];
                count++;
            } else if (nums[i] != prevElement) {
                prevElement = nums[i];
                nums[dupIndex++] = nums[i];
                count =1;
            }
        }
        return dupIndex;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 1, 2};
        System.out.println(removeDuplicates(nums));
        System.out.println("Nums after : " + Arrays.toString(nums));
        nums = new int[]{0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
        System.out.println(removeDuplicates(nums));
        System.out.println("Nums after : " + Arrays.toString(nums));
        nums = new int[]{1,1,1,2,2,3};
        System.out.println(removeDuplicates(nums));
        System.out.println("Nums after : " + Arrays.toString(nums));

    }
}
Simplified version of above program:

Here is the simplified version of above program, for illustration purpose we have used prevElement and count, we can write the same logic, just by comparing current element with dupIndex -2 indexed element, if they are not same, only then move the current element to dupIndex and increment dupIndex.

Java
import java.util.Arrays;

public class RemoveDuplicatesFromSortedArrayII {

    static int removeDuplicates_Simplified(int[] nums) {
        if (nums.length <= 2) {
            return nums.length;
        }
        int dupIndex = 2;
        for (int i = 2; i < nums.length; i++) {
            if (nums[i] != nums[dupIndex -2]) {
                nums[dupIndex++] = nums[i];
            }
        }
        return dupIndex;
    }

    public static void main(String[] args) {

        System.out.println("########### Remove duplicates logic simplified ############");
        int[] nums = new int[]{0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
        System.out.println(removeDuplicates_Simplified(nums));
        System.out.println("Nums after : " + Arrays.toString(nums));
        nums = new int[]{1,1,1,2,2,3};
        System.out.println(removeDuplicates_Simplified(nums));
        System.out.println("Nums after : " + Arrays.toString(nums));

    }
}
Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the input array nums length.
Space complexity: O(1).

Above implementations source code can be found at GitHub link for Java code