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 are given a sorted array and must remove duplicates in-place so that each unique element appears at most twice. The function returns the new length while keeping the first k elements valid. Because the array is already sorted, duplicates always appear consecutively, which allows efficient in-place processing.
Approach 1: Two-Pointer Technique (O(n) time, O(1) space)
This approach leverages the sorted property of the array and processes it using two pointers. One pointer scans the array while the other marks the position where the next valid element should be written. For every number, compare it with the element located two positions before the write pointer. If the current value is different, it means adding it will not exceed the "at most twice" constraint, so write it and move the pointer forward. This works because duplicates appear next to each other in a sorted list. The algorithm runs in O(n) time since each element is visited once and uses O(1) extra space because modifications happen directly inside the input array. This is the most common solution using two pointers on a sorted array.
Approach 2: Count Duplicates with Tracking Variable (O(n) time, O(1) space)
Another method explicitly tracks how many times the current value has appeared. Iterate through the array while maintaining a counter for the current number and reset the counter when the value changes. If the counter is less than or equal to two, copy the element to the next available position in the array. When the counter exceeds two, skip the element. This technique still scans the array once, giving O(n) time complexity with O(1) extra space. The logic is slightly more verbose than the pointer comparison approach but easier to reason about for developers who prefer explicit state tracking over pointer arithmetic.
Recommended for interviews: The two-pointer technique is what most interviewers expect because it directly uses the sorted property and keeps the logic compact. Showing the counting method first demonstrates understanding of the constraint, but implementing the pointer-based solution shows stronger mastery of in-place array manipulation and common interview patterns.
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.
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
C#
JavaScript
Time Complexity: O(n), Space Complexity: O(1).
We use a variable k to record the current length of the array that has been processed. Initially, k=0, representing an empty array.
Then we traverse the array from left to right. For each element x we traverse, if k < 2 or x neq nums[k-2], we put x in the position of nums[k], and then increment k by 1. Otherwise, x is the same as nums[k-2], we directly skip this element. Continue to traverse until the entire array is traversed.
In this way, when the traversal ends, the first k elements in nums are the answer we want, and k is the length of the answer.
The time complexity is O(n), and the space complexity is O(1). Here, n is the length of the array.
Supplement:
The original problem requires that the same number appears at most 2 times. We can extend it to keep at most k identical numbers.
k times, we can directly keep the first k elements of the original array;x compares with the kth element from the end of the previously kept numbers. If they are different, keep it, otherwise skip it.Similar problems:
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
| 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). |
| Single Pass | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer Technique | O(n) | O(1) | Best choice when the array is sorted and in-place modification is required |
| Count Duplicates with Tracking Variable | O(n) | O(1) | Useful when explicit duplicate counting makes the logic easier to understand |
Remove Duplicates from Sorted Array II - Leetcode 80 - Python • NeetCodeIO • 115,771 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