Remove Duplicates from Sorted Array

Description

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.

Consider the number of unique elements in nums to be k**​​​​​​​**​​​​​​​. After removing duplicates, return the number of unique elements k.

The first k elements of nums should contain the unique numbers in sorted order. The remaining elements beyond index k - 1 can be ignored.

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.

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:

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

Brute Force Approach (Using Auxiliary Space)

Intuition: Store all elements in an ordered set (or temporary list) to automatically filter out duplicates, then write the unique values back into the original array.

import java.util.*;
 
class Solution {
    public int removeDuplicates(int[] nums) {
        // TreeSet keeps elements unique and sorted
        Set<Integer> set = new TreeSet<>();
        for (int num : nums) {
            set.add(num);
        }
        
        // Copy unique elements back to nums
        int k = 0;
        for (int num : set) {
            nums[k++] = num;
        }
        
        return set.size();
    }
}
 

• Time Complexity: $O(N\log N)$ using TreeSet (or $O(N)$ using LinkedHashSet).
• Space Complexity: $O(N)$ extra memory for the set.

---

Most Optimized Approach (Two Pointers — In-Place)

Intuition (“Read & Write Pointers”):
Since the array is already sorted, duplicate elements are guaranteed to sit right next to each other.

• Write pointer (l): Tracks the index where the next unique element should be written (starts at index 1).
• Read pointer (r): Scans through the array starting from index 1, comparing each element with its predecessor (nums[r - 1]).

Whenever nums[r] differs from nums[r - 1], a new unique number has been found. Copy nums[r] into nums[l] and increment l using post-increment (nums[l++] = nums[r]).

public class Solution {
    public int removeDuplicates(int[] nums) {
        int l = 1;
        for (int r = 1; r < nums.length; r++) {
            if (nums[r] != nums[r - 1]) {
                nums[l++] = nums[r];
            }
        }
        return l;
    }
}
 

Step-by-Step Dry Run (nums = [0, 0, 1, 1, 2])

Step	r	nums[r]	nums[r - 1]	Action	Array State
Init	-	-	-	Set l = 1	[0, 0, 1, 1, 2]
1	1	0	0	Duplicate, skip	[0, 0, 1, 1, 2]
2	2	1	0	New value: nums[1] = 1, l++ (2)	[0, 1, 1, 1, 2]
3	3	1	1	Duplicate, skip	[0, 1, 1, 1, 2]
4	4	2	1	New value: nums[2] = 2, l++ (3)	[0, 1, 2, 1, 2]

Result: Return l = 3. The first 3 elements of nums are [0, 1, 2].

• Time Complexity: $O(N)$ — single pass through the array.
• Space Complexity: $O(1)$ — modifies the input array in-place using constant memory.