Remove Duplicates from Sorted Array
Remove Duplicates from Sorted Array is a easy arrays & hashing problem solved with the two pointer pattern.
The best approach, optimal (two pointers, in place), runs in O(n) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (copy distinct values out and back) up.
Problem
You are given an integer array nums sorted in non-decreasing order. Remove the repeated values in place so that each distinct value appears once, keeping the values in their original relative order.
Return k, the number of distinct values. The first k slots of nums must hold those values; whatever is left in the slots after them is ignored. Do it with O(1) extra memory.
Examples
Example 1
- Input
nums = [2, 2, 5, 7, 7, 7, 9]- Output
4, nums = [2, 5, 7, 9, _, _, _]- Why
- There are four distinct values. They must fill the first four slots in their original order; what is left after them does not matter.
Example 2
- Input
nums = [-3, -3, -3]- Output
1, nums = [-3, _, _]- Why
- Only one distinct value remains.
Example 3
- Input
nums = [1, 4, 6]- Output
3, nums = [1, 4, 6]- Why
- No duplicates, so the array is already in its final form.
Constraints
1 <= nums.length <= 3 * 10^4-100 <= nums[i] <= 100numsis sorted in non-decreasing order.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (copy distinct values out and back) | O(n) | O(n) |
| Optimal (two pointers, in place) | O(n) | O(1) |
1Brute force (copy distinct values out and back)
O(n)One pass to collect and one pass to copy back.O(n)The extra list can hold up to n values, which the in-place requirement wants to avoid.Collect the distinct values in order into a separate list (or an ordered set), then copy them back to the front of nums.
- Walk the array and add each value to a list if it differs from the last value added.
- Copy the list into nums[0 … k - 1].
- Return k, the size of the list.
class Solution {
public int removeDuplicates(int[] nums) {
List<Integer> distinct = new ArrayList<>();
for (int x : nums) {
if (distinct.isEmpty() || distinct.get(distinct.size() - 1) != x) {
distinct.add(x);
}
}
for (int i = 0; i < distinct.size(); i++) {
nums[i] = distinct.get(i);
}
return distinct.size();
}
}class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
distinct: List[int] = []
for x in nums:
if not distinct or distinct[-1] != x:
distinct.append(x)
for i, x in enumerate(distinct):
nums[i] = x
return len(distinct)class Solution {
public:
int removeDuplicates(vector<int>& nums) {
vector<int> distinct;
for (int x : nums) {
if (distinct.empty() || distinct.back() != x) {
distinct.push_back(x);
}
}
for (int i = 0; i < (int)distinct.size(); i++) {
nums[i] = distinct[i];
}
return distinct.size();
}
};function removeDuplicates(nums) {
const distinct = [];
for (const x of nums) {
if (distinct.length === 0 || distinct[distinct.length - 1] !== x) {
distinct.push(x);
}
}
for (let i = 0; i < distinct.length; i++) {
nums[i] = distinct[i];
}
return distinct.length;
}2Optimal (two pointers, in place)
O(n)Each element is read once.O(1)Only the two indices; the array is rewritten in place.Use write as the length of the deduplicated prefix. Scan with read; whenever nums[read] differs from the last kept value nums[write - 1], it is a new value, so copy it to nums[write] and grow the prefix.
- write = 1 (the first element is always kept).
- For read = 1 … n - 1: if nums[read] != nums[write - 1], set nums[write] = nums[read] and increase write.
- Return write.
class Solution {
public int removeDuplicates(int[] nums) {
int write = 1;
for (int read = 1; read < nums.length; read++) {
if (nums[read] != nums[write - 1]) {
nums[write] = nums[read];
write++;
}
}
return write;
}
}class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
write = 1
for read in range(1, len(nums)):
if nums[read] != nums[write - 1]:
nums[write] = nums[read]
write += 1
return writeclass Solution {
public:
int removeDuplicates(vector<int>& nums) {
int write = 1;
for (int read = 1; read < (int)nums.size(); read++) {
if (nums[read] != nums[write - 1]) {
nums[write] = nums[read];
write++;
}
}
return write;
}
};function removeDuplicates(nums) {
let write = 1;
for (let read = 1; read < nums.length; read++) {
if (nums[read] !== nums[write - 1]) {
nums[write] = nums[read];
write++;
}
}
return write;
}Edge cases to test
- A single element
- Every element is the same
- No duplicates at all
- Long runs of duplicates at the start or the end
Hints
Hint 1
Because the array is sorted, equal values sit next to each other. A value is new exactly when it differs from the one before it.
Hint 2
Keep a write index for the next free slot of the answer, and a read index that scans the whole array.
FAQ
What is the best time complexity for Remove Duplicates from Sorted Array?
Optimal (two pointers, in place) runs in O(n) time and O(1) extra space. Each element is read once.
Which pattern does Remove Duplicates from Sorted Array use?
It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Container With Most Water.
Is there a brute force solution for Remove Duplicates from Sorted Array?
Yes. Brute force (copy distinct values out and back) takes O(n) time and O(n) space. Collect the distinct values in order into a separate list (or an ordered set), then copy them back to the front of nums.
Which edge cases should I test for Remove Duplicates from Sorted Array?
A single element; Every element is the same; No duplicates at all; Long runs of duplicates at the start or the end.