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:
nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.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] <= 100nums is sorted in non-decreasing order.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.
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.
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.
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.
Time Complexity: O(n)
Space Complexity: O(1)
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.
k times, we can directly keep the first k elements of the original array;x is compared with the last kth element of the previously retained numbers. If they are different, keep them, otherwise skip them.Similar problems:
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
PHP
| 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 | — |
| 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 |
Remove Duplicates from Sorted Array - Leetcode 26 - Python • NeetCode • 312,845 views views
Watch 9 more video solutions →Practice Remove Duplicates from Sorted Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor