Remove Duplicates from Sorted Array II solution and explanation
Google
TCS
9 more videos on this problem
Remove Duplicates from Sorted Array II - Leetcode 80 - PythonNeetCodeIO · 12:19 · 122K views
Remove Duplicates from Sorted Array 2 | Leetcode 80 | Top 150 Interview questions seriesTechnosage · 10:12 · 49K views
Remove Duplicates from Sorted Array II | Leetcode 80 | ArrayAyushi Sharma · 11:29 · 48K views
Remove Duplicates from Sorted Array II | Live Coding with Explanation | Leetcode - 80Algorithms Made Easy · 5:14 · 33K views
Remove Duplicates From Sorted Array II - Leetcode 80 - Arrays & Strings (Python)Greg Hogg · 5:49 · 21K views
Remove Duplicates from Sorted Array II | leetcode 80 | two pointerNaresh Gupta · 5:58 · 11K views
Remove Duplicates from Sorted Array II | Array | Python | LeetCode 80 | Top Interview 150Ace Leetcode · 9:18 · 1K views
Daily Leetcode #255: Dec 11, 2020 - 80. Remove Duplicates from Sorted Array IIProgramming Live with Larry · 8:50 · 483 views
LeetCode 80: Remove Duplicates from Sorted Array II - In-Depth Solution ExplanationCode Scribbler · 7:09 · 482 views
LeetCode 80 Solved | Remove Duplicates in-place with O(1) SpaceScott Hacks Code · 7:41 · 395 views
The problem
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] <= 104numsis sorted in non-decreasing order.
Approach overview
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 1: Two-Pointer Technique
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.
def removeDuplicates(nums):
if len(nums) <= 2:
return len(nums)
write = 2
for read in range(2, len(nums)):
if nums[read] != nums[write - 2]:
nums[write] = nums[read]
write += 1
return writepublic int removeDuplicates(int[] nums) {
if (nums.length <= 2) return nums.length;
int write = 2;
for (int read = 2; read < nums.length; read++) {
if (nums[read] != nums[write - 2]) {
nums[write] = nums[read];
write++;
}
}
return write;
}int removeDuplicates(vector<int>& nums) {
if (nums.size() <= 2) return nums.size();
int write = 2;
for (int read = 2; read < nums.size(); ++read) {
if (nums[read] != nums[write - 2]) {
nums[write] = nums[read];
++write;
}
}
return write;
}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.
Approach 2: Count Duplicates with Tracking Variable
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.
function removeDuplicates(nums) {
if (nums.length <= 2) return nums.length;
let write = 1, count = 1;
for (let read = 1; read < nums.length; read++) {
if (nums[read] === nums[read - 1]) {
count++;
} else {
count = 1;
}
if (count <= 2) {
nums[write++] = nums[read];
}
}
return write;
}int removeDuplicates(int* nums, int numsSize) {
if (numsSize <= 2) return numsSize;
int write = 1, count = 1;
for (int read = 1; read < numsSize; ++read) {
if (nums[read] == nums[read - 1]) {
++count;
} else {
count = 1;
}
if (count <= 2) {
nums[write++] = nums[read];
}
}
return write;
}public int RemoveDuplicates(int[] nums) {
if (nums.Length <= 2) return nums.Length;
int write = 1, count = 1;
for (int read = 1; read < nums.Length; read++) {
if (nums[read] == nums[read - 1]) {
count++;
} else {
count = 1;
}
if (count <= 2) {
nums[write++] = nums[read];
}
}
return write;
}This JavaScript solution applies the same logic of maintaining a variable to count occurrences while iterating and comparing consecutive elements using a write pointer to overwrite the array in-place maintaining the constraints.
Time Complexity: O(n), Space Complexity: O(1).
Approach 3: Single Pass
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.
- Since the same number can be kept at most
ktimes, we can directly keep the firstkelements of the original array; - For the later numbers, the premise of being able to keep them is: the current number
xcompares with thekth element from the end of the previously kept numbers. If they are different, keep it, otherwise skip it.
Similar problems:
function removeDuplicates(nums: number[]): number {
let k = 0;
for (const x of nums) {
if (k < 2 || x !== nums[k - 2]) {
nums[k++] = x;
}
}
return k;
}func removeDuplicates(nums []int) int {
k := 0
for _, x := range nums {
if k < 2 || x != nums[k-2] {
nums[k] = x
k++
}
}
return k
}impl Solution {
pub fn remove_duplicates(nums: &mut Vec<i32>) -> i32 {
let mut k = 0;
for i in 0..nums.len() {
if k < 2 || nums[i] != nums[k - 2] {
nums[k] = nums[i];
k += 1;
}
}
k as i32
}
}Complexity comparison
| 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 | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Remove Duplicates from Sorted Array II easy or hard?
The problem is generally categorized as Medium difficulty. The logic becomes straightforward once you recognize that the sorted property allows comparing the current element with the value two positions behind to enforce the "at most twice" rule.
Remove Duplicates from Sorted Array II Python/Java solution
Most implementations follow the same logic across languages. Maintain an index for the next valid position and check whether the current element differs from the element two positions earlier. This approach translates cleanly to Python, Java, C++, and other languages while keeping O(n) time and O(1) space.
How to solve Remove Duplicates from Sorted Array II in O(n)?
Iterate through the sorted array using a two-pointer method. Maintain a write pointer and only copy the current number if it differs from the element located two indices before the write position. This ensures no value appears more than twice while processing the array in a single pass.
What is the best approach for Remove Duplicates from Sorted Array II?
The two-pointer technique is the most efficient and commonly expected approach. It scans the sorted array once while maintaining a write index and ensures each number appears at most twice by comparing the current element with the value two positions behind. This runs in O(n) time and uses O(1) extra space.
Is Remove Duplicates from Sorted Array II asked at Google/Amazon/Meta?
Variants of this problem frequently appear in interviews at large tech companies including Amazon, Google, and Meta. It tests understanding of in-place array manipulation, pointer techniques, and leveraging sorted properties to reduce complexity.
What data structure is used in Remove Duplicates from Sorted Array II?
The problem primarily uses arrays with the two-pointer technique. Since the input array is sorted, pointers can efficiently control where valid elements are written without needing extra structures like hash maps or sets.
What is the time complexity of Remove Duplicates from Sorted Array II?
The optimal solution runs in O(n) time because the array is traversed only once. Each element is evaluated exactly one time, and valid elements are written in-place. Space complexity remains O(1) since no additional data structures are required.