Remove Duplicates From Sorted Array

Share

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

Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:

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,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 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,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 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 will move the distinct elements to the front of the array and ignore remaining.

Implementation steps:
  • We will create two variables dupIndex to track the index of nums array where to move distinct elements to, and prevElement to track current indexed element to check whether next coming elements are duplicates or not.
  • We will initialize dupIndex =1 , since element at 0th index will not have any elements before that, and prevElement = nums[0].
  • 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. If the current element is same as prevElement then continue the loop.
  • Finally, return dupIndex, it will be at the position where all distinct elements are moved to its left side.
Example: consider below input nums = [1,1,2,3]
  • As a first step, we will initialize dupIndex = 1 and prevElement = nums[0] = 1.
  • Now, loop through nums array from index 1.
  • Element at 1st index = 1, is same as prevElement, so we continue to next element.
  • Element at 2nd index = 2, is not same as prevElement (2 ≠ 1):
    • So, we update prevElement with current value, prevElement = 2
    • Move current indexed element to dupIndex, so the resultant array looks like below: Example
    • Now, increment dupIndex to 2.
  • Element at 3rd index = 3, is not same as prevElement (3 ≠ 2):
    • So, we update prevElement with current value, prevElement = 3
    • Move current indexed element to dupIndex, so the resultant array looks like below: Example
    • Now, increment dupIndex to 3.
  • At the end, we will simply return the dupIndex, this represents the the index where it left off, and that is also the length of distinct elements size.
Java
public class RemoveDuplicatesFromSortedArray {

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

    public static void main(String[] args) {
        System.out.println(removeDuplicates(new int[]{1, 1, 2}));
        System.out.println(removeDuplicates(new int[]{0,0,1,1,1,2,2,3,3,4}));

    }
}
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