Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.
Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.
Return k after placing the final result in the first k slots of nums.
Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.
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,1,2,2,3] Output: 5, nums = [1,1,2,2,3,_] Explanation: Your function should return k = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 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,1,2,3,3] Output: 7, nums = [0,0,1,1,2,3,3,_,_] Explanation: Your function should return k = 7, with the first seven elements of nums being 0, 0, 1, 1, 2, 3 and 3 respectively. It does not matter what you leave beyond the returned k (hence they are underscores).
Constraints:
1 <= nums.length <= 3 * 104-104 <= nums[i] <= 104nums is sorted in non-decreasing order.Problem Overview: You receive a sorted integer array and must modify it in-place so that each value appears at most twice. The relative order must stay the same, and the function returns the new valid length k. Only the first k elements of the array should contain the allowed values.
The key constraint is that the array is already sorted. That property allows you to detect duplicates by comparing nearby elements rather than scanning the entire array repeatedly. Most efficient solutions rely on controlled overwriting while iterating through the array once.
Approach 1: Two-Pointer Technique (O(n) time, O(1) space)
This is the standard optimal solution using the two pointers pattern. Maintain a write pointer that marks where the next valid element should go. Iterate through the array with a read pointer. For each number, check whether it can be placed without violating the “at most twice” rule.
The trick: an element is valid if it differs from the element located two positions before the write pointer (nums[write - 2]). If they are different, the current element can safely be written. Because the array is sorted, identical values appear together, so comparing with the element two slots back ensures no value is written more than twice.
You scan the array once and overwrite elements in-place, making the algorithm O(n) time and O(1) extra space. This approach works well for interview settings because it demonstrates mastery of array traversal and in-place modification on a sorted array.
Approach 2: Count Duplicates with Tracking Variable (O(n) time, O(1) space)
This variation keeps track of how many times the current value has appeared consecutively. Iterate through the array while maintaining a counter for the current element. If the value matches the previous one, increment the count; otherwise reset the counter to 1.
Whenever the count is less than or equal to 2, copy the element to the next write position. If the count exceeds two, skip writing it. Because the array is sorted, duplicates always appear in contiguous blocks, which makes tracking counts straightforward.
This method also performs a single linear pass through the array and modifies elements in-place. Time complexity remains O(n) and space complexity O(1). It is slightly more explicit than the pointer trick and may feel easier to reason about if you prefer tracking state rather than comparing positions.
Recommended for interviews: The two-pointer technique is the solution most interviewers expect. It leverages the sorted property directly and produces a concise O(n) in-place algorithm. Showing the counting approach still demonstrates strong understanding, but the pointer-based condition (nums[i] != nums[k-2]) is considered the cleanest implementation.
This approach uses the two-pointer technique to traverse the array and modify it in-place. The 'write' pointer tracks where the next unique element should be written, ensuring each appears at most twice. The 'read' pointer goes through the array, checking each element.
This Python solution uses two pointers: 'write' initialized at position 2 and 'read' iterating from 2 to the end of the array. The condition nums[read] != nums[write - 2] ensures that we only allow two instances of each element.
C++
Java
Time Complexity: O(n), Space Complexity: O(1), where n is the length of the input array.
This approach utilizes a variable to track the count of each duplicate as we iterate through the sorted array. The array is overwritten by resetting the duplicate counter each time a new element is found.
The C solution uses a count variable to keep track of consecutive duplicates. For each element checked, the count is updated, and elements are copied based on whether they meet the condition of appearing at most twice.
C#
JavaScript
Time Complexity: O(n), Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Two-Pointer Technique | Time Complexity: O(n), Space Complexity: O(1), where n is the length of the input array. |
| Count Duplicates with Tracking Variable | Time Complexity: O(n), Space Complexity: O(1). |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer Technique | O(n) | O(1) | Best choice for sorted arrays when modifying in-place with minimal logic |
| Count Duplicates with Tracking Variable | O(n) | O(1) | When you prefer explicit duplicate counting for clarity |
Remove Duplicates from Sorted Array - Leetcode 26 - Python • NeetCode • 246,487 views views
Watch 9 more video solutions →Practice Remove Duplicates from Sorted Array II with our built-in code editor and test cases.
Practice on FleetCode