A visual walkthrough of the two-pointer technique for in-place deduplication — from brute force to optimal.
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.
Consider the number of unique elements in nums to be k. After removing duplicates, return the number of unique elements k.
The first k elements of nums should contain the unique numbers in sorted order. The remaining elements beyond index k - 1 can be ignored.
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.The simplest approach: iterate through the sorted array, copy each unique element into a new array, then copy back. Let's see it visually:
This works but uses O(n) extra space for the temporary array. The problem says we must do it in-place with O(1) extra memory. We need a smarter approach.
// Brute force: O(n) time, O(n) space int[] temp = new int[nums.length]; int k = 0; for (int i = 0; i < nums.length; i++) { if (i == 0 || nums[i] != nums[i - 1]) temp[k++] = nums[i]; } System.arraycopy(temp, 0, nums, 0, k);
// Brute force: O(n) time, O(n) space temp := []int{} for i, v := range nums { if i == 0 || v != nums[i-1] { temp = append(temp, v) } } copy(nums, temp)
# Brute force: O(n) time, O(n) space temp = [] for i in range(len(nums)): if i == 0 or nums[i] != nums[i - 1]: temp.append(nums[i]) nums[:len(temp)] = temp
// Brute force: O(n) time, O(n) space let mut temp: Vec<i32> = Vec::new(); for (i, &v) in nums.iter().enumerate() { if i == 0 || v != nums[i - 1] { temp.push(v); } } nums[..temp.len()].copy_from_slice(&temp);
// Brute force: O(n) time, O(n) space const temp: number[] = []; for (let i = 0; i < nums.length; i++) { if (i === 0 || nums[i] !== nums[i - 1]) temp.push(nums[i]); } for (let i = 0; i < temp.length; i++) { nums[i] = temp[i]; }
Since the array is sorted, all duplicates are adjacent. We can use two pointers moving in the same direction:
The slow pointer marks the boundary of the "processed unique" region. The fast pointer scans ahead looking for new unique values.
0..slow is unique.slow + 1.Key idea: When nums[fast] != nums[slow], we found a new unique value. Increment slow, then copy the value. This overwrites duplicates in-place without needing extra space.
Let's trace through [1, 1, 2] step by step:
slow=0, fast=1. nums[1] == nums[0] (both 1) → duplicate, skip. fast++.
slow=0, fast=2. nums[2] != nums[0] (2 != 1) → new unique! Increment slow to 1, copy: nums[1] = 2.
Length is 0 → return 0 immediately. The guard clause handles this.
Only one element, already unique. The loop never runs. Return slow + 1 = 1.
Fast never finds a different value. Slow stays at 0. Return 1.
Every element is unique. Each copy overwrites the same position. Array is unchanged, return 4.
class Solution { public int removeDuplicates(int[] nums) { // Guard: empty array if (nums.length == 0) return 0; // slow points to the last unique element int slow = 0; // fast scans every element starting from index 1 for (int fast = 1; fast < nums.length; fast++) { // Found a new unique value? if (nums[fast] != nums[slow]) { slow++; // advance the write position nums[slow] = nums[fast]; // place the unique value } // If equal, fast just moves on (skip duplicate) } // slow is the index of the last unique element // The count of unique elements is slow + 1 return slow + 1; } }
func removeDuplicates(nums []int) int { // Guard: empty array if len(nums) == 0 { return 0 } // slow points to the last unique element slow := 0 // fast scans every element starting from index 1 for fast := 1; fast < len(nums); fast++ { // Found a new unique value? if nums[fast] != nums[slow] { slow++ // advance the write position nums[slow] = nums[fast] // place the unique value } // If equal, fast just moves on (skip duplicate) } // slow is the index of the last unique element // The count of unique elements is slow + 1 return slow + 1 }
class Solution: def remove_duplicates(self, nums: list[int]) -> int: # Guard: empty array if not nums: return 0 # slow points to the last unique element slow = 0 # fast scans every element starting from index 1 for fast in range(1, len(nums)): # Found a new unique value? if nums[fast] != nums[slow]: slow += 1 # advance the write position nums[slow] = nums[fast] # place the unique value # If equal, fast just moves on (skip duplicate) # slow is the index of the last unique element # The count of unique elements is slow + 1 return slow + 1
impl Solution { pub fn remove_duplicates(nums: &mut Vec<i32>) -> i32 { // Guard: empty array if nums.is_empty() { return 0; } // slow points to the last unique element let mut slow = 0; // fast scans every element starting from index 1 for fast in 1..nums.len() { // Found a new unique value? if nums[fast] != nums[slow] { slow += 1; // advance the write position nums[slow] = nums[fast]; // place the unique value } // If equal, fast just moves on (skip duplicate) } // slow is the index of the last unique element // The count of unique elements is slow + 1 (slow + 1) as i32 } }
function removeDuplicates(nums: number[]): number { // Guard: empty array if (nums.length === 0) return 0; // slow points to the last unique element let slow = 0; // fast scans every element starting from index 1 for (let fast = 1; fast < nums.length; fast++) { // Found a new unique value? if (nums[fast] !== nums[slow]) { slow++; // advance the write position nums[slow] = nums[fast]; // place the unique value } // If equal, fast just moves on (skip duplicate) } // slow is the index of the last unique element // The count of unique elements is slow + 1 return slow + 1; }
Enter a sorted array and step through the two-pointer algorithm. Watch the slow and fast pointers move in real time.
The fast pointer visits each element exactly once, giving O(n) time. The slow pointer advances only when a new unique value is found, so it performs at most n writes. We use only two integer variables for O(1) extra space -- no temporary array needed.
A single pass copies unique elements into a temporary array, then a second pass copies them back. Both passes are O(n), but the temp array requires O(n) extra memory proportional to the number of unique elements.
The fast pointer reads each of the n elements exactly once. When a new unique value is found, it is written at the slow position -- at most n writes total. Only two integer index variables are needed, giving true O(1) auxiliary space.
The slow pointer tracks the "write position" -- every unique element is written exactly once. Because the array is sorted, all duplicates are contiguous. The fast pointer simply skips over them while slow holds the boundary. This is the canonical "read/write pointer" pattern for in-place array problems, and O(n) time is inherently optimal since every element must be inspected at least once.
Review these before coding to avoid predictable interview regressions.
Wrong move: Advancing both pointers shrinks the search space too aggressively and skips candidates.
Usually fails on: A valid pair can be skipped when only one side should move.
Fix: Move exactly one pointer per decision branch based on invariant.