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. Then return the number of unique elements in nums
.
Consider the number of unique elements of nums
to be k
, to get accepted, you need to do the following things:
nums
such that the first k
elements of nums
contain the unique elements in the order they were present in nums
initially. The remaining elements of nums
are not important as well as the size of nums
.k
.Custom Judge:
The judge will test your solution with the following code:
int[] 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.
Example 1:
Input: nums = [1,1,2] Output: 2, nums = [1,2,_] Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively. It does not matter what you leave beyond the returned k (hence they are underscores).
Example 2:
Input: nums = [0,0,1,1,1,2,2,3,3,4] Output: 5, nums = [0,1,2,3,4,_,_,_,_,_] Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively. It does not matter what you leave beyond the returned k (hence they are underscores).
Constraints:
1 <= nums.length <= 3 * 104
-100 <= nums[i] <= 100
nums
is sorted in non-decreasing order.When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
To get rid of the duplicate numbers in a sorted list, the brute force strategy is to create a brand new list. We'll look at each number from the original list one by one and decide if it's unique enough to be added to our new list.
Here's how the algorithm would work step-by-step:
def remove_duplicates_brute_force(sorted_numbers):
# Handle the edge case of an empty list to prevent index errors.
if not sorted_numbers:
return []
# Initialize the new list with the first element, as it's always unique initially.
unique_numbers = [sorted_numbers[0]]
# Iterate through the original list, starting from the second element.
for current_index in range(1, len(sorted_numbers)):
# Check if the current number is a new unique value compared to the last one added.
if sorted_numbers[current_index] != unique_numbers[-1]:
unique_numbers.append(sorted_numbers[current_index])
return unique_numbers
The key insight is to take advantage of the sorted nature of the numbers. Since all identical numbers are grouped together, we can process the collection in a single pass, keeping a separate section at the beginning for the unique numbers we've found so far.
Here's how the algorithm would work step-by-step:
def remove_duplicates(sorted_numbers):
if not sorted_numbers:
return 0
# The placement finger starts after the first element, which is always unique.
placement_index = 1
# The seeker finger iterates through the list to find the next unique number.
for seeker_index in range(1, len(sorted_numbers)):
# A new unique number is found if it's different from the last one recorded.
if sorted_numbers[seeker_index] != sorted_numbers[placement_index - 1]:
# This new unique number is placed at the next available unique slot.
sorted_numbers[placement_index] = sorted_numbers[seeker_index]
placement_index += 1
return placement_index
Case | How to Handle |
---|---|
Input array is empty | The solution should handle this gracefully by returning 0, as there are no elements to process. |
Input array contains only one element | The algorithm correctly returns 1, as a single-element array has no duplicates. |
All elements in the array are identical | The two-pointer approach correctly processes the entire array and returns 1, leaving just the first element. |
No duplicate elements exist in the array | The solution will correctly iterate through the array, find no duplicates, and return the original array length. |
Array contains negative numbers and zeros | The comparison logic works identically for negative numbers, zeros, and positive numbers, so no special handling is needed. |
Duplicates appear at the beginning or end of the array | The two-pointer method is robust enough to handle duplicate clusters regardless of their position in the sorted array. |
Very large input array near memory or time limits | The in-place O(N) time and O(1) space solution is highly efficient and scales well for large inputs without issues. |
Array contains integer boundary values like INT_MIN or INT_MAX | Standard integer comparisons work correctly with boundary values, so the algorithm handles them without modification. |