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, and the first k positions of the array must contain those unique values.
Approach 1: Two-Pointer Technique (O(n) time, O(1) space)
This approach leverages the fact that the array is already sorted. Use two indices: one pointer tracks the position of the last unique element, and the second pointer scans the array. As you iterate through the array, compare the current element with the last unique value. When a new value appears, move the unique pointer forward and copy the value into that position. The sorted order guarantees that duplicates appear consecutively, so a single linear pass is enough. This is a classic two pointers pattern and is the optimal solution for this problem.
Approach 2: Simple In-Place Overwrite Technique (O(n) time, O(1) space)
This method also scans the array once but focuses directly on writing unique elements sequentially. Maintain a write index representing where the next unique element should go. Start from the second element and compare it with the previous value. If the value differs, write it at the current write index and increment the index. Because the array is sorted, duplicates always appear next to each other, so comparing with the previous element reliably detects new values. This solution works entirely in-place, making it ideal when memory usage must remain constant while processing an array.
Both strategies rely on sequential traversal and constant extra memory. The core insight is recognizing that sorted input eliminates the need for auxiliary structures like hash sets. Instead of storing seen values, you simply detect when the value changes.
Recommended for interviews: The two-pointer solution is the expected answer. Interviewers look for candidates who recognize the sorted property and convert it into a single-pass algorithm using constant memory. A brute-force idea such as using a hash set demonstrates basic problem understanding, but the in-place two-pointer pattern shows stronger algorithmic reasoning and familiarity with common two pointer interview techniques.
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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n)
Space Complexity: O(1)
| 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) |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer Technique | O(n) | O(1) | Best choice when the array is sorted and the result must be produced in-place |
| Simple In-Place Overwrite | O(n) | O(1) | When implementing a straightforward sequential scan with minimal pointer management |
Remove Duplicates from Sorted Array - Leetcode 26 - Python • NeetCode • 246,487 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