Remove Duplicates from Sorted Array (In-Place)
Given an integer array sorted in non-decreasing order, remove the duplicates in-place so that each unique element appears only once. The relative order of elements must be preserved.
-
Return the number of unique elements k.
-
The first k elements of the array should store the unique values.
-
Values beyond the first k positions don’t matter.
Example 1
Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Unique numbers are [1,2]. Return length 2.
Example 2
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: Unique numbers are [0,1,2,3,4].
Constraints
-
1 <= nums.length <= 3 * 10^4
-
-100 <= nums[i] <= 100
-
nums is sorted in non-decreasing order
Brute Force Idea
Since the array is sorted, all duplicates appear next to each other.
Steps:
-
Use a temporary data structure (like Set) to store only unique elements.
-
Iterate over the original array and add elements to the Set.
-
Copy the unique elements back to the original array.
-
Return the size of the Set as the number of unique elements.
import java.util.*;
class RemoveDuplicatesBruteForce {
public int removeDuplicates(int[] nums) {
// LinkedHashSet preserves insertion order
Set<Integer> set = new LinkedHashSet<>();
for (int num : nums) {
set.add(num);
}
int i = 0;
for (int val : set) {
nums[i++] = val;
}
return set.size(); // number of unique elements
}
public static void main(String[] args) {
RemoveDuplicatesBruteForce sol = new RemoveDuplicatesBruteForce();
int[] nums = {0,0,1,1,1,2,2,3,3,4};
int k = sol.removeDuplicates(nums);
System.out.println("Unique count: " + k);
for (int i = 0; i < k; i++) {
System.out.print(nums[i] + " ");
}
}
}
Unique count: 5
0 1 2 3 4
Complexity Analysis
- Time Complexity : O(n), Iterating + Set insertions
- Space Complexity : O(n), Extra storage for unique elements
Brute Force In-Place Idea
-
Iterate through the array starting from index 1.
-
If the current element is equal to the previous element (nums[i] == nums[i-1]), it is a duplicate.
-
Shift all elements to the left to overwrite the duplicate.
-
Reduce the size of the array (k--) and recheck the current index (i--).
-
Continue until the end of the array.
This method does not use extra memory, but it is very inefficient for large arrays because of repeated shifting.
class RemoveDuplicatesShift {
public int removeDuplicates(int[] nums) {
int n = nums.length;
int k = n; // current effective length of array
for (int i = 1; i < k; i++) {
if (nums[i] == nums[i - 1]) {
for (int j = i; j < k - 1; j++) {
nums[j] = nums[j + 1];
}
k--; // decrease effective size
i--; // recheck current index after shifting
}
}
return k;
}
public static void main(String[] args) {
RemoveDuplicatesShift sol = new RemoveDuplicatesShift();
int[] nums = {0,0,1,1,1,2,2,3,3,4};
int k = sol.removeDuplicates(nums);
System.out.println("Unique count: " + k);
for (int i = 0; i < k; i++) {
System.out.print(nums[i] + " ");
}
}
}
Unique count: 5
0 1 2 3 4
Complexity Analysis
- Time Complexity : O(n²), Nested loops for shifting duplicates
- Space Complexity :O(1), No extra space used
Two Pointer Technique
Removing duplicates from a sorted array is a common problem in coding interviews and algorithm practice. If the array is sorted, all duplicates appear consecutively. This allows us to solve the problem efficiently using the Two Pointer Technique in one pass, without using extra space.
-
Since the array is sorted, duplicates are always adjacent.
-
We can use two pointers to efficiently remove duplicates:
-
Pointer i (slow) -> Keeps track of the last unique element.
-
Pointer j (fast) -> Scans through the array.
Step-by-Step Algorithm
-
Initialize i = 0 :- the first element is always unique.
-
Iterate j from 1 to the end of the array:
-
If nums[j] != nums[i], it means nums[j] is a new unique element.
-
Increment i by 1.
-
Copy nums[j] into nums[i].
-
-
After the loop, i + 1 gives the number of unique elements in the array.
Why Two Pointer Technique Works
-
Sorted arrays ensure duplicates are together.
-
The slow pointer (i) ensures we only keep unique elements at the start.
-
The fast pointer (j) scans for new unique elements.
-
Time Complexity: O(n) :- One pass through the array.
-
Space Complexity: O(1) :- No extra memory used.
This is the optimal solution for in-place duplicate removal in a sorted array.
class RemoveDuplicates {
public int removeDuplicates(int[] nums) {
if (nums.length == 0) return 0; // edge case: empty array
int i = 0; // slow pointer - tracks last unique element
for (int j = 1; j < nums.length; j++) { // fast pointer - scans array
if (nums[j] != nums[i]) {
i++; // move slow pointer forward
nums[i] = nums[j]; // update unique element
}
}
return i + 1; // length of unique elements
}
public static void main(String[] args) {
RemoveDuplicates sol = new RemoveDuplicates();
int[] nums1 = {1, 1, 2};
int k1 = sol.removeDuplicates(nums1);
System.out.println("Unique count: " + k1);
for (int i = 0; i < k1; i++) System.out.print(nums1[i] + " ");
System.out.println();
int[] nums2 = {0,0,1,1,1,2,2,3,3,4};
int k2 = sol.removeDuplicates(nums2);
System.out.println("Unique count: " + k2);
for (int i = 0; i < k2; i++) System.out.print(nums2[i] + " ");
}
}
Unique count: 2
1 2
Unique count: 5
0 1 2 3 4
Complexity Comparison of Approaches
| Approach | Time Complexity | Space Complexity | In-place | Notes |
|---|---|---|---|---|
| Brute Force (extra Set) | O(n) | O(n) | No | Simple, but not truly in-place |
| Brute Force (Shift duplicates) | O(n²) | O(1) | Yes | Works, but inefficient |
| Two-Pointer (Optimal) | O(n) | O(1) | Yes | Best choice for interviews |