Remove Duplicates from Sorted Array II — Problem & Solution
Remove Duplicates from Sorted Array II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Remove Duplicates from Sorted Array II is a medium coding problem on arrays and two pointers, asked in Amazon, Microsoft, Adobe and Meta interviews.
- Difficulty: Medium
- Topics: Arrays, Two Pointers
- Asked at: Amazon, Microsoft, Adobe, Meta, Freshworks
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer array nums sorted in non-decreasing order, remove extra copies so that each distinct value appears at most twice, keeping the relative order.
Return the resulting array.
Example 1
Input: nums = [1,1,1,2,2,3]
Output: [1,1,2,2,3]
Explanation: The third 1 is dropped.
Example 2
Input: nums = [0,0,1,1,1,1,2,3,3]
Output: [0,0,1,1,2,3,3]
Example 3
Input: nums = [1,2,3]
Output: [1,2,3]
Constraints
1 <= nums.length <= 40-100 <= nums[i] <= 100nums is sorted in non-decreasing order.
Follow-up: The interview version does this in place with O(1) extra memory.
Hints for Remove Duplicates from Sorted Array II
Hint 1
Keep a write cursor. A value is safe to keep if it differs from the element two places back in the output.
Hint 2
That single comparison enforces 'at most twice' without counting runs explicitly.
Hint 3
The first two elements are always kept, which the same check handles automatically.
How to solve Remove Duplicates from Sorted Array II
Keep a value if it differs from the element two places back in the output; that alone enforces "at most twice" on a sorted array.
Approach
- Walk the input, appending to
out. - Append
xwhenouthas fewer than two elements orout[-2] != x.
Why it works
In sorted order, equal values are adjacent; if out[-2] == x then out[-1] == x too and a third copy would follow. Any other value is a new run or a legitimate second copy.
Complexity
- Time —
O(n) - Space —
O(1) extra in the in-place write-cursor form
Pitfalls
- Comparing with
out[-1]only allows one copy — that is thek = 1version of the problem.
Reference solution
Python
def removeDuplicates(nums):
out = []
for x in nums:
if len(out) < 2 or out[-2] != x:
out.append(x)
return outJava
public static int[] removeDuplicates(int[] nums) {
int[] out = new int[nums.length];
int len = 0;
for (int v : nums) {
if (len < 2 || out[len - 2] != v) out[len++] = v;
}
return Arrays.copyOf(out, len);
}C++
vector<int> removeDuplicates(vector<int>& nums) {
vector<int> out;
for (int v : nums) {
if (out.size() < 2 || out[out.size() - 2] != v) out.push_back(v);
}
return out;
}JavaScript
var removeDuplicates = function(nums) {
const out = [];
for (let i = 0; i < nums.length; i++) {
if (out.length < 2 || out[out.length - 2] !== nums[i]) out.push(nums[i]);
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Two Pointers Technique