26. Remove Duplicates from Sorted Array
Model: qwen2.5-coder:14b
Topics: Array,Two Pointers
FAANG asked: 1
Acceptance rate: 46.8%
Problem Breakdown
The problem requires removing duplicates from a sorted array in-place such that each element appears only once. The function should return the new length of the array after duplicates have been removed. The input array is passed by reference, so modifications to it will be reflected by the caller. The constraints specify that the array can contain up to 30,000 elements, with values ranging from -10,000 to 10,000.
Inputs:
- A sorted integer array
nums.
Outputs:
- An integer representing the new length of the array after removing duplicates.
- The first
lenelements ofnumsshould be unique and in ascending order.
Implicit Constraints:
- The solution must use O(1) extra memory.
- The input array is sorted, which allows us to efficiently remove duplicates by comparing adjacent elements.
- Edge cases include an empty array or an array with all identical elements.
Intuition
A brute-force approach would involve creating a new array and copying unique elements from the original array. However, this approach would require O(n) extra space, which is not allowed by the problem constraints.
The key insight is to use two pointers: one for iterating through the array (i) and another for keeping track of the position where the next unique element should be placed (j). By comparing adjacent elements, we can efficiently remove duplicates in-place. This approach leverages the fact that the array is already sorted, allowing us to skip over duplicate elements without needing additional space.
Approach
- Initialize Pointers: Start with two pointers,
iandj, both set to 0. - Iterate Through Array: Use a loop to iterate through the array with pointer
i. - Compare Elements: For each element at index
i, compare it with the element at indexj. - Update Pointers:
- If
nums[i]is greater thannums[j], incrementjand setnums[j]tonums[i]. This effectively moves the unique elements to the front of the array. - If
nums[i]is equal tonums[j], simply move to the next element by incrementingi.
- If
- Return Length: After the loop,
j + 1will be the length of the array with duplicates removed.
Complexity Analysis
- Time Complexity: O(n), where n is the number of elements in the array. We iterate through the array once.
- Space Complexity: O(1). We use only a constant amount of extra space for the two pointers.
Solution
def removeDuplicates(nums):
if not nums:
return 0
i, j = 0, 0
while i < len(nums):
if nums[i] > nums[j]:
j += 1
nums[j] = nums[i]
i += 1
return j + 1
Edge Cases Handled
- Empty Array: If the input array is empty, the function returns 0 immediately.
- All Elements Identical: If all elements in the array are identical, the function will return 1, as only one unique element remains.
- Single Element Array: If the array contains only one element, it is already unique, and the function returns 1.