Arrays - Remove Duplicates From Sorted Array

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:

Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.
Return k.

Custom Judge:

The judge will test your solution with the following code:

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.

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).

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:

1 <= nums.length <= 3 * 10⁴
-100 <= nums[i] <= 100
nums is sorted in non-decreasing order.

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 0^th index will not have any elements before that, and prevElement = nums[0].
Then, we will loop through elements of nums array from 1^st 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 1^st index = 1, is same as prevElement, so we continue to next element.
Element at 2^nd 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:
- Now, increment dupIndex to 2.
Element at 3^rd 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:
- 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.

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

Custom Judge:

Constraints:

Contents

Implementation steps:

Example: consider below input nums = [1,1,2,3]

Complexity Analysis: