Given a sorted array nums, remove the duplicates in-place such that each element appears only once and returns the new length. Do not allocate extra space for another array; you must do this by modifying the input array in-place with O(1) extra memory.
Example 1:
Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Function should return the new length, which is 2, and the first two elements of nums being modified to 1 and 2 respectively. It does not matter what is left beyond the new length.
Example 2:
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: Function should return the new length, which is 5, and the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively. It does not matter what is left beyond the new length.
Q: Can the input array be empty? A: Yes, the input array can be empty. If the array is empty, the return value should be 0.
Q: Should the function handle negative numbers? A: Yes, the function should handle both positive and negative numbers since the array is sorted.
Q: Does the order of elements matter after removing duplicates? A: Yes, the order should be maintained as it is in the sorted array.
Since the array is sorted, all duplicates are adjacent. We can use the two-pointer technique where one pointer i tracks the place for the next unique element, and another pointer j scans through the array to find the next unique element.
def removeDuplicates(nums):
if not nums:
return 0
# Initialize the first pointer
i = 0
for j in range(1, len(nums)):
if nums[j] != nums[i]:
i += 1
nums[i] = nums[j]
return i + 1
# Example usage:
nums = [0,0,1,1,1,2,2,3,3,4]
length = removeDuplicates(nums)
print(length) # Output: 5
print(nums[:length]) # Output: [0, 1, 2, 3, 4]
Time Complexity: (O(n)), where (n) is the length of the input array. This is because we only traverse the array once with the j pointer.
Space Complexity: (O(1)), since we are not using any additional space proportional to the input size; only a few extra variables are used.
This solution effectively removes duplicates in-place with minimal extra memory and maintains the order of the array.
Got blindsided by a question you didn’t expect?
Spend too much time studying?
Or simply don’t have the time to go over all 3000 questions?