Watch 10 video solutions for Remove Duplicates from Sorted Array, a easy level problem involving Array, Two Pointers. This walkthrough by NeetCode has 246,487 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |