Remove Duplicates from Sorted Array
Compact a sorted array so each value appears once, in place, using the fact that duplicates sit next to each other. The standard drill for the slow/fast two-pointer pattern. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
You're given an integer array nums sorted in non-decreasing order. Rearrange it in place so that each distinct value appears exactly once at the front of the array, in the same sorted order. Let k be the number of distinct values; after your function runs, nums[0..k) must hold them.
Use only O(1) extra memory: overwrite nums itself rather than building a second array. What you leave in positions k and beyond doesn't matter.
How this page grades it: the classic version returns k and the grader then reads the first k elements of nums. Here, finish by returning that prefix, nums[:k] in Python or nums.slice(0, k) in JavaScript, so both the count and the contents are checked. Its length is k.
Example 1
- Input
- nums = [2, 2, 5, 7, 7, 7]
- Output
- [2, 5, 7]
k = 3. After the call nums starts with 2, 5, 7; whatever follows is ignored.
Example 2
- Input
- nums = [-3, -3, -3]
- Output
- [-3]
Example 3
- Input
- nums = [1, 4, 9]
- Output
- [1, 4, 9]
Already distinct, so k = 3 and nothing has to move.
Constraints
- 1 ≤ nums.length ≤ 3 × 10⁴
- -10⁴ ≤ nums[i] ≤ 10⁴
- nums is sorted in non-decreasing order.
Practice
Runs 12 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Remove Duplicates from Sorted Array in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Remove Duplicates from Sorted Array
Pattern: Slow/fast two pointers
Because the array is sorted, every copy of a value is in one contiguous block. A value is "new" exactly when it differs from the last value you kept.
Keep a write pointer k marking the end of the kept prefix, and scan with a read pointer. When the read pointer finds a value different from nums[k - 1], copy it to nums[k] and advance k. The kept prefix is always sorted and distinct, and the write pointer never passes the read pointer, so you never overwrite something you still need to read.
Approach 1: Delete duplicates as you find them
Walk the array and, whenever nums[i] == nums[i - 1], remove nums[i] with pop(i) or splice. It is in place, but each removal shifts the rest of the array, so a long run of duplicates costs quadratic time.
Time O(n²) · Space O(1)
Approach 2: Copy distinct values to a new array
Build a list of values that differ from their predecessor, then copy it back over nums. Linear time and easy to reason about, but it breaks the O(1) memory rule.
Time O(n) · Space O(n)
Approach 3: Write pointer over the kept prefix
Set k = 1 (the first element is always kept). For each i from 1 to n - 1:
- If
nums[i] != nums[k - 1], setnums[k] = nums[i]and incrementk.
At the end the first k slots hold the distinct values. Return nums[:k] for this page's grader.
Time O(n) · Space O(1) extra (the returned prefix is the answer itself)
| Approach | Time | Space |
|---|---|---|
| Delete duplicates as you find them | O(n²) | O(1) |
| Copy distinct values to a new array | O(n) | O(n) |
| Write pointer over the kept prefix | O(n) | O(1) extra (the returned prefix is the answer itself) |
Solution code
Try the practice editor first. Both solutions pass every test above.
Remove Duplicates from Sorted Array solution in Python
def remove_duplicates(nums: list[int]) -> list[int]:
k = 1 # nums[:k] holds the distinct values seen so far
for i in range(1, len(nums)):
if nums[i] != nums[k - 1]:
nums[k] = nums[i]
k += 1
return nums[:k]Remove Duplicates from Sorted Array solution in JavaScript
function removeDuplicates(nums) {
let k = 1; // nums[0..k) holds the distinct values seen so far
for (let i = 1; i < nums.length; i++) {
if (nums[i] !== nums[k - 1]) {
nums[k] = nums[i];
k++;
}
}
return nums.slice(0, k);
}Common mistakes
- Comparing `nums[i]` with `nums[i - 1]` after earlier writes have changed `nums[i - 1]`. Comparing with `nums[k - 1]` (the last kept value) is always safe.
- Removing elements while iterating forward, which skips the element that slides into the current index.
- Using a set, which ignores the sorted order guarantee and uses O(n) memory.
- Starting `k` at 0 and forgetting that the first element is always kept, which produces an off-by-one in the count.
What interviewers look for
Name the invariant before you code: "nums[0..k) holds the distinct values seen so far, in order." Interviewers want to hear that you know exactly what each pointer means, because the same structure solves Remove Element, Move Zeroes and the "allow at most two copies" variant.
Point out that sortedness is what makes the O(1) memory solution possible. Without it you would need a hash set.
Follow-up questions
What if each value may appear at most twice?
Compare against `nums[k - 2]` instead of `nums[k - 1]`: keep `nums[i]` if `k < 2` or `nums[i] != nums[k - 2]`. In general, for at most m copies, compare against `nums[k - m]`.
What if the array is not sorted?
Either sort first (O(n log n), loses the original order) or keep a hash set of seen values and use the same write-pointer pattern, which preserves first-occurrence order at O(n) memory.
How would you do the same for a sorted linked list?
Walk the list and, whenever `node.next.val == node.val`, splice out `node.next` by pointing `node.next` to `node.next.next`. Only advance when the next value differs. O(n) time, O(1) memory.
Companies that ask Remove Duplicates from Sorted Array
Remove Duplicates from Sorted Array is tagged by 109 companies in our interview dataset. The score shows how often it comes up at each company.
- General Dynamics Mission Systems100%
- Lululemon100%
- Ncino100%
- D Matrix100%
- Wissen Technology100%
- Culture Amp96%
- Liberty It96%
- NTT94%
- Supermicro92%
- Bae Systems89%
- Ikea87%
- Bandcamp87%
- Fis86%
- Palantir84%
- Sift83%
- Groq82%
- Clever80%
- GitLab80%
- Zuora80%
- Bosch Global80%
- Dxc Technology76%
- Hbc Digital75%
- Glovo75%
- Cloud Software Group74%
and 85 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required