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:
LeetCode Solutionsint[] 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.
1 <= nums.length <= 3 * 104-100 <= nums[i] <= 100nums is sorted in non-decreasing order.We iterate through the array once, where n is the length of the input array. Each element is visited exactly once.
We only use a constant amount of extra space for the pointer k, regardless of the input size.
Since the array is sorted, all duplicate elements are consecutive. We use a two-pointer approach where k tracks the position to place the next unique element. We iterate through the array with a pointer i, and whenever we encounter an element different from the previous one, we know it's unique—we copy it to position k and increment k. After iterating through the entire array, k represents the count of unique elements.
We iterate through the array once with pointer j, where n is the length of the input array. Each element is examined exactly once.
We use constant extra space for the two pointers i and j, independent of the input size.
This is a variant of the two-pointer approach using explicit pointers i and j. Pointer j iterates through the array while pointer i tracks where the next unique element should be placed. When j encounters an element different from its predecessor, it's unique—we copy it to position i and advance both pointers. This explicit two-pointer pattern is slightly more readable and mirrors the intuitive thinking of having one pointer to read and one to write.
| Approach | Rating | Time Complexity | Space Complexity | Advantages | Disadvantages |
|---|---|---|---|---|---|
| Two Pointers - Simple | Concise and straightforward with implicit pointer tracking | Implicit pointer may be less intuitive for beginners | |||
| Two Pointers - Explicit | Clear separation of read and write pointers | Slightly more verbose than Solution 1 |
The optimal approach for this problem is Solution 1: Two Pointers - Simple, which achieves time complexity and space complexity. This solution is the most elegant and efficient, using a minimalist two-pointer pattern that directly solves the in-place removal requirement.
class Solution: def removeDuplicates(self, nums: List[int]) -> int: if not nums: return 0
k = 1 # Start from the second element because the first element is always unique
for i in range(1, len(nums)): # If the current element is different from the previous one, it's a unique element if nums[i] != nums[i - 1]: # Copy the unique element to the position k and increment k nums[k] = nums[i] k += 1
return kclass Solution: def removeDuplicates(self, nums: List[int]) -> int: # Edge case: If the input array is empty, return 0 if not nums: return 0
# Initialize two pointers: i for the position of the next unique element, and j for iterating through the array i = 1 j = 1
while j < len(nums): # If the current element is different from the previous one, it's a unique element if nums[j] != nums[j - 1]: nums[i] = nums[j] i += 1
j += 1
return i