Remove Duplicates from Sorted Array
Compress consecutive duplicates in a sorted array in place — single write pointer.
2 min read
two-pointers array
Problem#
Given a sorted array nums, remove duplicates in place. Return the new length k; the first k elements must hold the distinct values in original order.
Examples#
[1,1,2]→k = 2,[1, 2, _][0,0,1,1,1,2,2,3,3,4]→k = 5,[0,1,2,3,4,_,_,_,_,_]
Constraints#
1 <= nums.length <= 3 * 10^4.
Approach#
Write-pointer w starts at 1. For each i ≥ 1, copy nums[i] into nums[w] only when it differs from nums[w-1], then increment w. Sorted input guarantees duplicates are adjacent.
Solution#
class Solution {public: int removeDuplicates(vector<int>& nums) { if (nums.empty()) return 0; int w = 1; for (int i = 1; i < (int)nums.size(); ++i) { if (nums[i] != nums[w - 1]) nums[w++] = nums[i]; } return w; }};func removeDuplicates(nums []int) int { if len(nums) == 0 { return 0 } w := 1 for i := 1; i < len(nums); i++ { if nums[i] != nums[w-1] { nums[w] = nums[i] w++ } } return w}from typing import List
class Solution: def removeDuplicates(self, nums: List[int]) -> int: if not nums: return 0 w = 1 for i in range(1, len(nums)): if nums[i] != nums[w - 1]: nums[w] = nums[i] w += 1 return wfunction removeDuplicates(nums) { if (nums.length === 0) return 0; let w = 1; for (let i = 1; i < nums.length; i++) { if (nums[i] !== nums[w - 1]) { nums[w++] = nums[i]; } } return w;}class Solution { public int removeDuplicates(int[] nums) { if (nums.length == 0) return 0; int w = 1; for (int i = 1; i < nums.length; i++) { if (nums[i] != nums[w - 1]) { nums[w++] = nums[i]; } } return w; }}function removeDuplicates(nums: number[]): number { if (nums.length === 0) return 0; let w = 1; for (let i = 1; i < nums.length; i++) { if (nums[i] !== nums[w - 1]) { nums[w++] = nums[i]; } } return w;}Editorial#
Compare against the last kept value (nums[w - 1]), not the previous read value — that’s what makes the algorithm robust against arbitrarily long runs. Each element is read and written at most once.
Complexity#
- Time: O(n).
- Space: O(1).
Concept revision#
Related#