Remove Duplicates from Sorted Array - Solution & Explanation
Problem Statement
Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.
Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:
- Change the array
numssuch that the firstkelements ofnumscontain the unique elements in the order they were present innumsinitially. The remaining elements ofnumsare not important as well as the size ofnums. - Return
k.
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,2] Output: 2, nums = [1,2,_] Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 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,2,2,3,3,4] Output: 5, nums = [0,1,2,3,4,_,_,_,_,_] Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively. It does not matter what you leave beyond the returned k (hence they are underscores).
Constraints:
1 <= nums.length <= 3 * 104-100 <= nums[i] <= 100numsis sorted in non-decreasing order.
Approach Overview
Problem Overview: You receive a sorted integer array and must remove duplicate values in-place so each element appears only once. The function returns the number of unique elements while keeping the first k positions of the array filled with those unique values.
Approach 1: Simple In-Place Overwrite Technique (O(n) time, O(1) space)
The array is already sorted, which means duplicates always appear next to each other. Iterate through the array while tracking the last unique value you wrote. When the current element differs from the previous unique value, overwrite the next position in the array with that element. This effectively compacts unique values toward the front while skipping duplicates. The algorithm performs a single linear pass with constant extra memory, making it ideal for problems that require in-place modification of an array.
Approach 2: Two-Pointer Technique (O(n) time, O(1) space)
This approach uses two indices: a read pointer that scans the array and a write pointer that marks the position for the next unique element. Start both at the beginning. As the read pointer iterates, compare nums[read] with the previous element. When they differ, increment the write pointer and copy the value there. Because the input is sorted, this comparison reliably detects duplicates without additional structures like hash sets. This pattern is a classic two pointers optimization for ordered data structures and keeps the solution linear with constant memory.
The key insight is that sorted order groups duplicates together. Instead of removing elements (which would require shifting many values), you simply overwrite positions with the next distinct number encountered. Every element is processed once, so runtime stays proportional to the array size.
Recommended for interviews: Interviewers expect the two-pointer solution. It demonstrates that you recognize the sorted property and can optimize the algorithm to O(n) time with O(1) space. Writing the overwrite logic clearly shows you understand in-place operations and pointer movement. A naive removal approach with repeated shifting works conceptually but performs unnecessary operations and does not demonstrate the same level of algorithmic efficiency.
Approach 1: Two-Pointer Technique
The two-pointer technique is an efficient way to solve this problem in-place. We initialize two pointers, where one (called slow) tracks the position of unique elements, and the other (called fast) traverses the entire array.
Whenever we find a new unique element using the fast pointer, we move the slow pointer one step forward and place the unique element at that position. This way, the array elements from index 0 to the slow pointer are all unique.
We start with the assumption that the array has at least one element if it's non-empty. We initialize two indices: j which tracks the last position of unique elements and starts at 0, and i, which iterates from 1 to the end of the array.
Whenever a non-duplicate element is found by comparing nums[i] with nums[j], j is incremented, and nums[j] is updated with nums[i]. Finally, we return j + 1 as it represents the count of unique elements.
Complexity
Time Complexity: O(n), where n is the number of elements in the array, since each of the n elements is accessed once.
Space Complexity: O(1), since the solution uses only a constant amount of extra space.
Approach 2: Simple In-Place Overwrite Technique
An alternative approach without pointers uses a simple loop to iterate over the array and compare each element with the previous one. The still unique elements overwrite duplicate positions directly in the initial part of the array.
This approach iterates from the second element, comparing it with its predecessor to check duplicates and copying only non-duplicates towards the start.
Complexity
Time Complexity: O(n)
Space Complexity: O(1)
Approach 3: Single Pass
We use a variable k to record the current length of the processed array. Initially, k=0 represents an empty array.
Then we traverse the array from left to right. For each element x we encounter, if k=0 or x neq nums[k-1], we place x in the position of nums[k], and then increment k by 1. Otherwise, x is the same as nums[k-1], so we 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 are looking for, 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 appear at most once. 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 following numbers, the premise of being able to keep them is: the current number
xis compared with the lastkth element of the previously retained numbers. If they are different, keep them, otherwise skip them.
Similar problems:
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
PHP
Complexity Comparison
| Approach | Complexity |
|---|---|
| Two-Pointer Technique | Time Complexity: O(n), where n is the number of elements in the array, since each of the n elements is accessed once. Space Complexity: O(1), since the solution uses only a constant amount of extra space. |
| Simple In-Place Overwrite Technique | Time Complexity: O(n) Space Complexity: O(1) |
| Single Pass | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simple In-Place Overwrite | O(n) | O(1) | When the array is sorted and duplicates appear consecutively |
| Two-Pointer Technique | O(n) | O(1) | Preferred interview approach for in-place array modification |
Video Solution
Remove Duplicates from Sorted Array - Leetcode 26 - Python • NeetCode • 325,045 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Remove Duplicates from Sorted Array easy or hard?
Remove Duplicates from Sorted Array Python/Java solution
How to solve Remove Duplicates from Sorted Array in O(n)?
What is the best approach for Remove Duplicates from Sorted Array?
Is Remove Duplicates from Sorted Array asked at Google/Amazon/Meta?
What data structure is used in Remove Duplicates from Sorted Array?
What is the time complexity of Remove Duplicates from Sorted Array?
Ready to solve this problem?
Practice Remove Duplicates from Sorted Array with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor