Remove Duplicates from Sorted Array
Problem link: https://leetcode.com/problems/remove-duplicates-from-sorted-array/
Problem Statement
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.
Return the number of unique elements k. You must modify the array such that the first k elements of nums contain the unique elements in the order they were present initially.
Input
A sorted integer array nums.
Output
The number of unique elements k.
Example
Input: nums = [0,0,1,1,1,2,2,3,3,4] Output: 5, nums = [0,1,2,3,4,,,,,_]
Explanation
We keep the first '0', skip the second '0', pick the first '1', skip the rest of '1's, and so on. The unique elements are moved to the earliest possible empty slots.
Brute Force
Intuition
Use a Set data structure to store unique elements. Since a Set only keeps unique values, we can push everything into it and then put them back into the array.
Approach
- Create a LinkedHashSet to maintain order and uniqueness.
- Iterate through
numsand add every element to the set. - Iterate through the set and overwrite the beginning of the
numsarray with these values. - Return the size of the set.
Dry Run
nums = [1,1,2] Set = {1, 2} nums[0]=1, nums[1]=2 Return 2.
Code (Java)
import java.util.*;
class Solution {
public int removeDuplicates(int[] nums) {
Set<Integer> set = new LinkedHashSet<>();
for (int x : nums) set.add(x);
int i = 0;
for (int x : set) {
nums[i++] = x;
}
return set.size();
}
}
Complexity Analysis
We use a Set to store up to N elements, which requires extra linear space.
Optimal Solution
Intuition
Since the array is sorted, we can use two pointers: i stays at the last known unique element, and j searches for the next different element. When nums[j] is different from nums[i], we know we've found a new unique number.
Approach
- If the array is empty, return 0.
- Initialize
i = 0(this is our 'unique' pointer). - Iterate
jfrom 1 to N-1. - If
nums[j] != nums[i], it means we found a new element. Incrementiand setnums[i] = nums[j]. - Return
i + 1.
Dry Run
nums = [1, 1, 2]
- i=0, j=1: nums[0]==nums[1] (1==1), j continues.
- i=0, j=2: nums[0]!=nums[2] (1!=2), i becomes 1, nums[1]=2.
- End: return i+1 = 2.
Code (Java)
class Solution {
public int removeDuplicates(int[] nums) {
if (nums.length == 0) return 0;
int i = 0;
for (int j = 1; j < nums.length; j++) {
if (nums[j] != nums[i]) {
i++;
nums[i] = nums[j];
}
}
return i + 1;
}
}
Complexity Analysis
We traverse the array only once and modify it in-place without extra storage.
Quick Revision (Brute Force)
- Use a Set for uniqueness
- Copy back to array
- O(N) space
Quick Revision (Optimal)
- Two-Pointer approach
- Compare nums[i] and nums[j]
- Update nums[++i] when new element found
- In-place, O(1) space