Watch 10 video solutions for Remove Duplicates from Sorted Array II, a medium level problem involving Array, Two Pointers. This walkthrough by NeetCodeIO has 115,771 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |